

A317836


Number of partitions of n with carryfree sum in primorial base.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

"Carryfree sum" in this context means that when the digits of summands (written in primorial base, see A049345) are lined up (rightjustified), 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 kth column from the right (with the rightmost as column 1) over all the summands is the same as the kth 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.


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


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 carryfree 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; };
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)));


CROSSREFS

Cf. A001055, A049345, A002110, A276086, A278226.
Cf. also A317826.
Sequence in context: A230442 A034951 A317826 * A214740 A064848 A212791
Adjacent sequences: A317833 A317834 A317835 * A317837 A317838 A317839


KEYWORD

nonn


AUTHOR

Antti Karttunen, Aug 08 2018


STATUS

approved



