OFFSET
1,4
COMMENTS
Also the number of ways to factor (x^(n^3)-1)/(x-1) into p(x)*q(x)*r(x), such that p(x),q(x),r(x) are polynomials with exactly n terms and all coefficients +1 (and all exponents nonnegative). (Krasner and Ranulac, 1937)
a(n) depends only on the prime signature of n. Hence a(n) will be 1 for all primes, 15 for all squares of primes, 71 for all products of distinct primes, and so on. - William P. Orrick, Jan 26 2023
LINKS
William P. Orrick, Table of n, a(n) for n = 1..10000
M. Krasner and B. Ranulac, Sur une propriété des polynomes de la division du cercle, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.
Matthew C. Lettington and Karl Michael Schmidt, Divisor Functions and the Number of Sum Systems, arXiv:1910.02455 [math.NT], 2019.
FORMULA
Recurrence: a(1) = 1. For n > 1, a(n) = r(n,n,n) / 2 where r(i,1,1) = g(1,j,1) = b(1,1,k) = 1 for all i, j, k > 1, r(i,j,k) = Sum_{d|i,d<i} (g(d,j,k) + b(d,j,k)) for j, k not both 1, g(i,j,k) = Sum_{d|j,d<j} (r(i,d,k) + b(i,d,k)) for i, k not both 1, and b(i,j,k) = Sum_{d|k,d<k} (r(i,j,d) + g(i,j,d)) for i, j not both 1. - William P. Orrick, Jan 26 2023
EXAMPLE
a(4)=15 because we can choose any of the following 15 configurations for our three dice:
[ {0, 1, 2, 3}, {0, 4, 8, 12}, {0, 16, 32, 48} ],
[ {0, 1, 2, 3}, {0, 4, 16, 20}, {0, 8, 32, 40} ],
[ {0, 1, 2, 3}, {0, 4, 32, 36}, {0, 8, 16, 24} ],
[ {0, 1, 4, 5}, {0, 2, 8, 10}, {0, 16, 32, 48} ],
[ {0, 1, 4, 5}, {0, 2, 16, 18}, {0, 8, 32, 40} ],
[ {0, 1, 4, 5}, {0, 2, 32, 34}, {0, 8, 16, 24} ],
[ {0, 1, 8, 9}, {0, 2, 4, 6}, {0, 16, 32, 48} ],
[ {0, 1, 8, 9}, {0, 2, 16, 18}, {0, 4, 32, 36} ],
[ {0, 1, 8, 9}, {0, 2, 32, 34}, {0, 4, 16, 20} ],
[ {0, 1, 16, 17}, {0, 2, 4, 6}, {0, 8, 32, 40} ],
[ {0, 1, 16, 17}, {0, 2, 8, 10}, {0, 4, 32, 36} ],
[ {0, 1, 16, 17}, {0, 2, 32, 34}, {0, 4, 8, 12} ],
[ {0, 1, 32, 33}, {0, 2, 4, 6}, {0, 8, 16, 24} ],
[ {0, 1, 32, 33}, {0, 2, 8, 10}, {0, 4, 16, 20} ],
[ {0, 1, 32, 33}, {0, 2, 16, 18}, {0, 4, 8, 12} ].
PROG
(SageMath)
@cached_function
def R3(i, j, k):
if i > 1 and j==1 and k==1:
return(1)
elif j > 1 or k > 1:
divList = divisors(i)[:-1]
return(sum(G3(d, j, k) for d in divList) + sum(B3(d, j, k) for d in divList))
@cached_function
def G3(i, j, k):
if i==1 and j > 1 and k==1:
return(1)
elif i > 1 or k > 1:
divList = divisors(j)[:-1]
return(sum(R3(i, d, k) for d in divList) + sum(B3(i, d, k) for d in divList))
@cached_function
def B3(i, j, k):
if i==1 and j==1 and k > 1:
return(1)
elif i > 1 or j > 1:
divList = divisors(k)[:-1]
return(sum(R3(i, j, d) for d in divList) + sum(G3(i, j, d) for d in divList))
def a3(n):
if n == 1:
return(1)
else:
return(R3(n, n, n) / 2) # William P. Orrick, Jan 26 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
H.B. Wassenaar (towr(AT)ai.rug.nl), Aug 14 2007
EXTENSIONS
Terms a(16) and beyond from William P. Orrick, Jan 26 2023
STATUS
approved