cp's OEIS Frontend

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

%I A071331 #29 Jun 18 2021 18:08:44
%S A071331 1,149,331,373,509,701,757,809,877,907,959,997,1019,1087,1199,1207,
%T A071331 1211,1243,1259,1271,1477,1529,1541,1549,1589,1597,1619,1657,1719,
%U A071331 1759,1777,1783,1807,1829,1859,1867,1927,1969,1973,2171,2231
%N A071331 Numbers having no decomposition into a sum of two prime powers.
%C A071331 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
%C A071331 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
%H A071331 T. D. Noe, <a href="/A071331/b071331.txt">Table of n, a(n) for n = 1..1000</a>
%H A071331 Florian Luca and Pantelimon Stănică, <a href="http://faculty.nps.edu/pstanica/research/fiboprimeProcAMS.pdf">Fibonacci numbers that are not sums of two prime powers</a>, Proceedings of the American Mathematical Society 133 (2005), pp. 1887-1890.
%H A071331 Yong-Gao Chen, <a href="http://www.ams.org/journals/mcom/2005-74-250/S0025-5718-04-01674-6/S0025-5718-04-01674-6.pdf">Five consecutive positive odd numbers, none of which can be expressed as a sum of two prime powers</a>, Mathematics of Computation 74 (2005), pp. 1025-1031.
%t A071331 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 *)
%t A071331 Join[{1},Select[Range[4,2300],Count[IntegerPartitions[#,{2}],_?( AllTrue[ #,PrimePowerQ]&)]==0&]] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale_, May 28 2021 *)
%o A071331 (PARI) isprimepower(n)=ispower(n,,&n);isprime(n)||n==1;
%o A071331 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)
%o A071331 \\ _Charles R Greathouse IV_, Jul 06 2011
%o A071331 (Haskell)
%o A071331 a071331 n = a071331_list !! (n-1)
%o A071331 a071331_list = filter ((== 0) . a071330) [1..]
%o A071331 -- _Reinhard Zumkeller_, Jan 11 2013
%Y A071331 A071330(a(n))=0. Cf. A000961, A109829, A014092.
%K A071331 nonn,nice
%O A071331 1,2
%A A071331 _Reinhard Zumkeller_, May 19 2002