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.
LINKS
EXAMPLE
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};
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.
CROSSREFS
KEYWORD
nonn
AUTHOR
Antti Karttunen, Aug 08 2018
STATUS
approved