A067760 -id:A067760 - cp's OEIS frontend

A139803 A033875(n) + 2^a(n) = A033875(n+1).

0, 1, 1, 2, 1, 2, 1, 2, 3, 4, 5, 2, 7, 4, 1, 2, 3, 4, 9, 2, 955, 468

Offset: 1

Johan Särnbratt, May 22 2008

a(23) > 10^4. - Zak Seidov, Jan 24 2017

a(23) > 30000 (if it exists). - Pontus von Brömssen, Jan 08 2023

			a(10) = 4 because A033875(10) = 31, 31 + 2^4 = 47, which is prime.

Skipping from prime to prime by least powers of 2: A033875.

Cf. A059662, A067760.

p = 2; n = 0; While[true, x = 0; While[ ! PrimeQ[p + 2^x], x++ ]; p = p + 2^x; Print[x]; n++ ]

a(n) = A067760((A033875(n)-1)/2) for n >= 2. - Pontus von Brömssen, Jan 08 2023

A252168 Smallest k > 0 such that |(2n-1) - 2^k| is prime, or -1 if no such k exists.

Original entry on oeis.org

2, 3, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 4, 1, 1, 2, 3, 1, 2, 1, 1, 2, 1, 2, 4, 1, 2, 4, 1, 1, 2, 3, 1, 2, 1, 1, 2, 3, 1, 2, 1, 2, 4, 1, 2, 4, 3, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 4, 3, 4, 4, 47, 1, 2, 1, 2, 6, 1, 1, 2, 3, 3, 8, 1, 1, 2, 3, 1, 2, 5, 1, 2, 1, 2, 4

Offset: 1

Eric Chen, Dec 14 2014

It is known that a(254602) = -1, because |509203-2^k| is always divisible by 3, 5, 7, 13, 17, or 241. a(1147) is the first unknown term.
a((A101036(n)+1)/2) = -1, so there are infinitely many n such that a(n) = -1.
a((A133122(n)+1)/2) = A096502((A133122(n)-1)/2).

			a(12) = 2 because 2*12-1 = 23 and that 23-2^1 = 21 is not prime but 23-2^2 = 19 is.
a(69) = 6 because 2*69-1 = 137, |137-2^k| is composite for k = 1, 2, 3, 4, 5 and prime for k = 6.
Even the smallest k can be also very large. For example, a(169) = 791.
a(1147) > 65536.

Jinyuan Wang, Table of n, a(n) for n = 1..1146

Cf. A006285, A096502, A133122, A188903.

Cf. A046067, A046069, A067760.

Table[k = 1; While[!PrimeQ[Abs[(2*n-1) - 2^k]], k++]; k, {n, 1, 1000}]

A252168(n)={ my(k=1); n=2*n-1; while(!ispseudoprime(abs(n-2^k)), k++); k }

a(19) corrected by Jinyuan Wang, Mar 25 2023

A033919 Odd k for which k+2^m is composite for all m < k.

Original entry on oeis.org

773, 2131, 2491, 4471, 5101, 7013, 8543, 10711, 14717, 17659, 19081, 19249, 20273, 21661, 22193, 28433, 35461, 37967, 39079, 40291, 41693, 48527, 60443, 60451, 60947, 64133, 75353, 78557

Offset: 1

Dan Hoey

nonn

Related to the Sierpiński number problem.

In an archived website, Payam Samidoost gives these numbers and other results about the dual Sierpiński problem. It is conjectured that, for each of these k<78557, there is an m such that k+2^m is prime. Then a covering argument would show that 78557 is the least odd number such that 78557+2^m is composite for all m. The impediment in the "dual" problem is that it is currently very difficult to prove the primality of large numbers of the form k+2^m. It is much easier to prove the Proth primes of the form k*2^m+1 which occur in the usual Sierpiński problem. According to the distributed search project "Five or Bust", 40291 is the only value of k < 78557 for which there is currently no m known making k + 2^m a prime or probable prime. - T. D. Noe, Jun 14 2007 and Phil Moore (moorep(AT)lanecc.edu), Dec 14 2009

Mersenneforum, Five or Bust
Payam Samidoost, The dual Sierpinski problem search (Archive of the site at the Wayback Machine, original link is dead)
Eric Weisstein's World of Mathematics, Sierpiński Number of the Second Kind.

Cf. A067760, A076336.

