A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 20, (20 n + 19) of the coefficient of, q of the Formal Power Series infinity --------' ' | | 1 | | ----------------------------- | | / j \ / / j \2 \ | | | (20 )| | | (20 )| | j = 0 \1 - q / \-\q / + 1/ 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 \ / / j \2 \ ----- | | | (20 )| | | (20 )| | n = 0 j = 0 \1 - q / \-\q / + 1/ Let , d(n), be , c(20 n + 19) Define , 36, integers as follows: C[0] = 1, C[1] = 3, C[2] = 7, C[3] = 13, C[4] = 2, C[5] = 14, C[6] = 10, C[7] = 10, C[8] = 15, C[9] = 5, C[10] = 1, C[11] = 3, C[12] = 12, C[13] = 8, C[14] = 12, C[15] = 4, C[16] = 5, C[17] = 15, C[18] = 15, C[19] = 5, C[20] = 4, C[21] = 12, C[22] = 8, C[23] = 12, C[24] = 3, C[25] = 1, C[26] = 5, C[27] = 15, C[28] = 10, C[29] = 10, C[30] = 14, C[31] = 2, C[32] = 13, C[33] = 7, C[34] = 3, C[35] = 1 If j is larger then, 35, then C[j]=0 d(n) modulo, 20, can be computed VERY fast (in logarithmic time!) using the f\ ollowing recurrence, taken modulo, 20 d(20 n + a) = C[a] d(n) + C[a + 20] d(n - 1) subject to the initial condition d(0) = 10 Proof: Since we are interested in, d(n) = c(20 n + 19), 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 \ / / j \2 \ | | | (20 )| | | (20 )| | j = 0 \1 - q / \-\q / + 1/ Obviously, f(q) saisfies the Functional Equation 20 f(q ) f(q) = ----------------- 2 (1 - q) (-q + 1) Let us, 20, -sect both sides and take the powers that are congruent to, 19, modulo , 20 It is readily seen that the part belonging to the powers that are, 19, modulo , 1 20, in the formal power series expansion of, ----------------- 2 (1 - q) (-q + 1) 19 20 can be written as, q R0(q ), where R0 is the rational function 10 ------------ 2 q - 2 q + 1 Exctacting the, 19, mudulu , 20, powers from both sides, we get 19 20 19 20 20 q G(q ) = q R0(q ) f(q ) 20 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) 20 40 20 2 G(q ) (q - 2 q + 1) 1/10 G(q) (q - 2 q + 1) = 1/10 ------------------------ 2 (1 - q) (-q + 1) In other words 40 20 20 (q - 2 q + 1) G(q ) G(q) = -------------------------------- 2 2 (q - 2 q + 1) (1 - q) (-q + 1) Doing the partial fraction decomposition we get 40 20 q - 2 q + 1 3700 2 20 -------------------------------- = 3501 + ------ + 3303 q + 3107 q + 444 q 2 2 -1 + q (q - 2 q + 1) (1 - q) (-q + 1) 35 34 33 32 31 30 29 28 + q + 3 q + 7 q + 13 q + 22 q + 34 q + 50 q + 70 q 27 26 25 24 23 22 21 + 95 q + 125 q + 161 q + 203 q + 252 q + 308 q + 372 q 19 18 17 16 15 14 13 + 525 q + 615 q + 715 q + 825 q + 944 q + 1072 q + 1208 q 12 11 10 9 8 7 6 + 1352 q + 1503 q + 1661 q + 1825 q + 1995 q + 2170 q + 2350 q 5 4 3 200 + 2534 q + 2722 q + 2913 q + --------- 2 (-1 + q) and taking it modulo, 20, we get 40 20 q - 2 q + 1 35 34 33 32 31 -------------------------------- = q + 3 q + 7 q + 13 q + 2 q 2 2 (q - 2 q + 1) (1 - q) (-q + 1) 30 29 28 27 26 25 24 23 22 + 14 q + 10 q + 10 q + 15 q + 5 q + q + 3 q + 12 q + 8 q 21 20 19 18 17 16 15 14 + 12 q + 4 q + 5 q + 15 q + 15 q + 5 q + 4 q + 12 q 13 12 11 10 9 8 7 6 5 + 8 q + 12 q + 3 q + q + 5 q + 15 q + 10 q + 10 q + 14 q 4 3 2 + 2 q + 13 q + 7 q + 3 q + 1 Hence, modulo, 20, we have the functional equation 35 34 33 32 31 30 29 28 G(q) = (q + 3 q + 7 q + 13 q + 2 q + 14 q + 10 q + 10 q 27 26 25 24 23 22 21 20 19 + 15 q + 5 q + q + 3 q + 12 q + 8 q + 12 q + 4 q + 5 q 18 17 16 15 14 13 12 11 10 + 15 q + 15 q + 5 q + 4 q + 12 q + 8 q + 12 q + 3 q + q 9 8 7 6 5 4 3 2 + 5 q + 15 q + 10 q + 10 q + 14 q + 2 q + 13 q + 7 q + 3 q + 1) 20 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, 20, is 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 ----------------------------------------------------------------------------\ ----------------- This took, 0.030, seconds, ----------------------------------------------------------------------------\ -----------------