A317826 Number of partitions of n with carry-free sum in factorial 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, 1, 2, 2, 5, 4, 11, 2, 5, 5, 15, 11, 36, 4, 11, 11, 36, 26, 92, 7, 21, 21, 74, 52, 198, 2, 4, 4, 11, 9, 26, 4, 11, 11, 36, 26, 92, 9, 26, 26, 92, 66, 249, 16, 52, 52, 198, 137, 560, 3, 7, 7, 21, 16, 52, 7, 21, 21, 74, 52, 198, 16, 52, 52, 198, 137, 560, 31, 109
Offset: 0
Keywords
Examples
n in fact.base a(n) carry-free partitions
------------------------------
0 "0" 1 {} (unique empty partition, thus a(0) = 1)
1 "1" 1 {1}
2 "10" 1 {2}
3 "11" 2 {2, 1} and {3}, in fact.base: {"10", "1"} and {"11"}
4 "20" 2 {2, 2} and {4}, in fact.base: {"10" "10"} and {"20"}
5 "21" 4 {2, 2, 1}, {3, 2}, {4, 1} and {5},
in factorial base: {"10", "10", "1"}, {"11", "10"}, {"20", "1"} and {"21"}.
Links
Crossrefs
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 A276076(n) = { my(i=0,m=1,f=1,nextf); while((n>0),i=i+1; nextf = (i+1)*f; if((n%nextf),m*=(prime(i)^((n%nextf)/f));n-=(n%nextf));f=nextf); m; }; A317826(n) = A001055(A276076(n)); -
PARI
\\ Slightly faster, memoized version: 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. A276076(n) = { my(i=0,m=1,f=1,nextf); while((n>0),i=i+1; nextf = (i+1)*f; if((n%nextf),m*=(prime(i)^((n%nextf)/f));n-=(n%nextf));f=nextf); m; }; A046523(n) = { my(f=vecsort(factor(n)[, 2], , 4), p); prod(i=1, #f, (p=nextprime(p+1))^f[i]); }; \\ From A046523 A317826(n) = A001055(A046523(A276076(n)));
Comments