A039669 -id:A039669 - cp's OEIS frontend

A089654 Table T(n,k), read by rows, related to a conjecture of P. Erdos (see A039669).

1, 3, 1, 5, 3, 7, 5, 1, 9, 7, 3, 11, 9, 5, 13, 11, 7, 15, 13, 9, 1, 17, 15, 11, 3, 19, 17, 13, 5, 21, 19, 15, 7, 23, 21, 17, 9, 25, 23, 19, 11, 27, 25, 21, 13, 29, 27, 23, 15, 31, 29, 25, 17, 1, 33, 31, 27, 19, 3, 35, 33, 29, 21, 5

Offset: 1

Philippe Deléham, Jan 04 2004

row n=1 : 1
row n=2 : 3, 1
row n=3 : 5, 3
row n=4 : 7, 5, 1
row n=5 : 9, 7, 3
row n=6 : 11, 9, 5
row n=7 : 13, 11, 7
row n=8 : 15, 13, 9, 1
row n=9 : 17, 15, 11, 3
P. Erdos conjectures that T(n,k) are all primes for n = 3, 7, 10, 22, 37, 52 and these are the only values of n with property . The conjecture has been verified for n up to 2^77. example : n=10; 19, 17, 13, 5 are all primes.

P. Erdős, On integers of the form 2^k + p and some related questions, Summa Bras. Math., 2 (1950), 113-123.

Cf. A039669.

T(n, k) = 2*n+1-2^k, if T(n, k)>0.

A109925 Number of primes of the form n - 2^k.

Original entry on oeis.org

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

Offset: 1

Amarnath Murthy, Jul 17 2005

Erdős conjectures that the numbers in A039669 are the only n for which n-2^r is prime for all 2^rT. D. Noe and Robert G. Wilson v, Jul 19 2005

a(A006285(n)) = 0. - Reinhard Zumkeller, May 27 2015

			a(21) = 4, 21-2 =19, 21-4 = 17, 21-8 = 13, 21-16 = 5, four primes.
127 is the smallest odd number > 1 such that a(n) = 0: A006285(2) = 127. - _Reinhard Zumkeller_, May 27 2015

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A039669, A109926, A175956, A156695.
Cf. A000079, A000040, A010051, A006285.
Cf. A118954, A118955, A118952, A078687.

