A071330 Number of decompositions of n into sum of two prime powers.
0, 1, 1, 2, 2, 3, 2, 3, 3, 4, 3, 4, 3, 4, 3, 4, 3, 5, 3, 5, 4, 4, 2, 5, 3, 5, 4, 5, 3, 6, 3, 7, 5, 7, 4, 7, 2, 6, 4, 6, 3, 6, 3, 6, 5, 6, 2, 8, 3, 8, 4, 6, 2, 9, 3, 7, 4, 6, 2, 8, 3, 7, 4, 7, 3, 9, 2, 8, 5, 7, 2, 10, 3, 8, 6, 7, 3, 9, 2, 9, 4, 7, 4, 11, 3, 9, 4, 7, 3, 12, 4, 8, 3, 7, 2
Offset: 1
Examples
10 = 1 + 3^2 = 2 + 2^3 = 3 + 7 = 5 + 5, therefore a(10) = 4; 11 = 2 + 3^2 = 3 + 2^3 = 4 + 7, therefore a(11) = 3; 12 = 1 + 11 = 3 + 3^2 = 2^2 + 2^3 = 5 + 7, therefore a(12) = 4; a(149)=0, as for all x<149: if x is a prime power then 149-x is not.
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
Programs
-
Haskell
a071330 n = sum $ map (a010055 . (n -)) $ takeWhile (<= n `div` 2) a000961_list -- Reinhard Zumkeller, Jan 11 2013
-
Mathematica
primePowerQ[n_] := Length[ FactorInteger[n]] == 1; a[n_] := (r = 0; Do[ If[ primePowerQ[k] && primePowerQ[n-k], r++], {k, 1, Floor[n/2]}]; r); Table[a[n], {n, 1, 95}](* Jean-François Alcover, Nov 17 2011, after Michael B. Porter *) -
PARI
ispp(n) = (omega(n)==1 || n==1) A071330(n) = {local(r);r=0;for(i=1,floor(n/2),if(ispp(i) && ispp(n-i),r++));r} \\ Michael B. Porter, Dec 04 2009
-
PARI
a(n)=my(s); forprime(p=2,n\2,if(isprimepower(n-p), s++)); for(e=2,log(n)\log(2), forprime(p=2, sqrtnint(n\2,e), if(isprimepower(n-p^e), s++))); s+(!!isprimepower(n-1))+(n==2) \\ Charles R Greathouse IV, Nov 21 2014
Comments