A006549 - OEIS

%I M0582 #57 Dec 15 2021 02:23:16

%S 1,2,3,4,7,8,16,31,127,256,8191,65536,131071,524287,2147483647,

%T 2305843009213693951,618970019642690137449562111,

%U 162259276829213363391578010288127,170141183460469231731687303715884105727

%N Numbers k such that k and k+1 are prime powers.

%C Numbers k such that k + (0, 1) is a prime power pair.

%C Consecutive prime powers.

%C k + (0, 2m), m >= 1, being an admissible pattern for prime pairs, since (0, 2m) == (0, 0) (mod 2), has high density.

%C k + (0, 2m-1), m >= 1, being a non-admissible pattern for prime pairs, since (0, 2m-1) == (0, 1) (mod 2), has low density [the only possible pairs are (2^a - 2m-1, 2^a) or (2^a, 2^a + 2m-1), a >= 0].

%C Numbers k such that k and k+1 are primes would give only 2, for the prime pair (2, 3).

%C This sequence corresponds to the least member of each one of the following prime power pairs, ordered by increasing value of least member: (1, 2), (2^3, 3^2), (Fermat primes - 1, Fermat primes), (Mersenne primes, Mersenne primes + 1).

%C It is not known whether this sequence is infinite, but is conjectured to be since:

%C (*) 2^3, 3^2 are the only consecutive prime powers with exponents >= 2

%C (as a consequence of Mihailescu's theorem -- Mihailescu proved Catalan's conjecture in 2002);

%C (*) Only the first 5 Fermat numbers f_0 to f_4 are known to be prime

%C (it is conjectured that there might be no others, f_5 to f_32 are all composite);

%C (*) It has been conjectured that there exist an infinite number of Mersenne primes.

%C Numbers k such that A003418(k) appears only once in the sequence A003418. This may suggest that k is also characterized by the pairs formed by a 2 whose direct neighbor is a prime number in the sequence A014963. - _Eric Desbiaux_, Feb 11 2015

%C The power graph and enhanced power graph of the groups PGL(2,q) have the same clique number iff q>1 is a term of this sequence (Peter Cameron's link). - _Bernard Schott_, Dec 14 2021

%D R. K. Guy, Unsolved Problems in Number Theory, D9.

%D P. Ribenboim, 13 Lect. on Fermat's Last Theorem, p. 236.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D David W. Wilson and Eric Rains (rains(AT)caltech.edu) found a simple proof that in this case of Catalan's conjecture either n or n+1 must be a power of 2 and the other number must be a prime, except for n=8. Using this the sequence is easy to extend.

%H Daniel Forgues, <a href="/A006549/b006549.txt">Table of n, a(n) for n = 1..25</a>

%H Peter Cameron, <a href="https://cameroncounts.wordpress.com/2021/11/08/graphs-on-groups-9/">Graphs on groups, 9</a>, Peter Cameron's blog.

%H Wacław Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm6/cm6128.pdf">Sur une question concernant le nombre de diviseurs premiers d'un nombre naturel</a>, Colloquium Mathematicum 6 (1958), 209-210.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CatalansConjecture.html">Catalan's Conjecture</a>.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CliqueNumber.html">Clique Number</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/FermatPrime.html">Fermat Prime</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MersennePrime.html">Mersenne Prime</a>.

%t Do[ a = Length[ FactorInteger[ 2^n - 1 ] ]; b = Length[ FactorInteger[ 2^n ] ]; c = Length[ FactorInteger[ 2^n + 1 ] ]; If[ a == b, Print[ 2^n - 1 ] ]; If[ b == c, Print[ 2^n ] ], {n, 0, 127} ]

%t Join[{1},SequencePosition[Boole[PrimePowerQ[Range[600000]]],{1,1}][[All,1]]] (* Requires Mathematica version 10 or later *) (* Generates the first 14 terms of the sequence. Increase Range constant to generate more. *) (* _Harvey P. Dale_, Apr 12 2020 *)

%o (Haskell)

%o a006549 n = a006549_list !! (n-1)

%o a006549_list = [1,2,3,4,7,8] ++ f (drop 4 a000040_list) where

%o    f (p:ps) | a010055 (p - 1) == 1 = (p - 1) : f ps

%o             | a010055 (p + 1) == 1 = p : f ps

%o             | otherwise            = f ps

%o -- _Reinhard Zumkeller_, Jan 03 2013

%o (PARI) is(n)=if(n<5,return(n>0)); isprimepower(n) && isprimepower(n+1) \\ _Charles R Greathouse IV_, Apr 24 2015

%Y Cf. A000961, A000040, A010055.

%Y Cf. A019434 Fermat primes: primes of form 2^(2^n) + 1, n >= 0.

%Y Cf. A000668 Mersenne primes (of form 2^p - 1 where p is a prime).

%Y Cf. A120431 Numbers n such that n and n+2 are prime powers.

%Y Cf. A164571 Numbers n such that n and n+3 are prime powers.

%Y Cf. A164572 Numbers n such that n and n+4 are prime powers.

%Y Cf. A164573 Numbers n such that n and n+5 are prime powers.

%Y Cf. A164574 Numbers n such that n and n+6 are prime powers.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_

%E Additional comments from _Daniel Forgues_, Aug 17 2009