cp's OEIS Frontend

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.

%I A331128 #17 Mar 30 2020 03:18:57
%S A331128 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 A331128 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 A331128 6,3,4,1,4,3,6,3,5,2,6,4,8,4,6,2,6
%N 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.
%C A331128 We call such a partition of n a hyperfactorial partition as these are in some sense analogous to hyperbinary partitions (A002487).
%C A331128 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 A331128 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 A331128 There are 6 ways to write n = 705 in the desired fashion:
%e A331128 705 = 1*1! + 1*2! + 1*3! + 4*4! + 5*5!;
%e A331128 705 = 1*1! + 1*2! + 5*3! + 3*4! + 5*5!;
%e A331128 705 = 1*1! + 4*2! + 4*3! + 3*4! + 5*5!;
%e A331128 705 = 1*1! + 4*2! + 4*3! + 8*4! + 4*5!;
%e A331128 705 = 1*1! + 1*2! + 5*3! + 8*4! + 4*5!;
%e A331128 705 = 1*1! + 4*2! + 0*3! + 4*4! + 5*5!.
%e A331128 Thus a(705) = 6.
%o A331128 (Sage)
%o A331128 def factoradic(n):
%o A331128     if n==0:
%o A331128         return [0]
%o A331128     L=[]
%o A331128     i=2
%o A331128     while n!=0:
%o A331128         dm=divmod(n,i)
%o A331128         L.append(dm[1])
%o A331128         n=dm[0]
%o A331128         i+=1
%o A331128     return L
%o A331128 @cached_function
%o A331128 def carryseq(n):
%o A331128     if n<0:
%o A331128         return 0
%o A331128     elif n==0:
%o A331128         return 1
%o A331128     else:
%o A331128         L=factoradic(n)
%o A331128         k=len(L)
%o A331128         nk=L[-1]
%o A331128         return carryseq(n-nk*factorial(k))+carryseq((nk+1)*factorial(k)-n-2)
%Y A331128 Cf. A108731, A084558, A099563.
%K A331128 nonn,base
%O A331128 0,3
%A A331128 _Tom Edgar_, Jan 10 2020