login
A358236
Number of factorizations of n where the sum of the factors is carryfree when the addition is done in the primorial base.
3
1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 1, 1, 1, 5, 1, 2, 1, 4, 1, 3, 1, 1, 1, 1, 1, 5, 1, 2, 1, 2, 1, 4, 1, 1, 1, 1, 1, 5, 1, 2, 1, 4, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 3, 1, 3, 1, 1, 1, 2, 1, 9, 1, 2, 1, 4, 1, 4, 1, 1, 1, 1, 1, 5, 1, 2, 1, 2, 1, 5, 1, 1, 1, 1, 1, 8, 1, 3, 1, 4, 1, 3, 1, 2, 1
OFFSET
1,4
FORMULA
For all n >= 1, a(2n-1) = 1, a(4n-2) = A358233(4n-2).
For all n >= 1, A358233(n) <= a(n) <= A001055(n).
EXAMPLE
36 has in total 9 = A001055(36) factorizations:
factors in decimal in primorial base Do they generate carries when summed?
[3, 3, 2, 2] [11, 11, 10, 10] Yes, as A049345(3+3+2+2) = "120".
[4, 3, 3] [20, 11, 11] Yes, in the least significant place.
[6, 3, 2] [100, 11, 10] No, 6+3+2 = 11 = "121".
[6, 6] [100, 100] No, 6+6 = 12 = "200".
[9, 2, 2] [111, 10, 10] Yes, in the second place from right.
[9, 4] [111, 20] Ditto.
[12, 3] [200, 11] No, 12+3 = 15 = "211".
[18, 2] [300, 10] No, 18+2 = 20 = "310".
[36] [1100] No, as a single factor never does.
Thus only five of the sums are carryfree, and a(36) = 5.
PROG
(PARI)
A276086(n) = { my(m=1, p=2); while(n, m *= (p^(n%p)); n = n\p; p = nextprime(1+p)); (m); };
A327936(n) = { my(f = factor(n)); for(k=1, #f~, f[k, 2] = (f[k, 2]>=f[k, 1])); factorback(f); };
A358236(n, m=n, facs=List([])) = if(1==n, 1==A327936(factorback(apply(A276086, Vec(facs)))), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs, d); s += A358236(n/d, d, newfacs))); (s));
CROSSREFS
KEYWORD
nonn,base
AUTHOR
Antti Karttunen, Nov 29 2022
STATUS
approved