A387053 a(n) is the least k such that n is the sum of a prime and k powers of 2.

0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 1, 1, 2, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 1, 1, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 1, 0, 1, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 1, 1, 2, 1, 2, 1, 2, 0

Offset

2,15

Links

David A. Corneth, Table of n, a(n) for n = 2..10001

Thomas Bloom, Problem 10, Erdős Problems.

Daniel R. Johnston and Tim Trudgian, An update on the Linnik-Goldbach and Romanov problems, arXiv:2605.17825 [math.NT] (2026).

Formula

a(n) = 0 <=> n is prime.

Johnston & Trudgian prove, on GRH, that a(2n) <= 6 for all but finitely many n. - Charles R Greathouse IV, May 20 2026

Example

a(4) = 1 as 4 is the sum of a prime (2) and one power of 2 (2) but 4 is not prime.

Mathematica

a[n_]:=Module[{res}, If[PrimeQ[n], Return[0]]; res=Min[Map[DigitCount[n - #, 2, 1]&, Select[Range[2, n], PrimeQ]]]; res]; Array[a, 96, 2] (* James C. McMahon, Sep 23 2025 *)

Prog

(PARI) a(n) = if(isprime(n), return(0)); my(res=oo); forprime(p=2, n, res = min(res, hammingweight(n-p))); res
(PARI) a(n)=if(isprime(n), return(0)); for(k=0, logint(n-2, 2), if(isprime(n-2^k), return(1))); for(a=0, logint(n-3, 2), for(b=0, a-1, if(isprime(n-2^a-2^b), return(2)))); for(a=0, logint(n-5, 2), for(b=1, a-1, for(c=0, b-1, if(isprime(n-2^a-2^b-2^c), return(3))))); my(r=oo); forprime(p=2, n, my(t=hammingweight(n-p)); if(t<r, r=t)); r \\ Charles R Greathouse IV, May 20 2026
(Python)
from sympy import isprime, primerange
def a(n): return 0 if isprime(n) else min((n-p).bit_count() for p in primerange(1, n))
print([a(n) for n in range(2, 98)]) # Michael S. Branicky, Sep 20 2025
(Python)
from itertools import combinations
from sympy import isprime
def A387053(n):
    l = n.bit_length()
    for i in range(l+1):
        for c in combinations(range(l), i):
            if isprime(n-sum(1<<i for i in c)):
                return i # Chai Wah Wu, May 20 2026

Crossrefs

Cf. A000040, A098237.

Sequence in context: A342656 A293896 A066416 * A292342 A091991 A108234

Adjacent sequences: A387050 A387051 A387052 * A387054 A387055 A387056

Keyword

nonn

Author

David A. Corneth, Sep 20 2025

Status

approved