A331128 - OEIS

%I #18 Sep 22 2025 16:01:32

%S 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,

%T 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,

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

%N 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.

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

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

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

%e There are 6 ways to write n = 705 in the desired fashion:

%e 705 = 1*1! + 1*2! + 1*3! + 4*4! + 5*5!;

%e 705 = 1*1! + 1*2! + 5*3! + 3*4! + 5*5!;

%e 705 = 1*1! + 4*2! + 4*3! + 3*4! + 5*5!;

%e 705 = 1*1! + 4*2! + 4*3! + 8*4! + 4*5!;

%e 705 = 1*1! + 1*2! + 5*3! + 8*4! + 4*5!;

%e 705 = 1*1! + 4*2! + 0*3! + 4*4! + 5*5!.

%e Thus a(705) = 6.

%o (SageMath)

%o def factoradic(n):

%o     if n==0:

%o         return [0]

%o     L=[]

%o     i=2

%o     while n!=0:

%o         dm=divmod(n,i)

%o         L.append(dm[1])

%o         n=dm[0]

%o         i+=1

%o     return L

%o @cached_function

%o def carryseq(n):

%o     if n<0:

%o         return 0

%o     elif n==0:

%o         return 1

%o     else:

%o         L=factoradic(n)

%o         k=len(L)

%o         nk=L[-1]

%o         return carryseq(n-nk*factorial(k))+carryseq((nk+1)*factorial(k)-n-2)

%Y Cf. A108731, A084558, A099563.

%K nonn,base

%O 0,3

%A _Tom Edgar_, Jan 10 2020