A317836 Number of partitions of n with carry-free sum in primorial base.

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

Author

Antti Karttunen, Aug 08 2018

Keywords

• nonn

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.

Examples

			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.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 0..2310
• Index entries for sequences related to partitions
• Index entries for sequences related to primorial base

Crossrefs

Cf. A001055, A049345, A002110, A276086, A278226.

Cf. also A317826.

Programs

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; };
A317836(n) = A001055(A276086(n));

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
A317836(n) = A001055(A046523(A276086(n)));

Formula

a(n) = A001055(A276086(n)) = A001055(A278226(n)).