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,2

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.

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 *)

Prog

(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
(Haskell)
a071331 n = a071331_list !! (n-1)
a071331_list = filter ((== 0) . a071330) [1..]
-- Reinhard Zumkeller, Jan 11 2013

Crossrefs

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

Sequence in context: A346891 A244661 A146137 * A095842 A142359 A185692

Adjacent sequences: A071328 A071329 A071330 * A071332 A071333 A071334

Keyword

nonn,nice

Author

Reinhard Zumkeller, May 19 2002

Status

approved