login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317836 Number of partitions of n with carry-free 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

"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

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 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.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 25 16:04 EDT 2019. Contains 322461 sequences. (Running on oeis4.)