A108421 Smallest number of ones needed to write in binary representation 2*n as sum of two primes.

2, 4, 4, 4, 5, 5, 5, 5, 4, 4, 5, 6, 5, 5, 6, 4, 5, 6, 5, 5, 5, 5, 6, 6, 6, 5, 6, 5, 6, 7, 7, 7, 8, 5, 5, 6, 5, 5, 6, 6, 5, 6, 6, 5, 6, 6, 7, 8, 5, 5, 6, 6, 6, 6, 7, 5, 6, 6, 7, 8, 7, 7, 8, 6, 7, 5, 5, 6, 5, 5, 6, 6, 5, 6, 6, 5, 6, 7, 7, 7, 6, 6, 6, 6, 6, 6, 7, 6, 6, 7, 7, 7, 8, 7, 8, 6, 5, 5, 6, 6, 6, 6, 7, 5, 6

Offset: 2

Author

Reinhard Zumkeller, Jun 03 2005

Keywords

• nonn
• base

Comments

a(n) = Min{A000120(p)+A000120(q) : p,q prime and p+q=2*n}.

a(n) = A108422(n) - A108423(n).

a(n) >= A000120(n)+1, with equality for n in A241757. - Robert Israel, Mar 25 2018

Examples

			n=15: 2*15=30 and A002375(15)=3 with 30=7+23=11+19=13+17,
13+17 -> 1101+10001 needs a(15)=5 binary ones, whereas
7+23 -> 111+10111 and 11+19 -> 1011+10011 need more.
		

Links

• Robert Israel, Table of n, a(n) for n = 2..10000
• Index entries for sequences related to Goldbach conjecture
• Index entries for sequences related to binary expansion of n

Crossrefs

Cf. A000120, A004676, A005843, A007088, A108422, A108423, A241757.

Programs

Maple

N:= 200: # to get a(2)..a(N)
Primes:= select(isprime, [seq(i,i=3..2*N-3,2)]):
Ones:= map(t -> convert(convert(t,base,2),`+`), Primes):
V:= Vector(N): V[2]:= 2:
for i from 1 to nops(Primes) do
  p:= Primes[i];
  for j from 1 to i do
    k:= (p+Primes[j])/2;
    if k > N then break fi;
    t:= Ones[i]+Ones[j];
    if V[k] = 0 or t < V[k] then V[k]:= t fi
  od
od:
convert(V[2..N],list); # Robert Israel, Mar 25 2018

Mathematica

Min[#]&/@(Table[Total[Flatten[IntegerDigits[#,2]]]&/@Select[ IntegerPartitions[ 2*n,{2}],AllTrue[#,PrimeQ]&],{n,2,110}]) (* Harvey P. Dale, Jul 27 2020 *)