A156695 -id:A156695 - cp's OEIS frontend

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

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

A154257 Number of triples such that p+F_s+F_t=n, where p is an odd prime, s and t are greater than one and the Fibonacci number F_s or F_t is odd.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 4, 6, 6, 7, 6, 7, 8, 6, 10, 8, 10, 10, 10, 12, 10, 10, 10, 12, 14, 13, 12, 15, 8, 12, 12, 13, 14, 13, 10, 16, 10, 13, 16, 11, 16, 11, 14, 17, 16, 15, 12, 12, 16, 11, 20, 13, 14, 13, 12, 12, 18, 12, 16, 14, 14, 19, 16, 18, 20, 16, 18, 15, 18, 16, 12, 16, 18, 19, 22, 18

Offset: 1

Zhi-Wei Sun, Jan 05 2009

nonn

On Dec 23 2008, Zhi-Wei Sun made a conjecture that states that a(n)>0 for all n=5,6,... (i.e., any integer n>4 can be written as the sum of an odd prime, an odd Fibonacci number and a positive Fibonacci number). This has been verified for n up to 10^14 by D. S. McNeil; the conjecture looks more difficult than the Goldbach conjecture since Fibonacci numbers are much more sparse than prime numbers. Sun also conjectured that c=lim inf_n a(n)/log n is greater than 2 and smaller than 3.

Zhi-Wei Sun has offered a monetary reward for settling this conjecture.

			For n=9 the a(9)=6 solutions are 3 + F_4 + F_4, 3 + F_2 + F_5, 3 + F_5 + F_2, 5 + F_3 + F_3, 5 + F_2 + F_4, 5 + F_4 + F_2.

R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36(1971), 103-107.
Z. W. Sun and M. H. Le, Integers not of the form c(2^a+2^b)+p^{alpha}, Acta Arith. 99(2001), 183-190.

Zhi-Wei Sun, Table of n, a(n), n=1..50000.
D. S. McNeil, Sun's strong conjecture
Zhi-Wei Sun, A promising conjecture: n=p+F_s+F_t
Zhi-Wei Sun, A summary concerning my conjecture n=p+F_s+F_t (II)
K. J. Wu and Z.-W. Sun, Covers of the integers with odd moduli and their applications to the forms x^m-2^n and x^2-F_{3n}/2, Math. Comp. 78 (2009) 1853, [DOI], arXiv:math.NT/0702382

Cf. A000040, A000045, A156695. See A144559 for another version.

PQ[m_]:=m>2&&PrimeQ[m] RN[n_]:=Sum[If[(Mod[n,2]==0||Mod[x,3]>0)&&PQ[n-Fibonacci[x]-Fibonacci[y]],1,0], {x,2,2*Log[2,Max[2,n]]},{y,2,2*Log[2,Max[2,n-Fibonacci[x]]]}] Do[Print[n," ",RN[n]];Continue,{n,1,50000}]

The new verification record is 10^14 (due to D. S. McNeil). - Zhi-Wei Sun, Jan 17 2009

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

A304081 Number of ways to write n as p + 2^k + (1+(n mod 2))5^m, where p is an odd prime, and k and m are nonnegative integers with 2^k + (1+(n mod 2))5^m squarefree.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 2, 1, 3, 1, 2, 2, 2, 1, 3, 3, 3, 2, 4, 2, 3, 2, 5, 2, 4, 2, 3, 3, 3, 2, 4, 3, 5, 1, 7, 4, 4, 3, 7, 2, 4, 3, 8, 4, 7, 4, 6, 3, 7, 3, 6, 4, 5, 3, 5, 4, 5, 2, 7, 3, 5, 4, 8, 4, 5, 3, 5, 5, 8, 6, 6, 6, 9, 3, 9, 7, 6, 6, 8, 5, 6, 4, 6, 8, 7, 6, 8, 7, 4

Offset: 1

Zhi-Wei Sun, May 06 2018

nonn

Conjecture: a(n) > 0 for all n > 7.
This has been verified for n up to 2*10^10.
See also A303821, A303934, A303949, A304031 and A304122 for related information, and A304034 for a similar conjecture.
The author would like to offer 2500 US dollars as the prize to the first proof of the conjecture, and 250 US dollars as the prize to the first explicit counterexample. - Zhi-Wei Sun, May 08 2018

			a(6) = 1 since 6 = 3 + 2^1 + 5^0 with 3 an odd prime and 2^1 + 5^0 = 3 squarefree.