t={}; Do[k=1; While[kT. D. Noe, Jun 14 2007 *)

More terms from David W. Wilson
More terms from T. D. Noe, Jun 14 2007
Out-of-date information from Payam Samidoost's website corrected, using the current status on the dual Sierpiński problem from "Five or Bust," by Phil Moore (moorep(AT)lanecc.edu), Dec 14 2009
Broken link to Payam Samidoost's website replaced with link to archive in the Wayback Machine by Felix Fröhlich, Jul 11 2014
26213 removed from sequence following an email message from Maximilian Pacher, who reports that 2^1271+26213 is prime. - N. J. A. Sloane, Dec 31 2015

A276496 a(n) is the least positive k such that A276495(n) + 2^k is prime.

Original entry on oeis.org

1, 2, 5, 6, 10, 11, 60, 75, 1404, 1974, 16389, 37105

Offset: 1

Arkadiusz Wesolowski, Sep 05 2016

If A276495(13) = 453143, then a(13) > 10^5.

Cf. A067760, A276495.

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, k); c:=k; end if; end if; end for; lst;

Typo in name corrected by Rémy Sigrist, Sep 12 2016

A282194 a(n) = smallest positive k such that 2*n + 2^k + 1 is composite.

Original entry on oeis.org

3, 5, 2, 1, 4, 2, 1, 7, 2, 1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 4, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 3, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 4, 2, 1, 4, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 3, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 4, 2, 1, 3, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1

Offset: 0

Altug Alkan, Feb 15 2017

nonn

Least k such that a(k) = n are 3, 2, 0, 4, 1, 112, 7, 32917, 802, 9712, 1198673602 for the initial terms.

			a(1) = 5 because 3 + 2^k is prime for 0 < k < 5 and 3 + 2^5 = 35 is composite.

Altug Alkan, Table of n, a(n) for n = 0..10000

Cf. A067076, A067760, A153238, A282026.

spk[n_]:=Module[{k=1},While[!CompositeQ[2n+2^k+1],k++];k]; Array[spk,110,0] (* Harvey P. Dale, Apr 26 2017 *)

a(n) = my(k=1); while(isprime(2*n+2^k+1), k++); k;

A335653 Smallest prime whose binary expansion has Hamming distance 1 from 2n+1, or 0 if no such prime exists.

Original entry on oeis.org

3, 2, 7, 3, 11, 3, 5, 7, 19, 3, 5, 7, 17, 11, 13, 23, 37, 3, 5, 7, 43, 11, 13, 43, 17, 19, 37, 23, 41, 43, 29, 31, 67, 3, 5, 7, 89, 11, 13, 71, 17, 19, 1109, 23, 73, 83, 29, 31, 101, 67, 37, 71, 41, 43, 101, 47, 97, 83, 53, 103, 89, 59, 61, 383, 131, 3, 5, 7, 139, 11, 13, 139, 17, 19, 151, 23

Offset: 0

Ross Dempsey, Jun 15 2020

If 2n+1 is a dual Sierpiński number, and if 2n+1 cannot be made prime by flipping any of the ones in its binary representation to zero, then a(n) = 0.
2131099 is Sierpiński, and it is conjectured that the Sierpiński numbers are the same as the dual Sierpiński numbers. Furthermore 2131099 is the smallest Sierpiński number whose binary representation has the property stated above. If the dual Sierpiński conjecture holds, and if A076336 is complete up to 2131099, then a(1065549) = 0 and this is likely the first 0 in the sequence.
From Robert Israel, Jul 08 2020: (Start)
Every prime is in the sequence.
  Proof: Since 2 = a(1), we may assume prime p is odd. Take k so 2^k > p, and consider 2n+1 = p + 2^k. Then p has Hamming distance 1 from 2n+1. On the other hand, if q < p is prime, then q + 2^j < p + 2^k if j <= k while q + 2^j >= q + 2*2^k > p + 2^k if j > k, so q can't be at Hamming distance 1 from 2n+1. Thus p = a(n). (End)

			For n = 4, 2n+1 = 1001_2, and the smallest prime with Hamming distance 1 is 1011_2 = 11.

Robert Israel, Table of n, a(n) for n = 0..2234
MathOverflow, Hamming Distance to Primes

Cf. A067760, A076336.

