A006285 -id:A006285 - cp's OEIS frontend

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 3, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 1, 2, 0, 1, 1, 4, 2, 2, 2, 1, 3, 2, 2, 3, 1, 2, 4, 4, 2, 2, 1, 2, 2, 4, 2, 3, 1, 3, 2, 4, 2, 2, 2, 3, 4, 2, 1, 2, 1, 2, 3, 3, 1, 2, 3, 3, 4, 4, 2, 2, 2, 2, 1, 5, 1, 4, 2, 3, 3, 2, 1, 5, 2, 1, 4, 4, 3, 2, 1, 2, 4, 3, 2, 3, 2, 2, 4, 2, 2, 2, 2, 3, 2, 6, 2, 4, 2, 2, 4, 5, 2, 3, 1, 3, 3, 5, 2, 3, 1, 2, 4, 4, 3, 3, 2, 1, 6

Offset: 1

Eric Chen, May 17 2015

In this sequence, "perfect power" does not include 0 or 1, "prime" does not include 1. Both "perfect power" and "prime" must be positive.
In the past, I conjectured that a(n) > 0 for all n>24, but this is not true. My PARI program found that a(1549) = 0.
I also asked which a(n) are 1. For example, 331 is a de Polignac number (A006285), so it cannot be written as 2^n+p with p prime, and 331-6^n must divisible by 5, 331-10^n must divisible by 3, ..., 331-18^2 = 331-324 = 7 is prime (and it is the only prime of the form 331-m^n, with m, n natural numbers, m>1, n>1), so a(331) = 1. Similarly, a(3319) = 1. Conjecture: a(n) > 1 for all n > 3319.
This conjecture is not true: a(1771561) = 0. (See A119748)
Another conjecture: For every number m>=0, there is a number k such that a(n)>=m for all n>=k.
Another conjecture: Except for k=2, first occurrence of k must be earlier then first occurrence of k+1.
For n such that a(n) = 0, see A119748.
For n such that a(n) = 1, see the following a-file of this sequence.

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 3000 terms from Chen)
Eric Chen, The unique way to write n as a sum of a perfect power (>1) and a prime for those n such a(n)=1

Cf. A196228, A119748, A109925, A118954, A064272, A064233, A002471, A014090.

