A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 17, (17 n + 5) of the coefficient of, q in the Unique Formal Power Series Satisfying the Functional Equation 17 q f(q ) f(q) = 1 + q + ---------- 2 7 (-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 ----- \ n f(q) = ) c(n) q / ----- n = 0 is the unique formal power series satisfying the inhomogeneneous functional \ equation: 17 q f(q ) f(q) = 1 + q + ---------- 2 7 (-q + 1) Let , d(n), be , c(17 n + 5) Define , 20, integers as follows: C[0] = 0, C[1] = 1, C[2] = 0, C[3] = 8, C[4] = 0, C[5] = 2, C[6] = 0, C[7] = 1, C[8] = 0, C[9] = 7, C[10] = 0, C[11] = 10, C[12] = 0, C[13] = 16, C[14] = 0, C[15] = 15, C[16] = 0, C[17] = 9, C[18] = 0, C[19] = 16 If j is larger then, 19, then C[j]=0 Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that 24137569 6 15618427 5 if n modulo, 2, is , 0, then Q(n) equals , -------- n + -------- n 46080 7680 7433369 4 1026817 3 1756253 2 5797 + ------- n + ------- n + ------- n + ---- n + 28 2304 384 1440 20 231 142477 3 8435621 4 if n modulo, 2, is , 1, then Q(n) equals , ---- - ------ n + ------- n 1024 384 9216 1419857 5 24137569 6 3508171 2 27659 - ------- n + -------- n + ------- n - ----- n 1280 46080 46080 3840 d(n) modulo, 17, can be computed VERY fast (in logarithmic time!) using the f\ ollowing recurrence, taken modulo, 17 d(17 n + a) = Q(17 n + a) + C[a] d(n) + C[a + 17] d(n - 1) subject to the initial condition d(0) = 11, d(1) = 5, d(2) = 11, d(3) = 14, d(4) = 11, d(5) = 16, d(6) = 11, d(7) = 5, d(8) = 11, d(9) = 3, d(10) = 11, d(11) = 2, d(12) = 11, d(13) = 0, d(14) = 11, d(15) = 6, d(16) = 11, d(17) = 8, d(18) = 16, d(19) = 0 Just for fun the googol-th through googol+100-th terms of d(n) modulo, 17, is 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 5, 11, 14, 11, 16, 11, 5, 11, 3, 11, 2, 11, 0, 11, 6, 11, 8, 0, 0, 8, 11, 6, 11, 0, 11, 2, 11, 3, 11, 5, 11, 16, 11, 14, 5, 5, 14, 11, 16, 11, 5, 11, 3, 11, 2, 11, 0, 11, 6, 11, 8, 2, 0, 7, 11, 10, 11, 2, 11, 16, 11, 6, 11, 3, 11, 12, 11, 15, 6, 3, 5, 11, 1, 11, 6, 11, 10, 11, 12, 11, 16, 11, 4, 11, 0, 11, 16, 11, 11, 11, 11 ----------------------------------------------------------------------------\ ----------------- This took, 0.169, seconds, ----------------------------------------------------------------------------\ -----------------