The verbose version for the Generalized Capsules for the coefficient of q^(m\
*n+1) mod m
for the unique formal power series satisying thefunctional equation
m
q f(q )
f(q) = 1 + -------
1 - q
for m=10 is
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 10,
(10 n + 1)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
10
q f(q )
f(q) = 1 + --------
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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
10
q f(q )
f(q) = 1 + --------
1 - q
Let , d(n), be , c(10 n + 1)
Define , 10, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 2, C[3] = 3, C[4] = 4, C[5] = 5, C[6] = 6, C[7] = 7,
C[8] = 8, C[9] = 9
Also let Q(n) be the polynomial, 1
d(n) modulo, 10, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 10
d(10 n + a) = Q(10 n + a) + C[a] d(n)
subject to the initial condition
d(0) = 1, d(1) = 2, d(2) = 3, d(3) = 4, d(4) = 5, d(5) = 6, d(6) = 7, d(7) = 8,
d(8) = 9, d(9) = 0
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 10, is
1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 3, 5, 7, 9, 1, 3, 5, 7, 9, 1, 4, 7, 0, 3, 6, 9,
2, 5, 8, 1, 5, 9, 3, 7, 1, 5, 9, 3, 7, 1, 6, 1, 6, 1, 6, 1, 6, 1, 6, 1, 7,
3, 9, 5, 1, 7, 3, 9, 5, 1, 8, 5, 2, 9, 6, 3, 0, 7, 4, 1, 9, 7, 5, 3, 1, 9,
7, 5, 3, 1, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
----------------------------------------------------------------------------\
-----------------
This took, 0.022, seconds,
----------------------------------------------------------------------------\
-----------------