f:= proc(n) local L, nL, k, v;
    L:= convert(n, base, 2);
    nL:= nops(L);
    for k from nL to 1 by -1 do
      if L[k] = 1 then
        v:= n - 2^(k-1);
        if isprime(v) then return v fi;
      fi
    od;
    for k from 1 to nL do
      if L[k] = 0 then
        v:= n + 2^(k-1);
        if isprime(v) then return v fi;
      fi
    od;
    for k from nL+1 do
      v:= n+2^(k-1);
      if isprime(v) then return v fi;
    od
end proc:
map(f, [seq(i, i=1..200, 2)]); # Robert Israel, Jun 15 2020

a[n_Integer] := a[IntegerDigits[2 n + 1, 2]];
a[bin_List] := Module[{flips, primes},
   flips =
    Sort[FromDigits[bin,
       2] + (1 - 2 bin) Power[2, Length[bin] - Range[Length[bin]]]];
   primes = Select[flips, PrimeQ];
   If[Length[primes] >= 1, First[primes],
    a[FromDigits[bin, 2], Length[bin]]]
   ];
a[n_Integer, k_Integer] :=
  Module[{test = n + Power[2, k]}, test /; PrimeQ[test]];
a[n_Integer, k_Integer] := a[n, k + 1];
Table[a[n],{n,0,50}]

a(n) = my(p=2); while(norml2(binary(bitxor(p, 2*n+1))) != 1, p = nextprime(p+1)); p; \\ Michel Marcus, Jun 16 2020

a((p+2^k-1)/2) = p if p is an odd prime and 2^k > p-3. - Robert Israel, Jun 16 2020

A373210 Least k such that the smallest prime >= 2^k is 2^k + 2*n + 1, or -1 if no such k exists.

Original entry on oeis.org

0, 3, 5, 10, 9, 29, 64, 22, 13, 162, 19, 39, 34, 14, 17, 36, 60, 25, 74, 87, 121, 24, 151, 209, 170, 111, 35, 50, 188, 45, 96, 247, 193, 124, 49, 115, 258, 83, 173, 254, 56, 167, 136, 138, 279, 148, 314, 153, 158, 106, 199, 434, 93, 161, 6954, 104, 719, 240, 164

Offset: 0

Jianing Song, May 28 2024

sign

a(n) = -1 if 2*n + 1 is a Sierpiński number (for example when 2*n + 1 = 78557); cf. A076336. See also A067760.
Conjecture: a(n) != -1 if 2*n + 1 is not a Sierpiński number. In other words, if 2*n + 1 is not a Sierpiński number, then there exists some k >= 1 such that 2^k + 1, 2^k + 3, ..., 2^k + 2*n - 1 are all composite while 2^k + 2*n + 1 is prime.
a(54), a(75), a(83), a(128), a(159), a(176), ... > 5000 (if not equal to -1), which means that 109, 151, 167, 257, 319, 353, ... do not present among the first 5000 terms of A092131.
a(75) = 5880, a(83) = 5513. - Michael S. Branicky, May 28 2024
a(128) > 7000. - Michael S. Branicky, May 30 2024

			a(6) = 64, because the smallest prime >= 2^k is not 2^k + 13 for 0 <= k <= 63, while the smallest prime >= 2^64 is 2^64 + 13.

Michael S. Branicky, Table of n, a(n) for n = 0..127

Cf. A067760, A076336, A092131.

A373210_first_N_terms(N) = my(v = vector(N+1, i, -1), dist); v[1] = 0; for(i=2, oo, dist = nextprime(2^i) - 2^i; if(dist <= 2*N+1 && v[(dist+1)/2] == -1, v[(dist+1)/2] = i); if(vecmin(v) > -1, return(v))) \\ Warning: ignoring Sierpinski numbers

a(54) and beyond from Michael S. Branicky, May 29 2024

cp's OEIS Frontend

A139803 A033875(n) + 2^a(n) = A033875(n+1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A252168 Smallest k > 0 such that |(2n-1) - 2^k| is prime, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A033919 Odd k for which k+2^m is composite for all m < k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A276496 a(n) is the least positive k such that A276495(n) + 2^k is prime.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Extensions

A282194 a(n) = smallest positive k such that 2*n + 2^k + 1 is composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A335653 Smallest prime whose binary expansion has Hamming distance 1 from 2n+1, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A373210 Least k such that the smallest prime >= 2^k is 2^k + 2*n + 1, or -1 if no such k exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions