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,6

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]

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.

Example

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.

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 *)

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.

Sequence in context: A152949 A338431 A058660 * A273096 A076619 A318140

Adjacent sequences: A059868 A059869 A059870 * A059872 A059873 A059874

Keyword

nonn

Author

Antti Karttunen, Feb 05 2001

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

Status

approved