A071331 Numbers having no decomposition into a sum of two prime powers.

1, 149, 331, 373, 509, 701, 757, 809, 877, 907, 959, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, 2171, 2231

Offset: 1

Author

Reinhard Zumkeller, May 19 2002

Keywords

• nonn
• nice

Comments

Luca & Stanica show that this sequence contains infinitely many Fibonacci numbers. In particular, there is some N such that for all n > N, Fibonacci(1807873 + 3543120*n) is in this sequence. - Charles R Greathouse IV, Jul 06 2011

Chen shows that there are five consecutive odd numbers M-8, M-6, M-4, M-2, M, for which all are members of the sequence. Such M may be large; Chen shows that it is less than 2^(2^253000). In fact, there exists an arithmetic progression of such M, and thus they have positive density. - Charles R Greathouse IV, Jul 06 2011

Links

• T. D. Noe, Table of n, a(n) for n = 1..1000
• Florian Luca and Pantelimon Stănică, Fibonacci numbers that are not sums of two prime powers, Proceedings of the American Mathematical Society 133 (2005), pp. 1887-1890.
• Yong-Gao Chen, Five consecutive positive odd numbers, none of which can be expressed as a sum of two prime powers, Mathematics of Computation 74 (2005), pp. 1025-1031.

Crossrefs

A071330(a(n))=0. Cf. A000961, A109829, A014092.

Programs

Haskell

a071331 n = a071331_list !! (n-1)
a071331_list = filter ((== 0) . a071330) [1..]
-- Reinhard Zumkeller, Jan 11 2013

Mathematica

primePowerQ[n_] := Length[FactorInteger[n]] == 1; decomposableQ[n_] := (r = False; Do[If[primePowerQ[k] && primePowerQ[n - k], r = True; Break[]], {k, 1, Floor[n/2]}]; r); Select[Range[3000], !decomposableQ[#]& ] (* Jean-François Alcover, Jun 13 2012 *)
Join[{1},Select[Range[4,2300],Count[IntegerPartitions[#,{2}],?( AllTrue[ #,PrimePowerQ]&)]==0&]] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale, May 28 2021 *)

PARI

isprimepower(n)=ispower(n,,&n);isprime(n)||n==1;
isA071331(n)=forprime(p=2,n\2,if(isprimepower(n-p),return(0)));forprime(p=2,sqrtint(n\2),for(e=1,log(n\2)\log(p),if(isprimepower(n-p^e),return(0))));!isprimepower(n-1)
\\ Charles R Greathouse IV, Jul 06 2011