A059871 Number of solutions to the equation p_i = (1+mod(i,2))*p_{i-1} +- p_{i-2} +- p_{i-3} +- ... +- 2 +- 1, where p_i is the i-th prime number (where p_1 = 2 and the "zeroth prime" p_0 is defined to be 1).

1, 1, 1, 1, 1, 3, 3, 4, 6, 12, 16, 31, 46, 90, 140, 276, 449, 877, 1443, 2834, 4725, 9395, 16153, 32037, 55872, 110288, 190815, 380488, 672728, 1342395, 2434797, 4808180, 8579625, 17070112, 30858078, 61271317, 110926277, 220979544, 402354848

Offset: 1

Author

Antti Karttunen, Feb 05 2001

Keywords

• nonn

Comments

In Burton's book it is said that it is "known" that each prime can be represented as such sum. However, I do not know whether that means it has been proved.

This is Scherk's theorem, which was conjectured by Scherk in 1833 and proved by Pillai in 1928. [T. D. Noe, Oct 03 2008]

Examples

			For the first five primes we have only one solution for each: 2 = 2*1, 3 = 1*2 + 1*1, 5 = 2*3 - 1*2 + 1*1, 7 = 1*5 + 1*3 - 1*2 + 1*1, 11 = 2*7 - 1*5 + 1*3 - 1*2 + 1*1 and for the next prime 13, we have 3 solutions: 13 = 11-7+5+3+2-1 = 11+7-5-3+2+1 = 11+7-5+3-2-1.
		

References

• D. M. Burton, Elementary Number Theory.
• S. S. Pillai, "On some empirical theorem of Scherk", J. Indian Math. Soc. 17 (1927-28), pp. 164-171.
• W. Sierpiński, Elementary Theory of Numbers, Warszawa, 1964.

Links

• Alois P. Heinz and Ray Chandler, Table of n, a(n) for n = 1..1000 (first 250 terms from Alois P. Heinz)
• J. L. Brown, Proof of Scherk's Conjecture on the Representation of Primes, Amer. Math. Monthly 74 (1967), 31-33.
• William Y. Lee, On the representation of integers, Math. Mag. 47 (1974), 150-152.
• H. F. Scherk, Bemerkungen über die Bildung der Primzahlen aus einander, Journal für die reine und angewandte Mathematik 10 (1883), pp. 201-208.
• H. F. Scherk, Bemerkungen über die Bildung der Primzahlen aus einander, Journal für die reine und angewandte Mathematik 10 (1883), pp. 201-208.

Crossrefs

See A059872 for the table of all solutions encoded as binary vectors and A059873-A059875 for specific sequences. A059876 gives the function bin_prime_sum.

Cf. A022894, A083309.

Programs

Maple

map(nops, primesums_primes_mult(16)); primesums_primes_mult := proc(upto_n) local a,b,i,n,p,t; a := []; for n from 1 to upto_n do b := []; p := ithprime(n); for i from (2^(n-1)) to ((2^n)-1) do t := bin_prime_sum(i); if(t = p) then b := [op(b),i]; fi; od; a := [op(a),b]; print(a); od; RETURN(a); end;
# second Maple program
p:= n-> `if`(n<0, 0, `if`(n=0, 1, ithprime(n))):
sp:= proc(n) sp(n):= `if`(n<0, 0, p(n)+sp(n-1)) end:
b := proc(n, i) option remember; `if`(n>sp(i), 0, `if`(i<0, 1,
        b(n+p(i), i-1)+ b(abs(n-p(i)), i-1)))
     end:
a:= n-> b(p(n) -(1+irem(n, 2))*p(n-1), n-2):
seq(a(n), n=1..40);  # Alois P. Heinz, Aug 05 2012

Mathematica

nmax = 40; d = {1}; a1 = {}; pp = 1;
Do[
  p = Prime[n];
  i = Ceiling[Length[d]/2] +  Abs[p - (1 + Mod[n, 2])*pp];
  AppendTo[a1, If[i > Length[d], 0, d[[i]]]];
  d = PadLeft[d, Length[d] + 2 pp] + PadRight[d, Length[d] + 2 pp];
  pp = p;
  , {n, nmax}];
a1 (* Ray Chandler, Mar 11 2014 *)

Extensions

More terms from Naohiro Nomoto, Sep 11 2001

More terms from Larry Reeves (larryr(AT)acm.org), Nov 20 2003

a(33)-a(39) from Donovan Johnson, Oct 01 2010