A109925 -id:A109925 - cp's OEIS frontend

A109926 Least k such that k-2^r is prime for n values of r. Index of the first occurrence of n in A109925.

1, 3, 4, 15, 21, 45, 75, 465, 1095, 2145, 4935, 14955, 80685, 229845, 1295325, 1575285, 9700575, 20435415, 15054105, 53999715, 2282745465

Offset: 0

Amarnath Murthy, Jul 17 2005

It appears that 3 and 5 divide a(n) for n>4. Note that a(18)T. D. Noe, Jul 19 2005
Conjecture: a(n)==0 (mod 3) for n > 2. Then n-2^k is not == 0 (mod 3) and a prime is more probable. - Robert G. Wilson v, Jul 21 2005
Conjecture: a(n+15)==0 (mod 30) for n > 4. - Robert G. Wilson v, Jul 21 2005
a(n) > 10^10 for n >= 21. - Donovan Johnson, Jan 21 2009

			a(4) = 21, 21-2 =19, 21-4 = 17, 21-8 = 13, 21-16 = 5, 21 is the smallest number that gives four such primes.

Cf. A109925.

t=Table[cnt=0; r=1; While[rRobert G. Wilson v *)

from itertools import count
from sympy import isprime
def A109926(n):
    for m in count(1):
        c = 0
        for k in range(m.bit_length()):
            if isprime(m-(1<n:
                break
        if c == n:
            return m # Chai Wah Wu, Feb 23 2025

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

a(20) from Donovan Johnson, Jan 21 2009

A175956 Numbers n such that A109925(n) = A109925(n+1).

Original entry on oeis.org

1, 6, 29, 41, 53, 59, 65, 89, 97, 126, 137, 148, 163, 179, 191, 192, 193, 223, 233, 239, 250, 252, 257, 269, 281, 307, 311, 330, 336, 359, 372, 389, 402, 419, 431, 457, 491, 504, 508, 521, 547, 557, 569, 598, 613, 641, 653, 659, 673, 683, 700, 719, 733, 739

Offset: 1

Juri-Stepan Gerasimov, Oct 29 2010, Oct 31 2010

nonn

(Number of primes of the form n-2^k) = (number of primes of the form n-2^k+1).

			a(2)=6 because A109925(6) = A109925(7) = 2.

Muniru A Asiru, Table of n, a(n) for n = 1..332

Cf. A000040, A000079.

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; S:=[]; a:=a109925(1); for n in [1..750] do b:=a109925(n+1); if a eq b then Append(~S, n); end if; a:=b; end for; S; // Klaus Brockhaus, Oct 30 2010

A109925 := proc(n) a := 0 ; for k from 0 do p := n-2^k ; if p < 2 then return a; elif isprime(p) then a := a+1 ; end if; end do: end proc:
isA175956 := proc(n) A109925(n) = A109925(n+1) ; end proc:
for n from 1 to 1500 do if isA175956(n) then printf("%d,",n); end if; end do:
# R. J. Mathar, Oct 30 2010

SequencePosition[Table[Count[n-2^Range[0,Floor[Log2[n]]],?PrimeQ],{n,800}],{x,x_}][[;;,1]] (* Harvey P. Dale, Oct 21 2024 *)

A109925(a(n)) = A109925(a(n) + 1).

More terms from Klaus Brockhaus and R. J. Mathar, Oct 30 2010

A006285 Odd numbers not of form p + 2^k (de Polignac numbers).

Original entry on oeis.org

1, 127, 149, 251, 331, 337, 373, 509, 599, 701, 757, 809, 877, 905, 907, 959, 977, 997, 1019, 1087, 1199, 1207, 1211, 1243, 1259, 1271, 1477, 1529, 1541, 1549, 1589, 1597, 1619, 1649, 1657, 1719, 1759, 1777, 1783, 1807, 1829, 1859, 1867, 1927, 1969, 1973, 1985, 2171, 2203, 2213, 2231, 2263, 2279, 2293, 2377, 2429, 2465, 2503, 2579, 2669

Offset: 1

N. J. A. Sloane

Contains both primes (A065381) and composites (A098237). - Jonathan Vos Post, Jun 19 2008
Crocker shows that this sequence is infinite; in particular, 2^2^n - 5 is in this sequence for each n > 2. - Charles R Greathouse IV, Sep 01 2015
Problem: what is the asymptotic density of de Polignac numbers? Based on the data in A254248, it seems this sequence may have an asymptotic density d > 0.05. Conjecture (cf. Pomerance 2013): the density d(n) of de Polignac numbers <= n is d(n) ~ (1 - 2/log(n))^(log(n)/log(2)), so the asymptotic density d = exp(-2/log(2)) = 0.055833... = 0.111666.../2. - Thomas Ordowski, Jan 30 2021
From Amiram Eldar, Feb 03 2021: (Start)
Romanov (or Romanoff) proved in 1934 that the complementary sequence has a positive lower asymptotic density, and the assumed asymptotic density was later named Romanov's constant (Pintz, 2006).
The lower asymptotic density of this sequence is positive (Van Der Corput, 1950; Erdős, 1950), and larger than 0.00905 (Habsieger and Roblot, 2006).
The upper asymptotic density of this sequence is smaller than 0.392352 (Elsholtz and Schlage-Puchta, 2018).
Previous bounds on the upper asymptotic density were given by Chen and Sun (2006), Pintz (2006), Habsieger and Roblot (2006), Lü (2007) and Habsieger and Sivak-Fischler (2010).
Romani (1983) conjectured that the asymptotic density of this sequence is 0.066... (End)
Chen, Dai, & Li show that the lower asymptotic density of this sequence is larger than 0.00965, improving on Habsieger & Roblot. - Charles R Greathouse IV, Jul 08 2024

			127 is in the sequence since 127 - 2^0 = 126, 127 - 2^1 = 125, 127 - 2^2 = 123, 127 - 2^3 = 119, 127 - 2^4 = 111, 127 - 2^5 = 95, and 127 - 2^6 = 63 are all composite. - _Michael B. Porter_, Aug 29 2016

Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966. See p. 226.
R. K. Guy, Unsolved Problems in Number Theory, Springer, 1st edition, 1981. See section F13.
Clifford A. Pickover, A Passion for Mathematics, John Wiley & Sons, Inc., NJ, 2005, pp. 62 & 300.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
J. G. Van Der Corput, On de Polignac's conjecture, Simon Stevin, Vol. 27 (1950), pp. 99-105.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, see #127.

T. D. Noe, Table of n, a(n) for n = 1..10000
Thomas Bloom, Is the set of odd integers not of the form 2^k+p the union of an infinite arithmetic progression and a set of density 0?, Erdős Problems.
Yuda Chen, Xiangjun Dai, and Huixi Li, Some results on a conjecture of de Polignac about numbers of the form p + 2^k, arXiv preprint (2024). arXiv:2402.06644 [math.NT]
Yong-Gao Chen and Xue-Gong Sun, On Romanoff's constant, Journal of Number Theory, Vol. 106, No. 2 (2004), pp. 275-284.
Roger Crocker, A theorem concerning prime numbers, Mathematics Magazine, Vol. 34, No. 6 (1961), pp. 316-344.
Yuchen Ding, On a problem of Romanoff type, arXiv:2201.12783 [math.NT], 2022.
Christian Elsholtz and Jan-Christoph Schlage-Puchta, On Romanov's constant, Mathematische Zeitschrift, Vol. 288 (2018), pp. 713-724; alternative link.
Paul Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math., Vol. 2 (1950), p. 113-125.
Laurent Habsieger and Xavier-François Roblot, On integers of the form p+2^k, Acta Arithmetica, Vol. 122, No. 1 (2006), pp. 45-50.
Laurent Habsieger and Jimena Sivak-Fischler, An effective version of the Bombieri-Vinogradov theorem, and applications to Chen's theorem and to sums of primes and powers of two, Archiv der Mathematik, Vol. 95, No. 6 (2010), pp. 557-566.
Guang-Shi Lü, On Romanoff's constant and its generalized problem, Chinese Advances in Mathematics, Vol. 36, No. 1 (2007), pp. 94-100.
János Pintz, A note on Romanov's constant, Acta Mathematica Hungarica, Vol. 112, No. 1-2 (2006), pp. 1-14.
Paul Pollack, Not Always Buried Deep: A Second Course in Elementary Number Theory, AMS, 2009, p. 201, exercise 34.
Carl Pomerance, Erdős, van der Corput, and the birth of covering congruences, Joint Mathematics Meetings, Special Session on Covering Congruences, San Diego, CA, January, 2013.
F. Romani, Computations concerning primes and powers of two, Calcolo, Vol. 20 (1983), pp. 319-336.
Nikolai Pavlovich Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann., Vol. 109 (1934), pp. 668-678.
Terence Tao, Erdős problem database, see entry no. 16.
Wikipedia, Romanov's theorem.

Cf. A133122, A098237, A065381, A156695, A109925, A118954, A232460, A276417, A254248.

See also A058517, A350957, A350959, A350960.

a006285 n = a006285_list !! (n-1)
a006285_list = filter ((== 0) . a109925) [1, 3 ..]
-- Reinhard Zumkeller, May 27 2015

lst:=[]; for n in [1..1973 by 2] do x:=-1; 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; // Arkadiusz Wesolowski, Aug 29 2016

N:= 10000: # to get all terms <= N
P:= select(isprime, {2,seq(i,i=3..N,2)}):
T:= {seq(2^i,i=0..ilog2(N))}:
R:= {seq(i,i=1..N,2)} minus {seq(seq(p+t,p=P),t=T)}:
sort(convert(R,list)); # Robert Israel, Sep 23 2016

Do[ i = 0; l = Ceiling[ N[ Log[ 2, n ] ] ]; While[ ! PrimeQ[ n - 2^i ] && i < l, i++ ]; If[ i == l, Print[ n ] ], {n, 1, 2000, 2} ]
Join[{1},Select[Range[5,1999,2],!MemberQ[PrimeQ[#-2^Range[Floor[ Log[ 2,#]]]], True]&]] (* Harvey P. Dale, Jul 22 2011 *)

isA006285(n,i=1)={ bittest(n,0) && until( isprime(n-i) || nn } \\ M. F. Hasler, Jun 19 2008, updated Apr 12 2017

from itertools import count, islice
from sympy import isprime
def A006285_gen(startvalue=1): # generator of terms
    return filter(lambda n: not any(isprime(n-(1<A006285_list = list(islice(A006285_gen(),30)) # Chai Wah Wu, Nov 29 2023

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

Conjecture: a(n) ~ n*exp(2/log(2)) = n*17.91... - Thomas Ordowski, Feb 02 2021

More terms from Larry Reeves (larryr(AT)acm.org), Apr 13 2000

A118955 Numbers of the form 2^k + prime.

Original entry on oeis.org

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 23, 24, 25, 27, 29, 30, 31, 32, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 47, 48, 49, 51, 53, 54, 55, 57, 59, 60, 61, 62, 63, 65, 66, 67, 68, 69, 71, 72, 73, 74, 75, 77, 79, 80, 81, 83, 84, 85, 87, 89, 90, 91, 93

Offset: 1

Reinhard Zumkeller, May 07 2006

nonn

A109925(a(n)) > 0, complement of A118954;
The lower density is at least 0.09368 (Pintz) and upper density is at most 0.49095 (Habsieger & Roblot). The density, if it exists, is called Romanov's constant. Romani conjectures that it is around 0.434. - Charles R Greathouse IV, Mar 12 2008
Elsholtz & Schlage-Puchta improve the bound on lower density to 0.107648. Unpublished work by Jie Wu improves this to 0.110114, see Remark 1 in Elsholtz & Schlage-Puchta. - Charles R Greathouse IV, Aug 06 2021

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.1, p. 87.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000.
Christian Elsholtz and Jan-Christoph Schlage-Puchta, On Romanov's constant, Mathematische Zeitschrift, Vol. 288 (2018), pp. 713-724.
Laurent Habsieger and Xavier-Francois Roblot, On integers of the form p + 2^k, Acta Arithmetica 122:1 (2006), pp. 45-50.
J. Pintz, A note on Romanov's constant, Acta Mathematica Hungarica 112:1-2 (2006), pp. 1-14.
F. Romani, Computations concerning primes and powers of two, Calcolo 20 (1983), pp. 319-336.

Subsequence of A081311; A118957 is a subsequence.

Cf. A156695, A010051, A000079.

a118955 n = a118955_list !! (n-1)
a118955_list = filter f [1..] where
   f x = any (== 1) $ map (a010051 . (x -)) $ takeWhile (< x) a000079_list
-- Reinhard Zumkeller, Jan 03 2014

Select[Range[100], (For[r=False; k=1, #>k, k*=2, If[PrimeQ[#-k], r=True]]; r)& ] (* Jean-François Alcover, Dec 26 2013, after Charles R Greathouse IV *)

is(n)=my(k=1);while(n>k,if(isprime(n-k),return(1),k*=2));0 \\ Charles R Greathouse IV, Mar 12 2008

list(lim)=my(v=List(),t=1); while(tCharles R Greathouse IV, Aug 06 2021

from itertools import count, islice
from sympy import isprime
def A118955_gen(startvalue=1): # generator of terms >= startvalue
    return filter(lambda n: any(isprime(n-(1<A118955_list = list(islice(A118955_gen(),30)) # Chai Wah Wu, Nov 29 2023

A118954 Numbers that cannot be written as 2^k + prime.

Original entry on oeis.org

1, 2, 16, 22, 26, 28, 36, 40, 46, 50, 52, 56, 58, 64, 70, 76, 78, 82, 86, 88, 92, 94, 96, 100, 106, 112, 116, 118, 120, 122, 124, 126, 127, 134, 136, 142, 144, 146, 148, 149, 154, 156, 160, 162, 166, 170, 172, 176, 178, 184, 186, 188, 190, 196, 202, 204, 206, 208

Offset: 1

Reinhard Zumkeller, May 07 2006

nonn

A109925(a(n)) = 0.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Roger Crocker, A theorem concerning prime numbers, Mathematics Magazine 34:6 (1961), pp. 316+344.
P. Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math. 2 (1950), 113-123.
N. P. Romanoff, Über einige Sätze der additiven Zahlentheorie, Math. Ann. 57 (1934), pp. 668-678.
J. G. van der Corput, On de Polignac’s conjecture, Simon Stevin 27 (1950), pp. 99-105. Cited in MR 35298.

Complement of A118955. Subsequence of A118956. Supersequence of A006285.

Cf. A156695, A010051, A000079.

a118954 n = a118954_list !! (n-1)
a118954_list = filter f [1..] where
   f x = all (== 0) $ map (a010051 . (x -)) $ takeWhile (< x) a000079_list
-- Reinhard Zumkeller, Jan 03 2014

lst:=[]; for n in [1..208] do k:=-1; repeat k+:=1; a:=n-2^k; until a lt 1 or IsPrime(a); if a lt 1 then Append(~lst, n); end if; end for; lst; // Arkadiusz Wesolowski, Sep 02 2016

is(n)=my(k=1);while(kCharles R Greathouse IV, Sep 01 2015

n < a(n) < kn for some k < 2 and all large enough n, see Romanoff and either Erdős or van der Corput. - Charles R Greathouse IV, Sep 01 2015

A078687 Number of x>=0 such that prime(n)-2^x is prime.

Original entry on oeis.org

0, 1, 1, 2, 2, 2, 1, 3, 2, 1, 2, 2, 1, 2, 2, 1, 1, 3, 2, 2, 2, 2, 3, 1, 1, 2, 2, 2, 2, 2, 0, 3, 1, 4, 0, 2, 2, 1, 3, 2, 1, 4, 1, 1, 2, 4, 2, 1, 3, 3, 1, 1, 3, 0, 2, 2, 1, 3, 2, 1, 2, 3, 1, 1, 2, 2, 0, 0, 2, 2, 3, 1, 2, 0, 2, 3, 1, 2, 2, 2, 1, 3, 1, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 3, 0, 1, 3, 2, 1, 1, 3, 1, 4

Offset: 1

Benoit Cloitre, Dec 17 2002

nonn

			prime(17)=59 and only 59-2^3 = 53 is prime hence a(17)=1

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

Cf. A156695.

f[p_] := Block[{c = exp = 0, lmt = 1 + Floor@ Log2@ p}, While[exp < lmt, If[ PrimeQ[p - 2^exp], c++]; exp++]; c]; Array[ f@ Prime@# &, 105] (* Robert G. Wilson v, Jul 07 2014 *)

a(n)=sum(i=0,floor(log(prime(n))/log(2)),if(isprime(prime(n)-2^i),1,0))

a(A049084(A065381(n)))=0, a(A049084(A065380(n)))=1; A118953(n)<=a(n); a(n)=A109925(A000040(n)). - Reinhard Zumkeller, May 07 2006

A098237 Composite de Polignac numbers (A006285).

Original entry on oeis.org

905, 959, 1199, 1207, 1211, 1243, 1271, 1477, 1529, 1541, 1589, 1649, 1719, 1807, 1829, 1859, 1927, 1969, 1985, 2171, 2231, 2263, 2279, 2429, 2465, 2669, 2983, 2993, 3029, 3149, 3215, 3239, 3341, 3353, 3431, 3505, 3665, 3817, 3845, 3985

Offset: 1

Ralf Stephan, Aug 31 2004

nonn

Odd composites that are not the sum of a prime and a power of two.

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

Cf. A156695.

Cf. A006285, A109925, A065381.

a098237 n = a098237_list !! (n-1)
a098237_list = filter ((== 0) . a109925) a071904_list
-- Reinhard Zumkeller, May 27 2015

A118952 Characteristic function of numbers that can be written as p+2^k, where p is prime and p less than 2^k (A118957).

Original entry on oeis.org

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

Offset: 1

Reinhard Zumkeller, May 07 2006

nonn

0 <= a(n) <= 1, a(n) <= A109925(n);
a(A118956(n)) = 0, a(A118957(n)) = 1;
A118953(n) = a(A000040(n)).

Index entries for characteristic functions

A282432 Number of primes of the form n - 3^k.

Original entry on oeis.org

0, 0, 1, 1, 1, 2, 0, 2, 0, 1, 1, 2, 0, 3, 0, 2, 0, 1, 0, 3, 0, 2, 0, 1, 0, 2, 0, 1, 1, 2, 0, 4, 0, 2, 0, 0, 0, 3, 0, 3, 0, 1, 0, 3, 0, 3, 0, 1, 0, 3, 0, 1, 0, 1, 0, 3, 0, 1, 0, 1, 0, 3, 0, 2, 0, 0, 0, 3, 0, 3, 0, 1, 0, 3, 0, 2, 0, 0, 0, 3, 0, 2, 1, 2, 0, 3, 0, 3, 0, 1, 0, 3, 0, 2, 0, 0, 0, 4, 0, 3, 0, 1, 0, 3, 0

Offset: 1

Arkadiusz Wesolowski, Feb 15 2017

			a(14) = 3; 14 - 3^0 = 13, 14 - 3 = 11, 14 - 3^2 = 5, three primes.

Cf. A109925, A282430.

lst:=[]; for n in [1..105] do c:=0; e:=Floor(Log(3, n)); k:=0; while k le e do p:=n-3^k; if IsPrime(p) then c+:=1; end if; k+:=1; end while; Append(~lst, c); end for; lst;

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

ispp3(n) = (n==1) || (n==3) || (ispower(n,,&p) && (p==3));
a(n) = {my(nb = 0); forprime(p=2, n, nb += ispp3(n-p);); nb;} \\ Michel Marcus, Feb 18 2017

a(A282430(n)) = 0.

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

cp's OEIS Frontend

A109926 Least k such that k-2^r is prime for n values of r. Index of the first occurrence of n in A109925.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

Extensions

A175956 Numbers n such that A109925(n) = A109925(n+1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A006285 Odd numbers not of form p + 2^k (de Polignac numbers).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A118955 Numbers of the form 2^k + prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A118954 Numbers that cannot be written as 2^k + prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Magma

PARI

Formula

A078687 Number of x>=0 such that prime(n)-2^x is prime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI