A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 19, (19 n) of the coefficient of, q of the Formal Power Series infinity --------' ' | | 1 | | ---------- | | j | | (19 ) j = 0 1 - q By Shalosh B. Ekhad Theorem: Let c(n) be the coefficient of q^n in the formal power series of th\ e title, in other words let infinity infinity ----- --------' \ n ' | | 1 ) c(n) q = | | ---------- / | | j ----- | | (19 ) n = 0 j = 0 1 - q Let , d(n), be , c(19 n) Define , 19, integers as follows: C[0] = 1, C[1] = 2, C[2] = 3, C[3] = 4, C[4] = 5, C[5] = 6, C[6] = 7, C[7] = 8, C[8] = 9, C[9] = 10, C[10] = 11, C[11] = 12, C[12] = 13, C[13] = 14, C[14] = 15, C[15] = 16, C[16] = 17, C[17] = 18, C[18] = 0 d(n) modulo, 19, can be computed VERY fast (in logarithmic time!) using the f\ ollowing recurrence, taken modulo, 19 d(19 n + a) = C[a] d(n) subject to the initial condition d(0) = 1 Proof: Since we are interested in, d(n) = c(19 n), Let's consider the generating function of d(n), let's call it G(q) infinity ----- \ n G(q) = ) d(n) q / ----- n = 0 Let our original generating function, given in the title, be called f(q) infinity --------' ' | | 1 f(q) = | | ---------- | | j | | (19 ) j = 0 1 - q Obviously, f(q) saisfies the Functional Equation 19 f(q ) f(q) = ------ 1 - q Let us, 19, -sect both sides and take the powers that are congruent to, 0, modulo , 19 It is readily seen that the part belonging to the powers that are, 0, modulo , 1 19, in the formal power series expansion of, ----- 1 - q 19 can be written as, R0(q ), where R0 is the rational function 1 - ------ -1 + q Exctacting the, 0, mudulu , 19, powers from both sides, we get 19 19 19 G(q ) = R0(q ) f(q ) 19 Replacing , q , by , q, we get G(q) = R0(q) f(q) Hence G(q) f(q) = ----- R0(q) Going back to the defining functional equation of f(q), this translates to a\ Functional Equation for G(q) 19 19 G(q ) (q - 1) -G(q) (-1 + q) = - ---------------- 1 - q In other words 19 19 (q - 1) G(q ) G(q) = ---------------- (-1 + q) (1 - q) Doing the partial fraction decomposition we get 19 q - 1 17 16 15 14 13 12 11 10 ---------------- = -q - 2 q - 3 q - 4 q - 5 q - 6 q - 7 q - 8 q (-1 + q) (1 - q) 9 8 7 6 5 4 3 2 - 9 q - 10 q - 11 q - 12 q - 13 q - 14 q - 15 q - 16 q - 17 q - 18 19 - ------ -1 + q and taking it modulo, 19, we get 19 q - 1 17 16 15 14 13 12 11 ---------------- = 18 q + 17 q + 16 q + 15 q + 14 q + 13 q + 12 q (-1 + q) (1 - q) 10 9 8 7 6 5 4 3 2 + 11 q + 10 q + 9 q + 8 q + 7 q + 6 q + 5 q + 4 q + 3 q + 2 q + 1 Hence, modulo, 19, we have the functional equation 17 16 15 14 13 12 11 10 G(q) = (18 q + 17 q + 16 q + 15 q + 14 q + 13 q + 12 q + 11 q 9 8 7 6 5 4 3 2 19 + 10 q + 9 q + 8 q + 7 q + 6 q + 5 q + 4 q + 3 q + 2 q + 1) G(q ) and it is readily seen that this is equivalent to the statement of the theor\ em. QED Just for fun the googol-th through googol+100-th terms of d(n) modulo, 19, is 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ----------------------------------------------------------------------------\ ----------------- This took, 0.022, seconds, ----------------------------------------------------------------------------\ -----------------