nn = 128; pwrs = Flatten[Table[Range[2, Floor[nn^(1/ex)]]^ex, {ex, 2, Floor[Log[2, nn]]}]]; pp = Prime[Range[PrimePi[nn]]]; t = Table[0, {nn}]; Do[ t[[i[[1]]]] = i[[2]], {i, Tally[Sort[Select[Flatten[Outer[Plus, pwrs, pp]], # <= nn &]]]}]; t

a(n) = sum(k=1, n-1, ispower(k) && isprime(n-k))

a(n)=sum(e=2,log(n)\log(2),sum(b=2,sqrtnint(n,e),isprime(n-b^e)&&!ispower(b))) \\ Charles R Greathouse IV, May 28 2015

A270446 Positive even numbers which are neither of the form p + 2^m + 1 nor of the form p + 2^m - 1 with p prime.

Original entry on oeis.org

906, 3342, 3432, 4152, 4812, 4842, 5730, 7388, 7812, 8922, 10236, 10512, 11082, 11436, 12372, 12732, 13092, 14022, 14142, 14382, 14532, 15042, 15120, 16026, 16866, 17370, 18210, 18612, 18896, 18898, 20142, 20322, 20382, 20652, 21672, 24132, 24432, 24462

Offset: 1

Arkadiusz Wesolowski, Mar 17 2016

nonn

Numbers whose distance to both nearest neighbor de Polignac numbers is 1.

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A006285.

lst:=[]; for n in [2..24462 by 2] do t:=Floor(Log(2, n)); c:=0; m:=0; while m le t do a:=n-2^m; if IsPrime(a+1) or IsPrime(a-1) then break; end if; c+:=1; m+:=1; end while; if c eq t+1 then Append(~lst, n); end if; end for; lst;

filter:= proc(n) local m;
   for m from 1 while n - 2^m > 0 do
     if isprime(n - 2^m + 1) or isprime(n - 2^m-1) then return false fi
   od;
   true
end proc:
select(filter, [seq(i,i=4..30000,2)]); # Robert Israel, Mar 22 2016

A276458 Smallest odd number not of the form p + 2^k with p prime and k >= 0 that is divisible by the n-th prime.

Original entry on oeis.org

1719, 905, 959, 1199, 1807, 1207, 2983, 1541, 2465, 1271, 5143, 1271, 2279, 1927, 2279, 1829, 5917, 1541, 1207, 2263, 3239, 7387, 4717, 1649, 6161, 4841, 7169, 1199, 1243, 127, 10873, 959, 1529, 149, 11023, 2669, 12877, 2171, 1211, 1969, 905, 1719, 7913, 7289

Offset: 2

Arkadiusz Wesolowski, Sep 03 2016

nonn

a(n) <= A213529(n).

			a(3) = 905 because it is the smallest de Polignac number (A006285) divisible by the third prime.

Robert Israel, Table of n, a(n) for n = 2..3000

Cf. A006285, A098237, A213529.

lst:=[]; for r in [2..45] do p:=NthPrime(r); n:=-p; f:=0; while IsZero(f) do n:=n+2*p; k:=-1; repeat k+:=1; a:=n-2^k; until a lt 1 or IsPrime(a); if a lt 1 then Append(~lst, n); f:=1; end if; end while; end for; lst;

N:= 10^5: # to use de Polignac numbers <= N
P:= select(isprime,{2,seq(i,i=3..N,2)}):
dP:= {seq(i,i=1..N,2)}:
for k from 0 to ilog2(N) do
  dP:= dP minus map(`+`,P,2^k)
od:
for m from 2 do
   R:= ListTools:-SelectFirst(1, t -> t mod P[m] = 0, dP);
   if R = {} then break fi;
   A[m]:= R[1];
od:
seq(A[i],i=2..m-1); # Robert Israel, Sep 06 2016

A276495 Odd numbers not of the form p + 2^m with p prime and m >= 0 for which the smallest k in A067760 such that n + 2^k is prime increases.

Original entry on oeis.org

1, 127, 251, 1657, 1777, 1973, 3181, 21893, 31951, 50839, 67607, 138977

Offset: 1

Arkadiusz Wesolowski, Sep 05 2016

There exist de Polignac numbers n such that for all k >= 1 the numbers n + 2^k are composite. It is conjectured that 30666137 is the smallest such number.

a(13) >= 453143.

Cf. A006285, A067760, A263644.

A276496 gives the record values.

lst:=[]; c:=0; for n in [1..31951 by 2] do m:=-1; repeat m+:=1; a:=n-2^m; until a lt 1 or IsPrime(a); if a lt 1 then k:=0; repeat k+:=1; b:=n+2^k; until IsPrime(b); if k gt c then Append(~lst, n); c:=k; end if; end if; end for; lst;

A276567 Odd squares not of the form p + 2^k with p prime.

Original entry on oeis.org

1, 40401, 62001, 96721, 121801, 192721, 326041, 410881, 555025, 660969, 683929, 772641, 786769, 822649, 1343281, 1390041, 1530169, 1739761, 1885129, 1923769, 1962801, 2283121, 2544025, 2913849, 3207681, 3214849, 3352561, 3396649, 3613801, 3775249, 3853369, 4060225

Offset: 1

Arkadiusz Wesolowski, Sep 06 2016

nonn

The sequence contains also Sierpiński numbers (i.e., 4521731193704761, 60428287050225649).

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A006285, A016754.

lst:=[]; for s in [1..2015 by 2] do n:=s^2; x:=0; repeat x+:=1; a:=n-2^x; until a lt 1 or IsPrime(a); if a lt 1 then Append(~lst, n); end if; end for; lst;

filter:= proc(n) local k;
   for k from 0 to ilog2(n) do
     if isprime(n - 2^k) then return false fi
   od:
   true
end proc:
select(filter, [seq((2*i+1)^2, i=0..10^4)]); # Robert Israel, Sep 07 2016

filterQ[n_] := Module[{k}, For[k = 0, k <= Log[2, n], k++, If[PrimeQ[n - 2^k], Return[False]]]; True];
Select[Table[(2i+1)^2, {i, 0, 10^4}], filterQ] (* Jean-François Alcover, Oct 06 2020, after Maple *)

A006285 INTERSECT A016754.

A283622 a(n) = smallest k > n + 1 not of the form p + n^x with p prime, where gcd(k, n) = 1 and gcd(k-1, n-1) = 1.

Original entry on oeis.org

127, 328, 149, 26, 127, 254, 17, 34, 59, 50, 37, 134, 23, 136, 65, 26, 43, 96, 29, 142, 47, 50, 49, 116, 35, 52, 53, 56, 79, 122, 41, 58, 59, 92, 157, 86, 47, 64, 89, 50, 67, 186, 53, 94, 95, 56, 73, 134, 59, 100, 77, 78, 79, 146, 65, 82, 83, 86, 109, 204, 71

Offset: 2

Arkadiusz Wesolowski, Mar 12 2017

nonn

Cf. A006285, A282430.

lst:=[]; for n in [2..62] do k:=n+2; t:=0; while t eq 0 do if GCD(k, n) eq 1 and GCD(k-1, n-1) eq 1 then x:=-1; repeat x+:=1; p:=k-n^x; until p lt 2 or IsPrime(p); if p lt 2 then Append(~lst, k); t:=1; end if; end if; k+:=1; end while; end for; lst;

A259534 a(n) = -1 + 2 * product_{i=0..n} A093179(i), where A093179(i) is the smallest prime factor of 2^(2^i) + 1.

Original entry on oeis.org

5, 29, 509, 131069, 8589934589, 5506148072189, 1509659159988837629, 90050548615896750734368618889875709, 111565998552535226317138856424609779410946920431869, 270528914968139650436266764640655805238384653911572627709

Offset: 0

Arkadiusz Wesolowski, Jul 02 2015

nonn

For any k >= 1, numbers of the form (k*a(n) + k - 1)*2^m - 1 are composite for all m < 2^(n+1).

Many terms are in common with A006285 (de Polignac numbers).

Cf. A006285, A093179.

a(n) = - 1 + 2 * prod(k=0, n, factor(2^(2^k)+1)[1,1]); \\ Michel Marcus, Jul 04 2015

A355885 a(n) is the smallest odd k such that k + 2^m is a de Polignac number for m = 1..n.

Original entry on oeis.org

125, 903, 7385, 87453, 957453, 6777393, 21487809, 27035379, 1379985537, 5458529139, 15399643917, 32702289081

Offset: 1

Thomas Ordowski, Jul 20 2022

All terms of this sequence are composite numbers.
Note that all positive values of a(n) + 2^i - 2^j are composite from i = 1 to n.
Conjecture: this sequence is infinite and bounded, namely a(n) = K for all n >= N.
If so, then K - 2^j is a Sierpiński number for every 1 < 2^j < K, by the dual Sierpiński conjecture. Note that each positive value of K + 2^i - 2^j is composite for every i > 0.
The number K can be a (partial) solution to the open problem: are there odd (composite) numbers k such that both |(k -+ 2^m)*2^n +- 1| are composite for every pair of positive integers m,n?
By the dual Sierpiński and Riesel conjectures, these are odd numbers k such that both ||k -+ 2^m| +- 2^n| are composite for m, n > 0.
The conditional theorem: by the dual Sierpiński conjecture and by the dual Riesel conjecture; if p is an odd prime and m is a positive integer, then there exist two numbers n such that both |(p -+ 2^m)*2^n +- 1| are prime.
So if such numbers k exist, they must be composite.

			a(3) = 7385, because 7385 is the smallest number k such that k+2^1, k+2^2, k+2^3 are de Polignac numbers 7387, 7389, 7393.

Cf. A006285, A156695, A337487.

depolQ[n_] := OddQ[n] && Module[{m = 2}, While[m < n && CompositeQ[n - m], m *= 2]; m > n]; a[n_] := Module[{k = 1}, While[AnyTrue[Range[1, n], !depolQ[k + 2^#] &], k++]; k]; Array[a, 5] (* Amiram Eldar, Jul 20 2022 *)

More terms from Amiram Eldar, Jul 20 2022

cp's OEIS Frontend

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A270446 Positive even numbers which are neither of the form p + 2^m + 1 nor of the form p + 2^m - 1 with p prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

A276458 Smallest odd number not of the form p + 2^k with p prime and k >= 0 that is divisible by the n-th prime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

A276495 Odd numbers not of the form p + 2^m with p prime and m >= 0 for which the smallest k in A067760 such that n + 2^k is prime increases.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

A276567 Odd squares not of the form p + 2^k with p prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A283622 a(n) = smallest k > n + 1 not of the form p + n^x with p prime, where gcd(k, n) = 1 and gcd(k-1, n-1) = 1.

Views

Author

Keywords

Crossrefs

Programs

Magma

A259534 a(n) = -1 + 2 * product_{i=0..n} A093179(i), where A093179(i) is the smallest prime factor of 2^(2^i) + 1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A355885 a(n) is the smallest odd k such that k + 2^m is a de Polignac number for m = 1..n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions