login
Number of ways to design a set of three n-sided dice (using nonnegative integers) such that summing the faces can give any integer from 0 to n^3 - 1.
5

%I #31 Feb 18 2023 15:28:56

%S 1,1,1,15,1,71,1,280,15,71,1,3660,1,71,71,5775,1,3660,1,3660,71,71,1,

%T 160440,15,71,280,3660,1,20365,1,126126,71,71,71,415185,1,71,71,

%U 160440,1,20365,1,3660,3660,71,1,6387150,15,3660,71,3660,1,160440,71,160440

%N Number of ways to design a set of three n-sided dice (using nonnegative integers) such that summing the faces can give any integer from 0 to n^3 - 1.

%C 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)

%C 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

%H William P. Orrick, <a href="/A131514/b131514.txt">Table of n, a(n) for n = 1..10000</a>

%H M. Krasner and B. Ranulac, <a href="https://gallica.bnf.fr/ark:/12148/bpt6k31562/f397.item">Sur une propriété des polynomes de la division du cercle</a>, Comptes Rendus Académie des Sciences Paris, 240:397-399, 1937.

%H Matthew C. Lettington and Karl Michael Schmidt, <a href="https://arxiv.org/abs/1910.02455">Divisor Functions and the Number of Sum Systems</a>, arXiv:1910.02455 [math.NT], 2019.

%F 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

%e a(4)=15 because we can choose any of the following 15 configurations for our three dice:

%e [ {0, 1, 2, 3}, {0, 4, 8, 12}, {0, 16, 32, 48} ],

%e [ {0, 1, 2, 3}, {0, 4, 16, 20}, {0, 8, 32, 40} ],

%e [ {0, 1, 2, 3}, {0, 4, 32, 36}, {0, 8, 16, 24} ],

%e [ {0, 1, 4, 5}, {0, 2, 8, 10}, {0, 16, 32, 48} ],

%e [ {0, 1, 4, 5}, {0, 2, 16, 18}, {0, 8, 32, 40} ],

%e [ {0, 1, 4, 5}, {0, 2, 32, 34}, {0, 8, 16, 24} ],

%e [ {0, 1, 8, 9}, {0, 2, 4, 6}, {0, 16, 32, 48} ],

%e [ {0, 1, 8, 9}, {0, 2, 16, 18}, {0, 4, 32, 36} ],

%e [ {0, 1, 8, 9}, {0, 2, 32, 34}, {0, 4, 16, 20} ],

%e [ {0, 1, 16, 17}, {0, 2, 4, 6}, {0, 8, 32, 40} ],

%e [ {0, 1, 16, 17}, {0, 2, 8, 10}, {0, 4, 32, 36} ],

%e [ {0, 1, 16, 17}, {0, 2, 32, 34}, {0, 4, 8, 12} ],

%e [ {0, 1, 32, 33}, {0, 2, 4, 6}, {0, 8, 16, 24} ],

%e [ {0, 1, 32, 33}, {0, 2, 8, 10}, {0, 4, 16, 20} ],

%e [ {0, 1, 32, 33}, {0, 2, 16, 18}, {0, 4, 8, 12} ].

%o (SageMath)

%o @cached_function

%o def R3(i,j,k):

%o if i > 1 and j==1 and k==1:

%o return(1)

%o elif j > 1 or k > 1:

%o divList = divisors(i)[:-1]

%o return(sum(G3(d,j,k) for d in divList) + sum(B3(d,j,k) for d in divList))

%o @cached_function

%o def G3(i,j,k):

%o if i==1 and j > 1 and k==1:

%o return(1)

%o elif i > 1 or k > 1:

%o divList = divisors(j)[:-1]

%o return(sum(R3(i,d,k) for d in divList) + sum(B3(i,d,k) for d in divList))

%o @cached_function

%o def B3(i,j,k):

%o if i==1 and j==1 and k > 1:

%o return(1)

%o elif i > 1 or j > 1:

%o divList = divisors(k)[:-1]

%o return(sum(R3(i,j,d) for d in divList) + sum(G3(i,j,d) for d in divList))

%o def a3(n):

%o if n == 1:

%o return(1)

%o else:

%o return(R3(n,n,n) / 2) # _William P. Orrick_, Jan 26 2023

%Y Cf. A273013, A002119.

%K nonn

%O 1,4

%A H.B. Wassenaar (towr(AT)ai.rug.nl), Aug 14 2007

%E Terms a(16) and beyond from _William P. Orrick_, Jan 26 2023