a109925 n = sum $ map (a010051' . (n -)) $ takeWhile (< n)  a000079_list
-- Reinhard Zumkeller, May 27 2015

a109925:=function(n); count:=0; e:=1; while e le n do if IsPrime(n-e) then count+:=1; end if; e*:=2; end while; return count; end function; [ a109925(n): n in [1..105] ]; // Klaus Brockhaus, Oct 30 2010

A109925 := proc(n)
    a := 0 ;
    for k from 0 do
        if n-2^k < 2 then
            return a ;
        elif isprime(n-2^k) then
            a := a+1 ;
        end if;
    end do:
end proc:
seq(A109925(n),n=1..80) ; # R. J. Mathar, Mar 07 2022

Table[cnt=0; r=1; While[rRobert G. Wilson v, Jul 21 2005 *)
Table[Count[n - 2^Range[0, Floor[Log2[n]]], ?PrimeQ], {n, 110}] (* _Harvey P. Dale, Oct 21 2024 *)

a(n)=sum(k=0,log(n)\log(2),isprime(n-2^k)) \\ Charles R Greathouse IV, Feb 19 2013

from sympy import isprime
def A109925(n): return sum(1 for i in range(n.bit_length()) if isprime(n-(1<Chai Wah Wu, Nov 29 2023

a(A118954(n))=0, a(A118955(n))>0; A118952(n)<=a(n); A078687(n)=a(A000040(n)). - Reinhard Zumkeller, May 07 2006

G.f.: ( Sum_{i>=0} x^(2^i) ) * ( Sum_{j>=1} x^prime(j) ). - Ilya Gutkovskiy, Feb 10 2022

Corrected and extended by T. D. Noe and Robert G. Wilson v, Jul 19 2005

A067526 Numbers n such that n - 2^k is a prime or 1 for all k satisfying 0 < k, 2^k < n.

Original entry on oeis.org

3, 4, 5, 7, 9, 15, 21, 45, 75, 105

Offset: 1

Amarnath Murthy, Feb 17 2002

Is the sequence finite?

Next term, if it exists, exceeds 5*10^9. - Sean A. Irvine, Dec 18 2023

			45 belongs to this sequence as 45-2, 45-4, 45-8, 45-16, 45-32, i.e., 43, 41, 37, 29 and 13 are all primes.

Cf. A039669 (n-2^k is prime).

f[n_] := Block[{k = 1}, While[2^k < n, k++ ]; k--; k]; Do[ a = Table[n - 2^k, {k, 1, f[n]} ]; If[ a[[ -1]] == 1, a = Drop[a, -1]]; If[ Union[ PrimeQ[a]] == {True}, Print[n]], {n, 5, 10^7, 2} ]

from sympy import isprime
def ok(n):
  k, pow2 = 1, 2
  while pow2 < n - 1:
    if not isprime(n-pow2): return False
    pow2 *= 2
  return (2 < n)
print([m for m in range(1, 200) if ok(m)]) # Michael S. Branicky, Mar 04 2021

Edited by Robert G. Wilson v, Feb 18 2002

A067528 Numbers n such that n - 4^k is a prime or 1 for all k > 0 and n > 4^k.

Original entry on oeis.org

5, 6, 7, 9, 11, 15, 17, 21, 23, 27, 33, 35, 45, 47, 57, 63, 75, 77, 83, 87, 105, 117, 143, 153, 167, 195, 215, 227, 243, 245, 255, 287, 297, 413, 437, 447, 483, 495, 507, 525, 573, 635, 657, 677, 755, 825, 1113, 1133, 1295, 1487, 1515, 1547, 1617, 1623, 2015

Offset: 1

Amarnath Murthy, Feb 17 2002

nonn

Is the sequence finite?
The last term appears to be 5833497. - T. D. Noe, Nov 23 2004
A less strict version of A039669, n - 2^k is prime for 0 < k < log_2 k. If a number is in that sequence, then obviously it is also in this sequence. As of this writing, 105 is believed to be the last term of that sequence. - Alonso del Arte, May 24 2017

			167 is a term as 167 - 4 = 163, 167 - 16 = 151, 167 - 64 = 103 are primes.

T. D. Noe, Table of n, a(n) for n=1..102 (no others < 2*10^9)

Cf. A067526.

filter:= proc(n) local k, t;
  for k from 1 do
    if 4^k >= n-1 then return true
    elif not isprime(n-4^k) then return false
    fi
  od
end proc:
select(filter, [$5..3000]); # Robert Israel, May 24 2017

A067528 = {}; Do[k = 1; While[p = n - 4^k; p > 0 && (p == 1 || PrimeQ[p]), k++]; If[p <= 0, AppendTo[A067528, n]], {n, 5, 10^7}]; A067528 (* T. D. Noe *)

More terms from Sascha Kurz, Mar 19 2002

A067527 n - 3^k is a prime for all k > 0 such that 3^k < n.

Original entry on oeis.org

5, 6, 8, 14, 16, 20, 22, 26, 32, 40, 46, 50, 56, 70, 110, 140, 260, 470, 1190, 1330

Offset: 1

Amarnath Murthy, Feb 17 2002

Is the sequence finite?

No other terms below 3^36. - Max Alekseyev, Dec 12 2011

			40 is a member as 40 - 3 = 37, 40 - 9 = 31, 40 - 27 = 13 are all primes.

Cf. A067526.

Cf. A039669 (n - 2^k is prime).

A067527 = {}; Do[k = 1; While[p = n - 3^k; p > 0 && PrimeQ[p], k++]; If[p <= 0, AppendTo[A067527, n]], {n, 4, 10000}]; A067527 (* T. D. Noe, Feb 20 2005 *)

More terms from Sascha Kurz, Mar 18 2002

Edited by Max Alekseyev, Dec 12 2011

A100349 Numbers n such that n-2^k is a prime or semiprime for all k > 0 with 2^k < n.

Original entry on oeis.org

4, 6, 7, 8, 11, 13, 15, 19, 21, 23, 25, 27, 37, 39, 41, 45, 51, 55, 57, 63, 69, 73, 75, 81, 87, 93, 99, 105, 111, 117, 123, 135, 147, 153, 159, 165, 171, 195, 201, 213, 219, 225, 231, 237, 243, 255, 267, 273, 285, 297, 315, 321, 363, 369, 399, 405, 411, 423, 435, 447

Offset: 1

T. D. Noe, Nov 18 2004

nonn

Is the sequence finite? If so, then A039669 is finite.

			27 is here because 27-2 is a semiprime and 27-4, 27-8 and 27-16 are primes.

T. D. Noe, Table of n < 2^31

Cf. A039669 (n such that n-2^k is prime), A100350 (primes p such that p-2^k is prime or semiprime), A100351 (n such that n-2^k is semiprime).

SemiPrimeQ[n_Integer] := If[Abs[n]<2, False, (2==Plus@@Transpose[FactorInteger[Abs[n]]][[2]])]; lst={}; Do[k=1; While[p=n-2^k; p>0 && (SemiPrimeQ[p] || PrimeQ[p]), k++ ]; If[p<=0, AppendTo[lst, n]], {n, 3, 1000}]; lst

A218044 Numbers of the form 2^k + prime, with k > 0.

Original entry on oeis.org

4, 5, 6, 7, 9, 10, 11, 13, 15, 17, 18, 19, 21, 23, 25, 27, 29, 31, 33, 34, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 66, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119

Offset: 1

Michel Marcus, Oct 19 2012

A039669 is included in this sequence.

			5 = 3 + 2 that is, a prime and a power of 2.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Yong-Gao Chena and Xue-Gong Sunb, On Romanoff's constant, Journal of Number Theory, Volume 106, Issue 2, June 2004, Pages 275-284.
Christian Elsholtz, Florian Luca, and Stefan Planitzer, Romanov type problems, The Ramanujan Journal 47.2 (2018): 267-289.
P. Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math. 2 (1950), pp. 113-123.
N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 57 (1934) 668-678.

Cf. A080340, A039669, A118955 (allows k=0).

q:= n-> ormap(isprime, [seq(n-2^k, k=1..ilog2(n))]):
select(q, [$0..200])[];  # Alois P. Heinz, Feb 14 2020

nn = 119; ps = Prime[Range[PrimePi[nn]]]; p2 = 2^Range[Log[2, nn]]; u = {}; Do[u = Union[u, ps + p2[[i]]], {i, Length[p2]}]; Select[u, # <= nn &] (* T. D. Noe, Oct 19 2012 *)

isok(n) = {forprime(p=2, n, my(d = n - p); if ((d==2) || (ispower(d,,&k) && (k==2)), return(1));); 0;} \\ Michel Marcus, Apr 18 2016

A100350 Primes p such that p-2^k is a prime or semiprime for all k > 0 with 2^k < p.

Original entry on oeis.org

7, 11, 13, 19, 23, 37, 41, 73

Offset: 1

T. D. Noe, Nov 18 2004

These are the primes in A100349. No others < 10^9; conjecture that this sequence is finite.

			37 is here because 37-2, 37-4, 37-16 are semiprimes and 37-8, 37-32 are primes.

Cf. A039669 (n such that n-2^k is prime), A100349 (n such that n-2^k is prime or semiprime), A100351 (n such that n-2^k is semiprime).

SemiPrimeQ[n_Integer] := If[Abs[n]<2, False, (2==Plus@@Transpose[FactorInteger[Abs[n]]][[2]])]; lst={}; Do[k=1; While[n=Prime[i]; p=n-2^k; p>0 && (SemiPrimeQ[p] || PrimeQ[p]), k++ ]; If[p<=0, AppendTo[lst, n]], {i, 2, 1000}]; lst

A100351 Numbers n such that n-2^k is a semiprime for all k > 0 with 2^k < n.

Original entry on oeis.org

8, 4311

Offset: 1

T. D. Noe, Nov 18 2004

A subset of A100349. No others < 10^9; conjecture that this sequence is finite.

Next term, if it exists, exceeds 5*10^10. [From Sean A. Irvine, Apr 13 2010]

			4311-2=31*139, 4311-4=59*73, 4311-8=13*331, 4311-16=5*859, 4311-32=11*389, 4311-64=31*137, 4311-128=47*89, 4311-256=5*811, 4311-512=29*131, 4311-1024=19*173, 4311-2048=31*73, 4311-4096=5*43

Cf. A039669 (n such that n-2^k is prime), A100349 (n such that n-2^k is prime or semiprime), A100350 (primes p such that p-2^k is prime or semiprime).

SemiPrimeQ[n_Integer] := If[Abs[n]<2, False, (2==Plus@@Transpose[FactorInteger[Abs[n]]][[2]])]; lst={}; Do[k=1; While[p=n-2^k; p>0 && SemiPrimeQ[p], k++ ]; If[p<=0, AppendTo[lst, n]], {n, 3, 1000000}]; lst

A067529 n - 5^k is a prime for all k > 0 and n > 5^k.

Original entry on oeis.org

7, 8, 10, 12, 16, 18, 22, 24, 28, 36, 42, 48, 66, 72, 78, 84, 108, 114, 132, 156, 162, 198, 204, 276, 282, 288, 318, 336, 492, 504, 546, 582, 612, 624, 666, 864, 882, 1044, 1134, 1218, 1242, 1326, 1452, 1998, 2136, 2472, 2922, 3234, 3948, 4032, 4572, 4914, 6342

Offset: 1

Amarnath Murthy, Feb 17 2002

Is the sequence finite?

The last term appears to be 7726572. - T. D. Noe, Nov 23 2004

			624 is a term as 624-5, 624-25,624-125 or 619,599 and 499 are primes.

Michel Marcus, Table of n, a(n) for n = 1..66
Walter E. Mientka and Roger C. Weitzenkamp, On f-plentiful numbers, Journal of Combinatorial Theory, Volume 7, Issue 4, December 1969, Pages 374-377

Cf. A067526, A067527, A067528.

Cf. A039669 (n-2^k is prime).

lst={}; Do[k=1; While[p=n-5^k; p>0 && PrimeQ[p], k++ ]; If[p<=0, AppendTo[lst, n]], {n, 6, 10^7}]; lst (T. D. Noe)

More terms from Sascha Kurz, Mar 19 2002

cp's OEIS Frontend

A089654 Table T(n,k), read by rows, related to a conjecture of P. Erdos (see A039669).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A109925 Number of primes of the form n - 2^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A067526 Numbers n such that n - 2^k is a prime or 1 for all k satisfying 0 < k, 2^k < n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A067528 Numbers n such that n - 4^k is a prime or 1 for all k > 0 and n > 4^k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A067527 n - 3^k is a prime for all k > 0 such that 3^k < n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A100349 Numbers n such that n-2^k is a prime or semiprime for all k > 0 with 2^k < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A218044 Numbers of the form 2^k + prime, with k > 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica