A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 3,
(3 n + 2)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
3
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
3
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(3 n + 2)
Define , 3, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
3 n
if n modulo, 2, is , 0, then Q(n) equals , --- + 1
2
3 n
if n modulo, 2, is , 1, then Q(n) equals , --- + 3/2
2
d(n) modulo, 3, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 3
d(3 n + a) = Q(3 n + a) + C[a] d(n)
subject to the initial condition
d(0) = 1, d(1) = 1, d(2) = 2
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 3, is
2, 0, 0, 2, 1, 0, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 0, 2, 1, 0, 1, 0, 1,
0, 1, 2, 0, 0, 2, 1, 1, 1, 2, 0, 2, 1, 1, 2, 0, 0, 1, 0, 1, 0, 1, 0, 0, 2,
1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 2, 1, 1,
2, 0, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 2, 1, 1, 2, 0, 0, 1, 0, 1
----------------------------------------------------------------------------\
-----------------
This took, 0.041, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 4
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 4,
(4 n + 3)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
4
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
4
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(4 n + 3)
Define , 5, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 3, C[3] = 3, C[4] = 1
If j is larger then, 4, then C[j]=0
Also let Q(n) be the polynomial, 2 n + 2
d(n) modulo, 4, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 4
d(4 n + a) = Q(4 n + a) + C[a] d(n) + C[a + 4] d(n - 1)
subject to the initial condition
d(0) = 2, d(1) = 2, d(2) = 0, d(3) = 2, d(4) = 0
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 4, is
0, 0, 2, 0, 2, 0, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0,
2, 0, 0, 2, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0,
2, 0, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 2, 0, 2,
2, 0, 2, 0, 0, 2, 0, 2, 0, 2, 0, 2, 2, 0, 2, 0, 0, 2, 0, 2, 2, 0, 2, 0
----------------------------------------------------------------------------\
-----------------
This took, 0.018, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 5
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 5,
(5 n + 4)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
5
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
5
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(5 n + 4)
Define , 7, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 1, C[6] = 1
If j is larger then, 6, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
5 n
if n modulo, 2, is , 0, then Q(n) equals , --- + 2
2
5 n
if n modulo, 2, is , 1, then Q(n) equals , --- + 5/2
2
d(n) modulo, 5, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 5
d(5 n + a) = Q(5 n + a) + C[a] d(n) + C[a + 5] d(n - 1)
subject to the initial condition
d(0) = 2, d(1) = 2, d(2) = 4, d(3) = 1, d(4) = 3, d(5) = 2, d(6) = 1
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 5, is
0, 1, 0, 4, 1, 3, 0, 0, 2, 0, 2, 1, 3, 3, 0, 1, 0, 2, 3, 1, 4, 1, 1, 2, 4, 4, 0,
4, 4, 2, 1, 3, 1, 2, 4, 4, 4, 3, 1, 4, 0, 4, 3, 3, 0, 1, 2, 4, 4, 2, 1, 4,
2, 0, 2, 0, 3, 1, 0, 3, 3, 1, 2, 0, 2, 0, 1, 4, 4, 2, 1, 0, 3, 3, 0, 1, 1,
3, 1, 4, 0, 1, 0, 4, 1, 3, 3, 3, 1, 4, 0, 4, 3, 3, 0, 1, 2, 4, 4, 2, 1
----------------------------------------------------------------------------\
-----------------
This took, 0.021, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 7
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 7,
(7 n + 6)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
7
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
7
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(7 n + 6)
Define , 11, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 3,
C[8] = 3, C[9] = 1, C[10] = 1
If j is larger then, 10, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
7 n
if n modulo, 2, is , 0, then Q(n) equals , --- + 3
2
7 n
if n modulo, 2, is , 1, then Q(n) equals , --- + 7/2
2
d(n) modulo, 7, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 7
d(7 n + a) = Q(7 n + a) + C[a] d(n) + C[a + 7] d(n - 1)
subject to the initial condition
d(0) = 3, d(1) = 3, d(2) = 6, d(3) = 2, d(4) = 5, d(5) = 4, d(6) = 0, d(7) = 2,
d(8) = 1, d(9) = 6, d(10) = 1
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 7, is
0, 4, 1, 5, 6, 3, 1, 1, 3, 6, 5, 4, 0, 2, 5, 3, 6, 0, 3, 0, 3, 3, 6, 2, 5, 4, 0,
2, 5, 3, 6, 0, 3, 0, 3, 5, 1, 1, 4, 2, 5, 1, 6, 0, 0, 6, 1, 5, 2, 1, 0, 1,
2, 5, 1, 6, 1, 1, 2, 4, 4, 1, 0, 5, 3, 2, 6, 6, 2, 3, 4, 6, 5, 1, 5, 2, 4,
3, 3, 4, 2, 5, 1, 6, 2, 2, 5, 0, 3, 0, 3, 6, 2, 4, 0, 1, 4, 4, 5, 4, 3
----------------------------------------------------------------------------\
-----------------
This took, 0.024, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 8
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 8,
(8 n + 7)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
8
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
8
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(8 n + 7)
Define , 13, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 3, C[3] = 7, C[4] = 5, C[5] = 6, C[6] = 2, C[7] = 2,
C[8] = 6, C[9] = 5, C[10] = 7, C[11] = 3, C[12] = 1
If j is larger then, 12, then C[j]=0
Also let Q(n) be the polynomial, 4 n + 4
d(n) modulo, 8, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 8
d(8 n + a) = Q(8 n + a) + C[a] d(n) + C[a + 8] d(n - 1)
subject to the initial condition
d(0) = 4, d(1) = 4, d(2) = 0, d(3) = 4, d(4) = 0, d(5) = 0, d(6) = 4, d(7) = 0,
d(8) = 4, d(9) = 0, d(10) = 4, d(11) = 0, d(12) = 4
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 8, is
4, 4, 0, 4, 0, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 4, 0,
4, 0, 0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 0, 4, 4, 0, 4,
0, 0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 4, 0, 4, 0,
0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 4, 0, 4, 0, 0, 4, 0, 4, 4, 0, 4, 0
----------------------------------------------------------------------------\
-----------------
This took, 0.016, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 9
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 9,
(9 n + 8)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
9
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
9
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(9 n + 8)
Define , 15, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 1,
C[8] = 1, C[9] = 6, C[10] = 6, C[11] = 3, C[12] = 3, C[13] = 1, C[14] = 1
If j is larger then, 14, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
9 n
if n modulo, 2, is , 0, then Q(n) equals , --- + 4
2
9 n
if n modulo, 2, is , 1, then Q(n) equals , --- + 9/2
2
d(n) modulo, 9, can be computed VERY fast (in logarithmic time!) using the fo\
llowing recurrence, taken modulo, 9
d(9 n + a) = Q(9 n + a) + C[a] d(n) + C[a + 9] d(n - 1)
subject to the initial condition
d(0) = 4, d(1) = 4, d(2) = 8, d(3) = 3, d(4) = 7, d(5) = 6, d(6) = 1, d(7) = 4,
d(8) = 8, d(9) = 6, d(10) = 5, d(11) = 7, d(12) = 1, d(13) = 7, d(14) = 5
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 9, is
0, 0, 8, 1, 7, 2, 6, 3, 1, 0, 1, 2, 6, 0, 7, 3, 4, 4, 8, 3, 1, 0, 1, 4, 8, 6, 4,
6, 7, 4, 8, 0, 7, 3, 4, 1, 5, 3, 1, 0, 1, 1, 5, 6, 8, 1, 1, 4, 2, 6, 2, 7,
1, 8, 0, 0, 8, 1, 7, 2, 6, 3, 4, 3, 1, 2, 6, 0, 1, 6, 4, 1, 5, 3, 4, 3, 1,
1, 5, 6, 4, 6, 7, 1, 5, 0, 7, 3, 4, 7, 2, 3, 1, 0, 1, 7, 2, 6, 8, 1, 1
----------------------------------------------------------------------------\
-----------------
This took, 0.027, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 11
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 11,
(11 n + 10)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
11
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
11
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(11 n + 10)
Define , 19, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 10,
C[8] = 10, C[9] = 4, C[10] = 4, C[11] = 10, C[12] = 10, C[13] = 6,
C[14] = 6, C[15] = 3, C[16] = 3, C[17] = 1, C[18] = 1
If j is larger then, 18, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
11 n
if n modulo, 2, is , 0, then Q(n) equals , ---- + 5
2
11 n
if n modulo, 2, is , 1, then Q(n) equals , ---- + 11/2
2
d(n) modulo, 11, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 11
d(11 n + a) = Q(11 n + a) + C[a] d(n) + C[a + 11] d(n - 1)
subject to the initial condition
d(0) = 5, d(1) = 5, d(2) = 10, d(3) = 4, d(4) = 9, d(5) = 8, d(6) = 2, d(7) = 6,
d(8) = 0, d(9) = 9, d(10) = 3, d(11) = 6, d(12) = 5, d(13) = 2, d(14) = 6,
d(15) = 8, d(16) = 6, d(17) = 2, d(18) = 5
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 11, is
1, 9, 0, 9, 1, 0, 4, 4, 9, 10, 0, 2, 10, 2, 6, 10, 10, 4, 0, 6, 9, 10, 9, 5, 0,
2, 4, 1, 10, 2, 7, 5, 8, 1, 2, 1, 0, 5, 2, 2, 8, 3, 7, 9, 0, 9, 9, 3, 1, 2,
9, 6, 0, 4, 5, 5, 2, 9, 2, 5, 5, 4, 0, 6, 9, 8, 7, 10, 5, 1, 3, 3, 1, 5, 10,
7, 2, 3, 10, 4, 1, 10, 8, 10, 9, 4, 4, 7, 8, 8, 10, 7, 10, 4, 8, 10, 4, 3,
10, 6, 4
----------------------------------------------------------------------------\
-----------------
This took, 0.030, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 12
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 12,
(12 n + 11)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
12
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
12
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(12 n + 11)
Define , 21, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 3, C[3] = 7, C[4] = 1, C[5] = 10, C[6] = 10,
C[7] = 2, C[8] = 10, C[9] = 11, C[10] = 5, C[11] = 5, C[12] = 11,
C[13] = 10, C[14] = 2, C[15] = 10, C[16] = 10, C[17] = 1, C[18] = 7,
C[19] = 3, C[20] = 1
If j is larger then, 20, then C[j]=0
Also let Q(n) be the polynomial, 6 n + 6
d(n) modulo, 12, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 12
d(12 n + a) = Q(12 n + a) + C[a] d(n) + C[a + 12] d(n - 1)
subject to the initial condition
d(0) = 6, d(1) = 6, d(2) = 0, d(3) = 6, d(4) = 0, d(5) = 0, d(6) = 6, d(7) = 0,
d(8) = 6, d(9) = 6, d(10) = 0, d(11) = 6, d(12) = 0, d(13) = 6, d(14) = 0,
d(15) = 6, d(16) = 0, d(17) = 6, d(18) = 0, d(19) = 6, d(20) = 0
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 12, is
0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6,
0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0,
6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6,
6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6, 6, 0, 6, 0, 0, 6, 0, 6
----------------------------------------------------------------------------\
-----------------
This took, 0.048, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 13
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 13,
(13 n + 12)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
13
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
13
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(13 n + 12)
Define , 23, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 10,
C[8] = 10, C[9] = 2, C[10] = 2, C[11] = 8, C[12] = 8, C[13] = 2, C[14] = 2,
C[15] = 10, C[16] = 10, C[17] = 6, C[18] = 6, C[19] = 3, C[20] = 3,
C[21] = 1, C[22] = 1
If j is larger then, 22, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
13 n
if n modulo, 2, is , 0, then Q(n) equals , ---- + 6
2
13 n
if n modulo, 2, is , 1, then Q(n) equals , ---- + 13/2
2
d(n) modulo, 13, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 13
d(13 n + a) = Q(13 n + a) + C[a] d(n) + C[a + 13] d(n - 1)
subject to the initial condition
d(0) = 6, d(1) = 6, d(2) = 12, d(3) = 5, d(4) = 11, d(5) = 10, d(6) = 3,
d(7) = 8, d(8) = 1, d(9) = 12, d(10) = 5, d(11) = 9, d(12) = 2, d(13) = 12,
d(14) = 11, d(15) = 1, d(16) = 6, d(17) = 2, d(18) = 0, d(19) = 2,
d(20) = 6, d(21) = 1, d(22) = 11
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 13, is
6, 1, 8, 0, 0, 2, 8, 7, 2, 11, 8, 1, 0, 3, 4, 4, 7, 4, 9, 3, 10, 8, 4, 6, 4, 10,
10, 7, 9, 10, 1, 6, 12, 8, 0, 0, 4, 8, 11, 6, 8, 7, 8, 11, 11, 5, 4, 10, 8,
0, 10, 1, 10, 0, 8, 10, 4, 5, 11, 11, 1, 0, 0, 11, 8, 5, 12, 8, 12, 7, 8, 2,
0, 2, 10, 7, 12, 4, 6, 6, 5, 0, 9, 12, 5, 3, 5, 11, 9, 10, 4, 0, 3, 7, 6, 5,
0, 7, 11, 10, 10
----------------------------------------------------------------------------\
-----------------
This took, 0.074, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 15
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 15,
(15 n + 14)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
15
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
15
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(15 n + 14)
Define , 27, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 10,
C[8] = 10, C[9] = 0, C[10] = 0, C[11] = 6, C[12] = 6, C[13] = 13,
C[14] = 13, C[15] = 6, C[16] = 6, C[17] = 0, C[18] = 0, C[19] = 10,
C[20] = 10, C[21] = 6, C[22] = 6, C[23] = 3, C[24] = 3, C[25] = 1,
C[26] = 1
If j is larger then, 26, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
15 n
if n modulo, 2, is , 0, then Q(n) equals , ---- + 7
2
15 n
if n modulo, 2, is , 1, then Q(n) equals , ---- + 15/2
2
d(n) modulo, 15, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 15
d(15 n + a) = Q(15 n + a) + C[a] d(n) + C[a + 15] d(n - 1)
subject to the initial condition
d(0) = 7, d(1) = 7, d(2) = 14, d(3) = 6, d(4) = 13, d(5) = 12, d(6) = 4,
d(7) = 10, d(8) = 2, d(9) = 0, d(10) = 7, d(11) = 12, d(12) = 4, d(13) = 1,
d(14) = 8, d(15) = 12, d(16) = 11, d(17) = 7, d(18) = 13, d(19) = 1,
d(20) = 14, d(21) = 9, d(22) = 14, d(23) = 1, d(24) = 13, d(25) = 7,
d(26) = 11
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 15, is
5, 6, 0, 14, 1, 13, 8, 3, 6, 14, 10, 3, 7, 0, 12, 5, 10, 3, 1, 9, 0, 8, 7, 0, 7,
0, 13, 6, 10, 3, 13, 6, 7, 0, 7, 0, 13, 6, 10, 3, 13, 8, 9, 6, 13, 12, 10,
11, 0, 3, 13, 3, 4, 11, 3, 12, 8, 4, 4, 2, 6, 6, 14, 1, 13, 2, 3, 9, 14, 7,
1, 13, 11, 12, 14, 4, 10, 4, 14, 12, 11, 13, 1, 7, 14, 9, 3, 2, 13, 1, 14,
6, 6, 2, 4, 4, 8, 12, 3, 11, 4
----------------------------------------------------------------------------\
-----------------
This took, 0.066, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 16
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 16,
(16 n + 15)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
16
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
16
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(16 n + 15)
Define , 29, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 3, C[3] = 7, C[4] = 13, C[5] = 6, C[6] = 2, C[7] = 2,
C[8] = 6, C[9] = 15, C[10] = 13, C[11] = 1, C[12] = 11, C[13] = 12,
C[14] = 4, C[15] = 4, C[16] = 12, C[17] = 11, C[18] = 1, C[19] = 13,
C[20] = 15, C[21] = 6, C[22] = 2, C[23] = 2, C[24] = 6, C[25] = 13,
C[26] = 7, C[27] = 3, C[28] = 1
If j is larger then, 28, then C[j]=0
Also let Q(n) be the polynomial, 8 n + 8
d(n) modulo, 16, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 16
d(16 n + a) = Q(16 n + a) + C[a] d(n) + C[a + 16] d(n - 1)
subject to the initial condition
d(0) = 8, d(1) = 8, d(2) = 0, d(3) = 8, d(4) = 0, d(5) = 0, d(6) = 8, d(7) = 0,
d(8) = 8, d(9) = 8, d(10) = 0, d(11) = 8, d(12) = 0, d(13) = 0, d(14) = 8,
d(15) = 0, d(16) = 8, d(17) = 0, d(18) = 8, d(19) = 0, d(20) = 8, d(21) = 0,
d(22) = 8, d(23) = 0, d(24) = 8, d(25) = 0, d(26) = 8, d(27) = 0, d(28) = 8
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 16, is
8, 8, 0, 8, 0, 0, 8, 0, 8, 8, 0, 8, 0, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8,
0, 8, 0, 8, 0, 8, 8, 0, 8, 0, 0, 8, 0, 8, 8, 0, 8, 0, 0, 8, 0, 8, 8, 0, 8,
0, 0, 8, 0, 8, 8, 0, 8, 0, 0, 8, 0, 8, 8, 0, 8, 0, 0, 8, 0, 8, 8, 0, 8, 0,
0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 0, 8, 8, 0, 8, 0
----------------------------------------------------------------------------\
-----------------
This took, 0.059, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 17
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 17,
(17 n + 16)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
17
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ 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 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(17 n + 16)
Define , 31, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 10,
C[8] = 10, C[9] = 15, C[10] = 15, C[11] = 4, C[12] = 4, C[13] = 11,
C[14] = 11, C[15] = 2, C[16] = 2, C[17] = 11, C[18] = 11, C[19] = 4,
C[20] = 4, C[21] = 15, C[22] = 15, C[23] = 10, C[24] = 10, C[25] = 6,
C[26] = 6, C[27] = 3, C[28] = 3, C[29] = 1, C[30] = 1
If j is larger then, 30, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
17 n
if n modulo, 2, is , 0, then Q(n) equals , ---- + 8
2
17 n
if n modulo, 2, is , 1, then Q(n) equals , ---- + 17/2
2
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) = 8, d(1) = 8, d(2) = 16, d(3) = 7, d(4) = 15, d(5) = 14, d(6) = 5,
d(7) = 12, d(8) = 3, d(9) = 1, d(10) = 9, d(11) = 15, d(12) = 6, d(13) = 3,
d(14) = 11, d(15) = 16, d(16) = 7, d(17) = 3, d(18) = 2, d(19) = 6,
d(20) = 13, d(21) = 8, d(22) = 6, d(23) = 9, d(24) = 15, d(25) = 9,
d(26) = 6, d(27) = 8, d(28) = 13, d(29) = 6, d(30) = 2
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 17, is
9, 6, 10, 8, 2, 1, 2, 2, 10, 11, 14, 16, 14, 0, 10, 14, 2, 7, 7, 13, 8, 15, 5,
13, 15, 7, 4, 0, 9, 9, 13, 0, 16, 7, 1, 13, 2, 1, 2, 5, 1, 8, 16, 10, 14,
12, 12, 14, 10, 16, 8, 1, 6, 3, 4, 5, 2, 7, 0, 9, 15, 10, 12, 10, 8, 9, 3,
7, 14, 4, 7, 0, 16, 12, 7, 6, 14, 16, 5, 10, 14, 5, 7, 1, 1, 15, 13, 13, 9,
12, 6, 12, 4, 13, 3, 15, 3, 1, 4, 5, 6
----------------------------------------------------------------------------\
-----------------
This took, 0.083, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 19
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 19,
(19 n + 18)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
19
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
19
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(19 n + 18)
Define , 35, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 1, C[3] = 3, C[4] = 3, C[5] = 6, C[6] = 6, C[7] = 10,
C[8] = 10, C[9] = 15, C[10] = 15, C[11] = 2, C[12] = 2, C[13] = 9,
C[14] = 9, C[15] = 17, C[16] = 17, C[17] = 7, C[18] = 7, C[19] = 17,
C[20] = 17, C[21] = 9, C[22] = 9, C[23] = 2, C[24] = 2, C[25] = 15,
C[26] = 15, C[27] = 10, C[28] = 10, C[29] = 6, C[30] = 6, C[31] = 3,
C[32] = 3, C[33] = 1, C[34] = 1
If j is larger then, 34, then C[j]=0
Also let Q(n) be the quasi-polynomial of quasi-period, 2, such that
19 n
if n modulo, 2, is , 0, then Q(n) equals , ---- + 9
2
19 n
if n modulo, 2, is , 1, then Q(n) equals , ---- + 19/2
2
d(n) modulo, 19, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 19
d(19 n + a) = Q(19 n + a) + C[a] d(n) + C[a + 19] d(n - 1)
subject to the initial condition
d(0) = 9, d(1) = 9, d(2) = 18, d(3) = 8, d(4) = 17, d(5) = 16, d(6) = 6,
d(7) = 14, d(8) = 4, d(9) = 2, d(10) = 11, d(11) = 18, d(12) = 8, d(13) = 5,
d(14) = 14, d(15) = 1, d(16) = 10, d(17) = 6, d(18) = 15, d(19) = 1,
d(20) = 0, d(21) = 14, d(22) = 3, d(23) = 7, d(24) = 5, d(25) = 18,
d(26) = 6, d(27) = 9, d(28) = 6, d(29) = 18, d(30) = 5, d(31) = 7,
d(32) = 3, d(33) = 14, d(34) = 0
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 19, is
13, 7, 6, 6, 14, 1, 18, 11, 18, 17, 14, 0, 6, 17, 13, 11, 16, 1, 15, 6, 10, 7,
1, 4, 7, 16, 9, 5, 7, 9, 1, 9, 10, 5, 15, 16, 16, 4, 13, 7, 14, 14, 0, 6, 9,
2, 3, 2, 1, 6, 3, 14, 9, 7, 0, 4, 14, 5, 13, 12, 18, 6, 10, 6, 8, 12, 12, 5,
3, 4, 0, 9, 3, 1, 12, 18, 8, 3, 1, 4, 10, 2, 16, 16, 0, 8, 0, 16, 16, 2, 10,
4, 1, 3, 8, 18, 12, 15, 17, 13, 4
----------------------------------------------------------------------------\
-----------------
This took, 0.131, seconds,
----------------------------------------------------------------------------\
-----------------
m is, 20
----------------------------------------------------------------------------\
-----------------
A Fast (Log Time!) Way to Determine the Remainder Upon Dividing by, 20,
(20 n + 19)
of the coefficient of, q
in the Unique Formal Power Series Satisfying the Functional Equation
20
q f(q )
f(q) = 1 + -----------------
2
(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
-----
\ n
f(q) = ) c(n) q
/
-----
n = 0
is the unique formal power series satisfying the inhomogeneneous functional \
equation:
20
q f(q )
f(q) = 1 + -----------------
2
(1 - q) (-q + 1)
Let , d(n), be , c(20 n + 19)
Define , 37, integers as follows:
C[0] = 0, C[1] = 1, C[2] = 3, C[3] = 7, C[4] = 13, C[5] = 2, C[6] = 14,
C[7] = 10, C[8] = 10, C[9] = 15, C[10] = 5, C[11] = 1, C[12] = 3,
C[13] = 12, C[14] = 8, C[15] = 12, C[16] = 4, C[17] = 5, C[18] = 15,
C[19] = 15, C[20] = 5, C[21] = 4, C[22] = 12, C[23] = 8, C[24] = 12,
C[25] = 3, C[26] = 1, C[27] = 5, C[28] = 15, C[29] = 10, C[30] = 10,
C[31] = 14, C[32] = 2, C[33] = 13, C[34] = 7, C[35] = 3, C[36] = 1
If j is larger then, 36, then C[j]=0
Also let Q(n) be the polynomial, 10 n + 10
d(n) modulo, 20, can be computed VERY fast (in logarithmic time!) using the f\
ollowing recurrence, taken modulo, 20
d(20 n + a) = Q(20 n + a) + C[a] d(n) + C[a + 20] d(n - 1)
subject to the initial condition
d(0) = 10, d(1) = 10, d(2) = 0, d(3) = 10, d(4) = 0, d(5) = 0, d(6) = 10,
d(7) = 0, d(8) = 10, d(9) = 10, d(10) = 0, d(11) = 10, d(12) = 0, d(13) = 0,
d(14) = 10, d(15) = 0, d(16) = 10, d(17) = 10, d(18) = 0, d(19) = 10,
d(20) = 0, d(21) = 10, d(22) = 0, d(23) = 10, d(24) = 0, d(25) = 10,
d(26) = 0, d(27) = 10, d(28) = 0, d(29) = 10, d(30) = 0, d(31) = 10,
d(32) = 0, d(33) = 10, d(34) = 0, d(35) = 10, d(36) = 0
Just for fun the googol-th through googol+100-th terms of d(n) modulo, 20, is
0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10, 0, 10,
0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 0, 10, 10, 0, 10, 0,
0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10, 10, 0,
10, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10, 10, 0, 10, 0, 0, 10, 0, 10,
10, 0, 10, 0, 0, 10, 0, 10, 10, 0, 10, 0
----------------------------------------------------------------------------\
-----------------
This took, 0.113, seconds,
----------------------------------------------------------------------------\
-----------------
This took, 0.777, seconds.