a(15) = 1 since 15 = 5 + 2^3 + 2*5^0 with 5 an odd prime and 2^3 + 2*5^0 = 2*5 squarefree.
a(35) = 1 since 35 = 29 + 2^2 + 2*5^0 with 29 an odd prime and 2^2 + 2*5^0 = 2*3 squarefree.
a(91) = 1 since 91 = 17 + 2^6 + 2*5^1 with 17 an odd prime and 2^6 + 2*5^1 = 2*37 squarefree.
a(9574899) = 1 since 9574899 = 9050609 + 2^19 + 2*5^0 with 9050609 an odd prime and 2^19 + 2*5^0 = 2*5*13*37*109 squarefree.
a(6447154629) = 2 since 6447154629 = 6447121859 + 2^15 + 2*5^0 with 6447121859 prime and 2^15 + 2*5^0 = 2*5*29*113 squarefree, and 6447154629 = 5958840611 + 2^15 + 2*5^12 with 5958840611 prime and 2^15 + 2*5^12 = 2*17*41*433*809 squarefree.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Mixed sums of primes and other terms, in: Additive Number Theory (edited by D. Chudnovsky and G. Chudnovsky), pp. 341-353, Springer, New York, 2010.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv, arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000040, A000079, A000351, A005117, A098983, A118955, A156695, A273812, A302982, A302984, A303233, A303234, A303338, A303363, A303389, A303393, A303399, A303428, A303401, A303432, A303434, A303539, A303540, A303541, A303543, A303601, A303637, A303639, A303656, A303660, A303702, A303821, A303932, A303934, A303949, A304031, A304032, A304034, A304122.

PQ[n_]:=n>2&&PrimeQ[n];
tab={};Do[r=0;Do[If[SquareFreeQ[2^k+(1+Mod[n,2])*5^m]&&PQ[n-2^k-(1+Mod[n,2])*5^m],r=r+1],{k,0,Log[2,n]},{m,0,If[2^k==n,-1,Log[5,(n-2^k)/(1+Mod[n,2])]]}];tab=Append[tab,r],{n,1,90}];Print[tab]

A304034 Number of ways to write n as p + 2^k + (1+(n mod 2))3^m with p prime, where k and m are positive integers with 2^k + (1+(n mod 2))3^m squarefree.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 0, 2, 1, 3, 1, 4, 2, 5, 1, 3, 2, 5, 1, 7, 3, 3, 4, 4, 4, 6, 2, 3, 5, 6, 2, 7, 3, 5, 5, 6, 5, 9, 3, 4, 6, 7, 2, 12, 2, 5, 6, 7, 4, 10, 3, 3, 5, 8, 2, 8, 3, 4, 6, 8, 5, 9, 4, 2, 7, 7, 3, 13, 5, 5, 9, 7, 5, 13, 3, 6, 10, 7, 5, 10, 5, 7, 7, 9, 8, 13

Offset: 1

Zhi-Wei Sun, May 06 2018

nonn

Conjecture: a(n) > 0 for all n > 11.
This has been verified for n up to 10^10.
See also A304081 for a similar conjecture.

			a(8) = 1 since 8 = 3 + 2^1 + 3^1 with 3 prime and 2^1 + 3^1 = 5 squarefree.
a(13) = 1 since 13 = 3 + 2^2 + 2*3^1 with 3 prime and 2^2 + 2*3^1 = 2*5 squarefree.
a(19) = 1 since 19 = 5 + 2^3 + 2*3^1 with 5 prime and 2^3 + 2*3^1 = 2*7 squarefree.
a(23) = 1 since 23 = 13 + 2^2 + 2*3^1 with 13 prime and 2^2 + 2*3 = 2*5 squarefree.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Mixed sums of primes and other terms, in: Additive Number Theory (edited by D. Chudnovsky and G. Chudnovsky), pp. 341-353, Springer, New York, 2010.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000040, A000079, A000224, A005117, A118955, A155216, A156695, A273812, A302982, A302984, A303233, A303234, A303338, A303363, A303389, A303393, A303399, A303428, A303401, A303432, A303434, A303539, A303540, A303541, A303543, A303601, A303637, A303639, A303656, A303660, A303702, A303821, A303932, A303934, A303949, A304031, A304032, A304081.

