A358233 Number of ways n can be expressed as an unordered product of two natural numbers that do not generate any carries when added together in the primorial base.
0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 3, 0, 1, 0, 1, 0, 4, 0, 2, 0, 3, 0, 3, 0, 1, 0, 1, 0, 4, 0, 2, 0, 2, 0, 4, 0, 1, 0, 1, 0, 4, 0, 2, 0, 3, 0, 4, 0, 2, 0, 1, 0, 5, 0, 2, 0, 3, 0, 3, 0, 1, 0, 2, 0, 6, 0, 2, 0, 3, 0, 4, 0, 1, 0, 1, 0, 4, 0, 2, 0, 2, 0, 5, 0, 1, 0, 1, 0, 6, 0, 3, 0, 3, 0, 3, 0, 2, 0
Offset: 1
Examples
a(6) = 2, because 6 has only two factor pairs, {1, 6} and {2, 3}, and for both of those pairs the criterion is satisfied, as we have A329041(1, 6) = 1 and A329041(2, 3) = 1. In the latter case the primorial base expansions of 2 and 3 are "10" and "11" (see A049345), which can be added together cleanly (i.e., without carries) to obtain "21" = A049345(2+3).
a(8) = 1, because while there are two ways to factor 8 into two factors, as 1*8 and 2*4, only 1+8 yields a carry-free sum ("1" and "110" added together gives "111" = 9 in primorial base, A049345), while 2+4 (= "10" + "20") is not carry-free, as 2 is the max. allowed digit in the second rightmost place.
Links
Crossrefs
Programs
-
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); }; A329041sq(row,col) = A327936(A276086(row)*A276086(col)); A358233(n) = sumdiv(n, d, ((d <= (n/d)) && 1==A329041sq(d,n/d)));
Formula
a(n) = Sum_{d|n} [d <= (n/d) and A329041(d,n/d) == 1], where [ ] is the Iverson bracket, and the dyadic function A329041 returns 1 only when its two arguments do not generate any carries when added together in the primorial base.
For all n >= 1, a(n) <= A038548(n) [see A358671 for the indices where the equality is attained] and a(n) <= A358236(n).
For all n >= 1, a(2n-1) = 0, a(4n-2) = A358236(4n-2).