login
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.
0
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.
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
KEYWORD
nonn,base
AUTHOR
Tom Edgar, Jan 10 2020
STATUS
approved