A331128 Number of ways to write n as n = h_1*1! + h_2*2! + ... + h_k*k! where 0 <= h_i <= 2*i for all i.

1, 1, 2, 1, 2, 1, 3, 2, 4, 2, 3, 1, 3, 2, 4, 2, 3, 1, 3, 2, 4, 2, 3, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6, 4, 8, 4, 6, 2, 5, 3, 6, 3, 4, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6, 4, 8, 4, 6, 2, 5, 3, 6, 3, 4, 1, 4, 3, 6, 3, 5, 2, 6, 4, 8, 4, 6, 2, 6

Offset

0,3

Comments

We call such a partition of n a hyperfactorial partition as these are in some sense analogous to hyperbinary partitions (A002487).

This sequence also counts the possible carry sequences when adding two numbers that sum to n using the traditional algorithm for adding two factorial-base representations.

Links

Table of n, a(n) for n=0..84.

Formula

a(n) = 0 if n<0; a(0) = 1; a(n) = a(n-n_k*k!) + a((n_k+1)*k!-n-2) for n > 0, where n_k is the most significant digit of the factorial-base representation of n (i.e., n_k = A099563(k)).

Example

There are 6 ways to write n = 705 in the desired fashion:
705 = 1*1! + 1*2! + 1*3! + 4*4! + 5*5!;
705 = 1*1! + 1*2! + 5*3! + 3*4! + 5*5!;
705 = 1*1! + 4*2! + 4*3! + 3*4! + 5*5!;
705 = 1*1! + 4*2! + 4*3! + 8*4! + 4*5!;
705 = 1*1! + 1*2! + 5*3! + 8*4! + 4*5!;
705 = 1*1! + 4*2! + 0*3! + 4*4! + 5*5!.
Thus a(705) = 6.

Prog

(Sage)
def factoradic(n):
    if n==0:
        return [0]
    L=[]
    i=2
    while n!=0:
        dm=divmod(n, i)
        L.append(dm[1])
        n=dm[0]
        i+=1
    return L
@cached_function
def carryseq(n):
    if n<0:
        return 0
    elif n==0:
        return 1
    else:
        L=factoradic(n)
        k=len(L)
        nk=L[-1]
        return carryseq(n-nk*factorial(k))+carryseq((nk+1)*factorial(k)-n-2)

Crossrefs

Cf. A108731, A084558, A099563.

Sequence in context: A304574 A139024 A217317 * A154958 A025806 A025802

Adjacent sequences: A331125 A331126 A331127 * A331129 A331130 A331131

Keyword

nonn,base

Author

Tom Edgar, Jan 10 2020

Status

approved