cp's OEIS Frontend

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

%I A317836 #17 Aug 26 2018 12:25:55
%S A317836 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,
%T A317836 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,
%U A317836 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
%N A317836 Number of partitions of n with carry-free sum in primorial base.
%C A317836 "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.
%H A317836 Antti Karttunen, <a href="/A317836/b317836.txt">Table of n, a(n) for n = 0..2310</a>
%H A317836 <a href="/index/Par#part">Index entries for sequences related to partitions</a>
%H A317836 <a href="/index/Pri#primorialbase">Index entries for sequences related to primorial base</a>
%F A317836 a(n) = A001055(A276086(n)) = A001055(A278226(n)).
%e A317836 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.
%e A317836 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.
%o A317836 (PARI)
%o A317836 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};
%o A317836 A001055(n) = fcnt(n, n); \\ From A001055
%o A317836 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; };
%o A317836 A317836(n) = A001055(A276086(n));
%o A317836 (PARI)
%o A317836 \\ Slightly faster, memoized implementation:
%o A317836 memA001055 = Map();
%o A317836 A001055(n) = {my(v); if(mapisdefined(memA001055,n), v = mapget(memA001055,n), v = fcnt(n, n); mapput(memA001055,n,v); (v));}; \\ Cached version.
%o A317836 A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); };  \\ From A046523
%o A317836 A317836(n) = A001055(A046523(A276086(n)));
%Y A317836 Cf. A001055, A049345, A002110, A276086, A278226.
%Y A317836 Cf. also A317826.
%K A317836 nonn
%O A317836 0,4
%A A317836 _Antti Karttunen_, Aug 08 2018