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