tab={};Do[r=0;Do[If[SquareFreeQ[2^k+(1+Mod[n,2])*3^m]&&PrimeQ[n-2^k-(1+Mod[n,2])*3^m],r=r+1],{k,1,Log[2,n]},{m,1,If[2^k==n,-1,Log[3,(n-2^k)/(1+Mod[n,2])]]}];tab=Append[tab,r],{n,1,90}];Print[tab]

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

Original entry on oeis.org

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

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

A154285 Number of ordered triples satisfying p+L_s+L_t=n, where p is an odd prime, s and t are nonnegative and the Lucas number L_s or L_t is odd.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 6, 4, 8, 5, 8, 6, 8, 9, 12, 10, 12, 9, 10, 12, 14, 9, 14, 12, 14, 10, 14, 8, 10, 10, 16, 11, 16, 12, 18, 12, 16, 10, 12, 13, 16, 15, 16, 13, 14, 13, 16, 14, 18

Offset: 1

Zhi-Wei Sun, Jan 06 2009

nonn

Zhi-Wei Sun conjectured that a(n)>0 for all n=5,6,...; in other words, any integer n>4 can be represented as the sum of an odd prime, an odd Lucas number and a Lucas number. This has been verified up to 1.5*10^8. Sun thought that the constant lim inf_n a(n)/log(n) is greater than 2 and smaller than 3. For k=2,3 Sun also conjectured that any integer n>4 can be written in the form p+L_s+(L_t)^k, where p is an odd prime and L_s or L_t is odd.

Zhi-Wei Sun has offered a monetary reward for settling this conjecture.

			For n=3 the a(7)=4 solutions are 3+L_1+L_2, 3+L_2+L_1, 5+L_1+L_1.

R. Crocker, On a sum of a prime and two powers of two, Pacific J. Math. 36(1971), 103-107.
Z. W. Sun and M. H. Le, Integers not of the form c(2^a+2^b)+p^{alpha}, Acta Arith. 99(2001), 183-190.

Zhi-Wei SUN, Table of n, a(n), n=1..50000.
D. S. McNeil, Sun's strong conjecture
Zhi-Wei Sun, A summary concerning my conjecture n=p+F_s+F_t
Zhi-Wei Sun, A summary concerning my conjecture n=p+F_s+F_t (II)
K. J. Wu and Z. W. Sun, Covers of the integers with odd moduli and their applications to the forms x^m-2^n and x^2-F_{3n}/2, Math. Comp. 78 (2009) 1853, arXiv:math.NT/0702382

Cf. A000032, A000040, A154257, A154258, A154263, A156695.

PQ[m_]:=m>2&&PrimeQ[m] RN[n_]:=Sum[If[(Mod[n,2]==0||Mod[x,3]>0)&&PQ[n-(2*Fibonacci[x+1]-Fibonacci[x])-(2*Fibonacci[y+1]-Fibonacci[y])],1,0], {x,0,2*Log[2,n]},{y,0,2*Log[2,Max[1,n-(2*Fibonacci[x+1]-Fibonacci[x])]]}] Do[Print[n," ",RN[n]];Continue,{n,1,50000}]

A303821 Number of ways to write 2*n as p + 2^x + 5^y, where p is a prime, and x and y are nonnegative integers.

Original entry on oeis.org

0, 1, 1, 3, 3, 4, 4, 5, 3, 6, 5, 5, 6, 6, 4, 7, 6, 7, 7, 10, 4, 9, 10, 6, 10, 8, 5, 8, 6, 7, 7, 9, 5, 8, 11, 6, 10, 11, 6, 11, 8, 6, 8, 11, 4, 9, 9, 7, 6, 11, 6, 7, 11, 7, 10, 11, 5, 11, 9, 6, 7, 6, 6, 5, 12, 7, 10, 15, 8, 15, 10, 11, 13, 11, 7, 9, 8, 9, 12, 14

Offset: 1

Zhi-Wei Sun, May 01 2018

nonn

Conjecture: a(n) > 0 for all n > 1. Moreover, for any integer n > 4, we can write 2*n as p + 2^x + 5^y, where p is an odd prime, and x and y are positive integers.
This has been verified for n up to 10^10.
See also A303934 and A304081 for further refinements, and A303932 and A304034 for similar conjectures.

			a(2) = 1 since 2*2 = 2 + 2^0 + 5^0 with 2 prime.
