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,
----------------------------------------------------------------------------\
-----------------