A054845 Number of ways of representing n as the sum of one or more consecutive primes.
0, 0, 1, 1, 0, 2, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 2, 1, 1, 0, 0, 0, 2, 1, 0, 1, 0, 1, 1, 1, 2, 0, 0, 0, 0, 2, 1, 0, 1, 0, 3, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 2, 0, 0, 1, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 2, 2, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 3, 1, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 2, 1, 0, 2, 2
Offset: 0
Examples
a(5)=2 because of 2+3 and 5. a(17)=2 because of 2+3+5+7 and 17. 41 = 41 = 11+13+17 = 2+3+5+7+11+13, so a(41)=3.
References
- R. K. Guy, Unsolved Problems In Number Theory, C2.
Links
- T. D. Noe, Table of n, a(n) for n = 0..10000
- Leo Moser, Notes on number theory. III. On the sum of consecutive primes, Canad. Math. Bull. 6 (1963), pp. 159-161.
- Carlos Rivera, Problem 9, The Prime Puzzles and Problems Connection.
Programs
-
Magma
S:=[0]; for n in [1..104] do count:=0; for q in PrimesUpTo(n) do p:=q; s:=p; while s lt n do p:=NextPrime(p); s+:=p; end while; if s eq n then count+:=1; end if; end for; Append(~S, count); end for; S; // Klaus Brockhaus, Feb 17 2011
-
Maple
A054845 := proc(n) local a,mipri,npr,ps ; a := 0 ; for mipri from 1 do for npr from 1 do ps := add(ithprime(i),i=mipri..mipri+npr-1) ; if ps = n then a := a+1 ; elif ps >n then break; end if; end do: if ithprime(mipri) > n then break ; end if; end do: a ; end proc: # R. J. Mathar, Nov 27 2018
-
Mathematica
f[n_] := Block[{p = Prime@ Range@ PrimePi@ n}, len = Length@ p; Count[(Flatten[#, 1] &)[Table[ p[[i ;; j]], {i, len}, {j, i, len}]], q_ /; Total@ q == n]]; f[0] = 0; Array[f, 102, 0](* Jean-François Alcover, Feb 16 2011 *) (* fixed by Robert G. Wilson v *) nn=100; p=Prime[Range[PrimePi[nn]]]; t=Table[0,{nn}]; Do[s=0; j=i; While[s=s+p[[j]]; s<=nn,t[[s]]++; j++], {i,Length[p]}]; Join[{0},t] -
PARI
{/* program gives values of a(n) for n=0..precprime(nn)-1 */ nn=2000;t=vector(nn+1);forprime(x=2,nn,s=x; forprime(y=x+1,nn,if(s<=nn,t[s+1]++,break());s=s+y));t[1..precprime(nn)]} \\ Zak Seidov, Feb 17 2011, corrected by Michael S. Branicky, Feb 28 2022 -
Perl
use ntheory ":all"; my $n=10000; my @W=(0)x($n+1); forprimes { my $s=$; do { $W[$s]++; $s += ($=next_prime($)); } while $s <= $n; } $n; print "$ $W[$]\n" for 0..$#W; # _Dana Jacobsen, Aug 22 2018 -
Python
from sympy import primerange def aupton(nn): # modification of PARI by Zak Seidov alst = [0 for n in range(nn+1)] for x in primerange(2, nn+1): s = x alst[s] += 1 for y in primerange(x+1, nn+1): s += y if s <= nn: alst[s] += 1 else: break return alst print(aupton(101)) # Michael S. Branicky, Feb 17 2022 -
Python
# alternate version for going to large n import heapq from sympy import prime from itertools import islice def agen(): # generator of terms p = v = prime(1); h = [(p, 1, 1)]; nextcount = 2; oldv = ways = 0 while True: (v, s, l) = heapq.heappop(h) if v == oldv: ways += 1 else: yield ways for n in range(oldv+1, v): yield 0 ways = 1 if v >= p: p += prime(nextcount) heapq.heappush(h, (p, 1, nextcount)) nextcount += 1 oldv = v v -= prime(s); s += 1; l += 1; v += prime(l) heapq.heappush(h, (v, s, l)) print(list(islice(agen(), 102))) # Michael S. Branicky, Feb 17 2022
Formula
G.f.: Sum_{i>=1} Sum_{j>=i} Product_{k=i..j} x^prime(k). - Ilya Gutkovskiy, Apr 18 2019
Extensions
Edited by N. J. A. Sloane, Oct 27 2008 at the suggestion of Jake M. Foster
Comments