A078687 -id:A078687 - cp's OEIS frontend

A065381 Primes not of the form p + 2^k, p prime and k >= 0.

2, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 907, 977, 997, 1019, 1087, 1259, 1549, 1597, 1619, 1657, 1759, 1777, 1783, 1867, 1973, 2203, 2213, 2293, 2377, 2503, 2579, 2683, 2789, 2843, 2879, 2909, 2999, 3119, 3163, 3181, 3187, 3299

Offset: 1

Reinhard Zumkeller, Nov 03 2001

nonn

Sequence is infinite. For example, Pollack shows that numbers which are 1260327937 mod 2863311360 are not of the form p + 2^k for any prime p and k >= 0, and there are infinitely many primes in this congruence class by Dirichlet's theorem. - Charles R Greathouse IV, Jul 20 2014

			127 is a prime, 127-2^0 through 127-2^6 are all nonprimes.

T. D. Noe, Table of n, a(n) for n = 1..1000
P. Pollack, Not Always Buried Deep: Selections from Analytic and Combinatorial Number Theory, p. 193, ex. 5.1.6, p. 216ff. [?Broken link]
P. Pollack, Not Always Buried Deep: Selections from Analytic and Combinatorial Number Theory, p. 193, ex. 5.1.6, p. 216ff.
Lei Zhou, Between 2^n and primes.

Equals A000040 minus A065380.
Cf. A010051, A006285, A102630, A094076, A156695.
Cf. A098237.

a065381 n = a065381_list !! (n-1)
a065381_list = filter f a000040_list where
   f p = all ((== 0) . a010051 . (p -)) $ takeWhile (<= p) a000079_list
-- Reinhard Zumkeller, Nov 24 2011

fQ[n_] := Block[{k = Floor[Log[2, n]], p = n}, While[k > -1 && ! PrimeQ[p - 2^k], k--]; If[k > 0, True, False]]; Drop[Select[Prime[Range[536]], ! fQ[#] &], {2}] (* Robert G. Wilson v, Feb 10 2005; corrected by Arkadiusz Wesolowski, May 05 2012 *)

is(p)=my(k=1);while(kp,return(isprime(p)));0 \\ Charles R Greathouse IV, Jul 20 2014

A078687(A049084(a(n))) = 0; subsequence of A118958. - Reinhard Zumkeller, May 07 2006

Link and cross-reference fixed by Charles R Greathouse IV, Nov 09 2008

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
Thomas Bloom, Let f(n) count the number of solutions to n = p + 2^k for prime p and k >= 0. Is it true that f(n) = o(log n)?, Erdős Problems.
Terence Tao, Erdős problem database, see no. 236.

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

A065380 Primes of the form p + 2^k, p prime and k >= 0.

Original entry on oeis.org

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 131, 137, 139, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 257, 263, 269, 271, 277, 281, 283, 293

Offset: 1

Reinhard Zumkeller, Nov 03 2001

nonn

			a(3) = 11 = 3 + 2^3 = 7 + 2^2.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A010051, A000079, A065381, A156695.

a065380 n = a065380_list !! (n-1)
a065380_list = filter f a000040_list where
   f p = any ((== 1) . a010051 . (p -)) $ takeWhile (<= p) a000079_list
-- Reinhard Zumkeller, Nov 24 2011

With[{upto=300},Select[Union[Select[Flatten[Outer[Plus,Prime[Range[ PrimePi[upto]]],2^Range[0,Floor[Log[2,upto]]]]],PrimeQ]],#<=upto&]] (* Harvey P. Dale, Feb 28 2012 *)

A078687(A049084(a(n))) > 0; A091932 is a subsequence. - Reinhard Zumkeller, May 07 2006

A118953 Number of ways to write the n-th prime as 2^k + p, where p is prime and p < 2^k.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1

Offset: 1

Reinhard Zumkeller, May 07 2006

nonn

0 <= a(n) <= 1, a(n) <= A078687(n);
a(A049084(A118958(n))) = 0, a(A049084(A091932(n))) = 1;
a(n) = A118952(A000040(n)).

A244917 Smallest prime p such that p - 2^e is also prime in exactly n cases for nonnegative integers e.

Original entry on oeis.org

2, 3, 7, 19, 139, 829, 3331, 32941, 176417, 854929, 2233531, 12699571, 47924959, 763597201, 5775760189

Offset: 0

Robert G. Wilson v, Jul 09 2014

The exponent e is obviously limited to 0 <= e <= log_2(p).
The sequence is obtained by building a greedy prime index inverse of A078687, which is 1, 2, 4, 8, 34, ..., followed by lookup in the primes, A000040.
From Robert G. Wilson v, Sep 12 2014: (Start)
2, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, …, ;
3, 5, 17, 29, 41, 53, 59, 89, 97, 137, 163, 179, 191, …, ;
7, 11, 13, 23, 31, 37, 43, 47, 67, 71, 73, 79, 101, …, ;
19, 61, 83, 131, 167, 227, 229, 241, 271, 293, 353, …, ;
139, 181, 199, 571, 601, 619, 677, 691, 1217, 1231, …, ;
829, 1487, 2131, 2341, 2551, 2971, 4051, 4261, 4583, …, ;
3331, 12109, 14551, 17393, 22279, 22307, 22741, …, ;
32941, 34369, 44029, 49433, 67189, 95717, 99833, …, ;
176417, 304771, 314723, 314779, 349667, 414707, …, ;
854929, 1297651, 1328927, 1784723, 2164433, 2488909, …, ;
2233531, 6026089, 7475389, 7623229, 9644911, …, ;
12699571, 18464123, 52849879, 78127339, 79303579, …, ;
47924959, 153309649, 204797059, 248685923, 273865219, …, ;
763597201, 1194032507, 1522018741, 1833343669, …, ;.
(End)

			a(3) = 19 since 19-2^1=17, 19-2^3=11 & 19-2^4=3 and there exists no prime less than 19 which exhibits this characteristic.

Cf. A078686.

f[n_] := Length@ Table[q = p - 2^exp; If[ PrimeQ@ q, {q}, Sequence @@ {}], {exp, 0, Floor@ Log2@ p}]; t = Table[0, {20}]; p = 2; While[p < 100000001, a = f@ p; If[ t[[a]] == 0, t[[a]] = p; Print[{a, p}]]; p = NextPrime@ p]; t

a(14) from Robert G. Wilson v, Sep 12 2014

cp's OEIS Frontend

A065381 Primes not of the form p + 2^k, p prime and k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

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

A065380 Primes of the form p + 2^k, p prime and k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A118953 Number of ways to write the n-th prime as 2^k + p, where p is prime and p < 2^k.

Views

Author

Keywords

Comments

A244917 Smallest prime p such that p - 2^e is also prime in exactly n cases for nonnegative integers e.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions