A109925 -id:A109925 - cp's OEIS frontend

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

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

Offset: 1

Eric Chen, May 17 2015

In this sequence, "perfect power" does not include 0 or 1, "prime" does not include 1. Both "perfect power" and "prime" must be positive.
In the past, I conjectured that a(n) > 0 for all n>24, but this is not true. My PARI program found that a(1549) = 0.
I also asked which a(n) are 1. For example, 331 is a de Polignac number (A006285), so it cannot be written as 2^n+p with p prime, and 331-6^n must divisible by 5, 331-10^n must divisible by 3, ..., 331-18^2 = 331-324 = 7 is prime (and it is the only prime of the form 331-m^n, with m, n natural numbers, m>1, n>1), so a(331) = 1. Similarly, a(3319) = 1. Conjecture: a(n) > 1 for all n > 3319.
This conjecture is not true: a(1771561) = 0. (See A119748)
Another conjecture: For every number m>=0, there is a number k such that a(n)>=m for all n>=k.
Another conjecture: Except for k=2, first occurrence of k must be earlier then first occurrence of k+1.
For n such that a(n) = 0, see A119748.
For n such that a(n) = 1, see the following a-file of this sequence.

Eric Chen and Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 3000 terms from Chen)
Eric Chen, The unique way to write n as a sum of a perfect power (>1) and a prime for those n such a(n)=1

Cf. A196228, A119748, A109925, A118954, A064272, A064233, A002471, A014090.

nn = 128; pwrs = Flatten[Table[Range[2, Floor[nn^(1/ex)]]^ex, {ex, 2, Floor[Log[2, nn]]}]]; pp = Prime[Range[PrimePi[nn]]]; t = Table[0, {nn}]; Do[ t[[i[[1]]]] = i[[2]], {i, Tally[Sort[Select[Flatten[Outer[Plus, pwrs, pp]], # <= nn &]]]}]; t

a(n) = sum(k=1, n-1, ispower(k) && isprime(n-k))

a(n)=sum(e=2,log(n)\log(2),sum(b=2,sqrtnint(n,e),isprime(n-b^e)&&!ispower(b))) \\ Charles R Greathouse IV, May 28 2015

A282459 Number of composite numbers of the form 2n - 2^k + 1 (k > 0, 2^k < 2n + 1).

Original entry on oeis.org

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

Offset: 0

Altug Alkan, Feb 15 2017

nonn

It is conjectured that a(n) > 0 for all n > 52. See related conjecture and findings in A039669. Also see the graph of this sequence.

			a(7) = 0 because 2*7 + 1 - 2^1 = 13, 2*7 + 1 - 2^2 = 11, 2*7 + 1 - 2^3 = 7 are prime numbers.

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

Cf. A002808, A039669, A067526, A109925.

isA002808(n) = n>1 && !isprime(n);
a(n) = sum(k=1, log(2*n+1)\log(2), isA002808(2*n+1-2^k))

A283806 Odd numbers which are uniquely decomposable into the sum of a prime and a power of two.

Original entry on oeis.org

3, 5, 17, 29, 41, 53, 59, 65, 89, 97, 119, 137, 163, 179, 185, 191, 193, 209, 217, 219, 221, 223, 233, 239, 247, 253, 269, 281, 305, 307, 311, 343, 359, 389, 403, 407, 415, 419, 427, 431, 457, 491, 505, 521, 533, 545, 547, 557, 569, 575, 581, 583, 597, 613, 637

Offset: 1

Arkadiusz Wesolowski, Mar 17 2017

It is conjectured that none of these numbers is in A101036.
A positive integer n belongs to this sequence if n is of the form x*y + x - 1 and for some m >= 1:
1) y = -1 + 2 * Product_{k=0..m} (2^(2^k) + 1),
2) x <= 2^(2^(m+1) - 1),
3) n - 2^(2^(m+1)) is prime.
Odd numbers m that satisfy A109925(m) = 1. - Michel Marcus, Mar 19 2017

			17 is in the sequence since 17 - 2^2 = 13 is a prime and 17 - 2^0 = 16, 17 - 2^1 = 15, 17 - 2^3 = 9, 17 - 2^4 = 1 are all nonprimes.

Robert G. Wilson v, Table of n, a(n) for n = 1..1000
Wikipedia, Prime number

Cf. A000215, A109925.

lst:=[]; for n in [1..637 by 2] do c:=0; r:=Floor(Log(n)/Log(2)); for x in [0..r] do a:=n-2^x; if IsPrime(a) then c+:=1; end if; if c eq 2 then break; end if; end for; if c eq 1 then Append(~lst, n); end if; end for; lst;

Select[Range[1, 640, 2], Function[n, Total@ Boole@ PrimeQ@ Map[n - # &, 2^Range[0, Floor@ Log2@ n]] == 1]] (* Michael De Vlieger, Mar 18 2017 *)

isok(n) = (n % 2) && (sum(k=0, log(n)\log(2), isprime(n-2^k)) == 1); \\ Michel Marcus, Mar 18 2017

from sympy import isprime
import math
print([n for n in range(1001) if n%2 and sum([isprime(n-2**k) for k in range(int(math.floor(math.log(n)/math.log(2))) + 1)]) == 1]) # Indranil Ghosh, Mar 29 2017

a(n) ~ 10*(n + n/log(n)).

A367186 Numbers that can be written as 2^k + prime in more than one way.

Original entry on oeis.org

4, 6, 7, 9, 11, 13, 15, 18, 19, 21, 23, 25, 27, 31, 33, 35, 37, 39, 43, 45, 47, 49, 51, 55, 57, 61, 63, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 91, 93, 95, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 121, 123, 125, 129, 131, 133, 135, 139, 141, 143, 145, 147, 151, 153, 155

Offset: 1

Yuda Chen, Nov 08 2023

nonn

Numbers m such that A109925(m) > 1.

			4 is a term since 4 = 2^0 + 3 = 2^1 + 2 which is 2 ways.
6 is a term since 6 = 2^0 + 5 = 2^2 + 2.

Subsequence of A118955.

Cf. A000040, A000079, A109925.

isok(m) = sum(k=0, logint(m,2), isprime(m-2^k)) > 1; \\ Michel Marcus, Nov 10 2023

from itertools import count, islice
from sympy import isprime
def A367186_gen(startvalue=1): # generator of terms >= startvalue
    for n in count(max(startvalue,1)):
        c = 0
        for i in range(n.bit_length()-1,-1,-1):
            if isprime(n-(1<1:
                yield n
                break
A367186_list = list(islice(A367186_gen(),30)) # Chai Wah Wu, Nov 29 2023

cp's OEIS Frontend

A253238 Number of ways to write n as a sum of a perfect power (>1) and a prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A282459 Number of composite numbers of the form 2*n - 2^k + 1 (k > 0, 2^k < 2*n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A283806 Odd numbers which are uniquely decomposable into the sum of a prime and a power of two.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

A367186 Numbers that can be written as 2^k + prime in more than one way.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

A282459 Number of composite numbers of the form 2n - 2^k + 1 (k > 0, 2^k < 2n + 1).