login
A317836
Number of partitions of n with carry-free sum in primorial base.
6
1, 1, 1, 2, 2, 4, 1, 2, 2, 5, 4, 11, 2, 4, 4, 11, 9, 26, 3, 7, 7, 21, 16, 52, 5, 12, 12, 38, 29, 98, 1, 2, 2, 5, 4, 11, 2, 5, 5, 15, 11, 36, 4, 11, 11, 36, 26, 92, 7, 21, 21, 74, 52, 198, 12, 38, 38, 141, 98, 392, 2, 4, 4, 11, 9, 26, 4, 11, 11, 36, 26, 92, 9, 26, 26, 92, 66, 249, 16, 52, 52, 198, 137, 560, 29, 98, 98, 392, 269, 1150, 3, 7
OFFSET
0,4
COMMENTS
"Carry-free sum" in this context means that when the digits of summands (written in primorial base, see A049345) are lined up (right-justified), then summing up of each column will not result in carries to any columns left of that column, that is, the sum of digits of the k-th column from the right (with the rightmost as column 1) over all the summands is the same as the k-th digit in n, thus at most prime(k)-1. Among other things, this implies that in any solution, at most one of the summands may be odd. Moreover, such an odd summand is present if and only if n is odd.
FORMULA
a(n) = A001055(A276086(n)) = A001055(A278226(n)).
EXAMPLE
For n=24, A049345(24) = "400" as 24 = 4*A002110(2) + 0*A002110(1) + 0*A002110(0). This can be partitioned in carry-free way either as "100" + "100" + "100" + "100" {6+6+6+6}, "200" + "100" + "100" {12+6+6}, "200" + "200" {12+12}, "300" + "100" {18+6}, or "400" {24}, thus a(24) = 5.
For n=0..23, A049345(n) = A007623(n), thus a(n) = A317826(n) in the same range. See the examples in the latter sequence for how the values for n=0..5 are formed.
PROG
(PARI)
fcnt(n, m) = {local(s); s=0; if(n == 1, s=1, fordiv(n, d, if(d > 1 & d <= m, s=s+fcnt(n/d, d)))); s};
A001055(n) = fcnt(n, n); \\ From A001055
A276086(n) = { my(i=0, m=1, pr=1, nextpr); while((n>0), i=i+1; nextpr = prime(i)*pr; if((n%nextpr), m*=(prime(i)^((n%nextpr)/pr)); n-=(n%nextpr)); pr=nextpr); m; };
(PARI)
\\ Slightly faster, memoized implementation:
memA001055 = Map();
A001055(n) = {my(v); if(mapisdefined(memA001055, n), v = mapget(memA001055, n), v = fcnt(n, n); mapput(memA001055, n, v); (v)); }; \\ Cached version.
A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ From A046523
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 08 2018
STATUS
approved