a(3) = 1 since 2*3 = 3 + 2^1 + 5^0 with 3 prime.
a(5616) = 2 since 2*5616 = 9059 + 2^11 + 5^3 = 10979 + 2^7 + 5^3 with 9059 and 10979 both prime.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Mixed sums of primes and other terms, in: Additive Number Theory (edited by D. Chudnovsky and G. Chudnovsky), pp. 341-353, Springer, New York, 2010.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000040, A000079, A000351, A118955, A156695, A273812, A302982, A302984, A303233, A303234, A303338, A303363, A303389, A303393, A303399, A303428, A303401, A303432, A303434, A303539, A303540, A303541, A303543, A303601, A303637, A303639, A303656, A303660, A303702, A303932, A303934, A304034, A304081.

tab={};Do[r=0;Do[If[PrimeQ[2n-2^k-5^m],r=r+1],{k,0,Log[2,2n-1]},{m,0,Log[5,2n-2^k]}];tab=Append[tab,r],{n,1,80}];Print[tab]

A303934 Number of ways to write 2*n as p + 2^k + 5^m with p prime and 2^k + 5^m squarefree, where k and m are nonnegative integers.

Original entry on oeis.org

0, 1, 1, 3, 3, 2, 2, 3, 3, 4, 3, 5, 4, 4, 3, 4, 5, 7, 4, 7, 4, 8, 7, 6, 7, 6, 5, 5, 5, 7, 5, 8, 5, 5, 8, 6, 9, 9, 6, 8, 6, 6, 7, 8, 4, 7, 8, 7, 3, 10, 6, 7, 8, 7, 7, 9, 5, 8, 7, 6, 5, 5, 6, 3, 11, 7, 9, 12, 8, 12, 10, 11, 11, 9, 7, 9, 7, 8, 8, 11, 7, 11, 8, 9, 15, 11, 8, 9, 8, 9

Offset: 1

Zhi-Wei Sun, May 03 2018

nonn

Conjecture: a(n) > 0 for all n > 1.
This has been verified for all n = 2..10^10.
Note that a(n) <= A303821(n).

			a(2) = 1 since 2*2 = 2 + 2^0 + 5^0 with 2 prime and 2^0 + 5^0 squarefree.
a(3) = 1 since 2*3 = 3 + 2^1 + 5^0 with 3 prime and 2^1 + 5^0 squarefree.

Zhi-Wei Sun, Table of n, a(n) for n = 1..10000
Zhi-Wei Sun, Mixed sums of primes and other terms, in: Additive Number Theory (edited by D. Chudnovsky and G. Chudnovsky), pp. 341-353, Springer, New York, 2010.
Zhi-Wei Sun, Conjectures on representations involving primes, in: M. Nathanson (ed.), Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, Springer, Cham, 2017, pp. 279-310. (See also arXiv:1211.1588 [math.NT], 2012-2017.)

Cf. A000040, A000079, A000351, A005117, A118955, A156695, A273812, A302982, A302984, A303233, A303234, A303338, A303363, A303389, A303393, A303399, A303428, A303401, A303432, A303434, A303539, A303540, A303541, A303543, A303601, A303637, A303639, A303656, A303660, A303702, A303821, A303932, A304034, A304081, A304122.

tab={};Do[r=0;Do[If[SquareFreeQ[2^k+5^m]&&PrimeQ[2n-2^k-5^m],r=r+1],{k,0,Log[2,2n-1]},{m,0,Log[5,2n-2^k]}];tab=Append[tab,r],{n,1,90}];Print[tab]

cp's OEIS Frontend

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

A154257 Number of triples such that p+F_s+F_t=n, where p is an odd prime, s and t are greater than one and the Fibonacci number F_s or F_t is odd.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Extensions

A118955 Numbers of the form 2^k + prime.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

A304081 Number of ways to write n as p + 2^k + (1+(n mod 2))*5^m, where p is an odd prime, and k and m are nonnegative integers with 2^k + (1+(n mod 2))*5^m squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A304034 Number of ways to write n as p + 2^k + (1+(n mod 2))*3^m with p prime, where k and m are positive integers with 2^k + (1+(n mod 2))*3^m squarefree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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.

A304081 Number of ways to write n as p + 2^k + (1+(n mod 2))5^m, where p is an odd prime, and k and m are nonnegative integers with 2^k + (1+(n mod 2))5^m squarefree.

A304034 Number of ways to write n as p + 2^k + (1+(n mod 2))3^m with p prime, where k and m are positive integers with 2^k + (1+(n mod 2))3^m squarefree.