A131514 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.

1, 1, 1, 15, 1, 71, 1, 280, 15, 71, 1, 3660, 1, 71, 71, 5775, 1, 3660, 1, 3660, 71, 71, 1, 160440, 15, 71, 280, 3660, 1, 20365, 1, 126126, 71, 71, 71, 415185, 1, 71, 71, 160440, 1, 20365, 1, 3660, 3660, 71, 1, 6387150, 15, 3660, 71, 3660, 1, 160440, 71, 160440

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

Cf. A273013, A002119.

Sequence in context: A201460 A040239 A126141 * A049327 A030527 A027467

Adjacent sequences: A131511 A131512 A131513 * A131515 A131516 A131517

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