The number of ways a number is a sum of consecutive primes

Question

Given an integer greater than 1, output the number of ways it can be expressed as the sum of one or more consecutive primes.

Order of summands doesn't matter. A sum can consist of a single number (so the output for any prime will be at least 1.)

This is code-golf. Standard rules apply.

See this OEIS wiki for related information and sequences, including the sequence itself OEIS A054845.

Test cases

2 => 1
3 => 1
4 => 0
5 => 2
6 => 0
7 => 1
8 => 1
10 => 1
36 => 2
41 => 3
42 => 1
43 => 1
44 => 0
311 => 5
1151 => 4
34421 => 6

Answer 1

Jelly, (削除) 6 (削除ここまで) 5 bytes

-1 thanks to dylnan

ÆRẆ§ċ

A monadic link

Try it online! Or see the test-suite (note the final test case would time out at 60s at TIO).

How?

ÆRẆ§ċ - Link: integer, n
ÆR - primes from 2 to n inclusive
 Ẇ - all contiguous substrings
 § - sum each
 ċ - count occurrences of n

• dylnan: 2æR is same as ÆR
• Jonathan Allan: @dylnan nice one thanks!

Answer 2

R, 95 bytes

function(x,P=2){for(i in 2:x)P=c(P,i[all(i%%P)])
for(i in 1:x){F=F+sum(cumsum(P)==x)
P[i]=0}
F}

Try it online!

• -24 bytes thanks to @Giuseppe who has basically revolutionized my solution supporting 34421 as well !

• Giuseppe: that's a clever way of coming up with primes up to x!
• Giuseppe: 97 bytes
• digEmAll: @Giuseppe: that is great !! Today I'm sick and I would have never been able to think that... (maybe never ever :P) I'm feeling bad in using your code...I reverted to previous, if you post a new answer I'll upvote ;)
• Giuseppe: @ngm what's the significance of 34421..? And @digEmAll, I don't really mind; I really didn't have a clue about using cumsum and setting the first few elements to 0 to get the consecutive prime sums. The prime golf was just me trying to get the last test case working, and I just lucked out that it was shorter than outer! I have more than enough rep (at least until we get proper rep requirements), and I'm always happy to help more R golfers get more visibility!
• ngm: @Giuseppe 34421 is the smallest number that is the sum of consecutive primes in exactly 6 ways (see oeis.org/A054859). Most solutions posted for this challenge run out of either time (on TIO) or memory for that test case. Although the Java answer even got the next integer in the sequence too (for 7) but not for 8.

Answer 3

05AB1E, 6 bytes

Code

ÅPŒOQO

Uses the 05AB1E encoding. Try it online!

Answer 4

JavaScript (ES6), 92 bytes

n=>(a=[],k=1,g=s=>k>n?0:!s+g(s>0?s-(p=d=>k%--d?p(d):d<2&&a.push(k)&&k)(++k):s+a.shift()))(n)

Try it online!

Commented

n => ( // n = input
 a = [], // a[] = array holding the list of consecutive primes
 k = 1, // k = current number to test
 g = s => // g = recursive function taking s = n - sum(a)
 k > n ? // if k is greater than n:
 0 // stop recursion
 : // else:
 !s + // increment the final result if s = 0
 g( // add the result of a recursive call to g():
 s > 0 ? // if s is positive:
 s - ( // subtract from s the result of p():
 p = d => k % --d ? // p() = recursive helper function looking
 p(d) // for the highest divisor d of k,
 : // starting with d = k - 1
 d < 2 && // if d is less than 2 (i.e. k is prime):
 a.push(k) && // append k to a[]
 k // and return k (else: return false)
 )(++k) // increment k and call p(k)
 : // else:
 s + a.shift() // remove the first entry from a[]
 // and add it to s
 ) // end of recursive call
 )(n) // initial call to g() with s = n

Answer 5

Brachylog, (削除) 14 (削除ここまで) 9 bytes

{⟦ṗss+?}c

Try it online!
Multiple test cases

(-5 whole bytes, thanks to @Kroppeb!)

Explanation:

{⟦ṗss+?}c
{ }c Count the number of ways this predicate can succeed:
 ⟦ Range from 0 to input
 ṗs Select only the prime numbers
 s The list of prime numbers has a substring (contiguous subset)
 + Whose sum
 ? Is the input

• Kroppeb: You can golf it by calculating ⟦ṗs inside the c loop. I got this {⟦ṗss+;?=}c Test suite: Try it online!
• Kroppeb: Realized I can replace the ;?= by ? and get {⟦ṗss+?}c (9 bytes)
• Sundar R: @Kroppeb Of course! That's a much more elegant answer too. Thank you.

Answer 6

MATL, (削除) 15 (削除ここまで) 12 bytes

EZqPYTRYsG=z

Try it on MATL Online

The initial E (multiply by 2) makes sure that, for prime input, the result of the later Ys (cumsum) does not have the input prime repeating itself in the zeroed part of the matrix (thus messing with the count).

Explanation:

 % Implicit input, say 5
E % Double the input
 Zq % Get list of primes upto (and including) that
 % Stack: [2 3 5 7]
 P % Reverse that list
 YT % Toeplitz matrix of that
 % Stack: [7 5 3 2
 5 7 5 3
 3 5 7 5
 2 3 5 7]
 R % `triu` - upper triangular portion of matrix
 % Stack: [7 5 3 2
 0 7 5 3
 0 0 7 5
 0 0 0 7]
 Ys % Cumulative sum along each column
 % Stack: [7 5 3 2
 7 12 8 5
 7 12 15 10
 7 12 15 17]
 G= % Compare against input - 1s where equal, 0s where not
 z % Count the number of non-zeros

• Luis Mendo: Toeplitz matrix of primes and triangular part, very nice!

Answer 7

Retina 0.8.2, 68 bytes

.+
$*_$&$*
_
$`__¶
A`^(__+)1円+$
m)&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

Try it online! Link includes faster test cases. Explanation:

m)

Run the whole script in multiline mode where ^ and $ match on every line.

.+
$*_$&$*

Convert to unary twice, first using _s, then using 1s.

_
$`__¶

Generate all the prefixes of the _s and add two to each, thus counting from \2ドル\$ to \$n + 1\$.

A`^(__+)1円+$

Delete all the composite numbers in the range.

&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

Match any number of _s and newlines (starting and ending at the end of a line) then compare the number of _s with the number of 1s. Count the number of sums of consecutive prime numbers which add up to \$n\$.

Answer 8

Husk, (削除) 9 (削除ここまで) 8 bytes

^{-1 byte thanks to Mr.Xcoder (use named argument 1 instead of S)!}

#1ṁ∫ṫ↑İp

Try it online!

Explanation

#1ṁ∫ṫ↑İp -- example input: 3
#1 -- count the occurrences of 3 in
 İp -- | primes: [2,3,5,7..]
 ↑ -- | take 3: [2,3,5]
 ṫ -- | tails: [[2,3,5],[3,5],[5]]
 ṁ -- | map and flatten
 ∫ -- | | cumulative sums
 -- | : [2,5,10,3,8,5]
 -- : 1

• Mr. Xcoder: As a full program, #¹ṁ∫ṫ↑İp should save 1 byte.

Answer 9

Perl 6, 53 bytes

{+grep $_,map {|[\+] $_},[\R,] grep *.is-prime,2..$_}

Try it online!

Uses the triangle reduction operator twice. The last test case is too slow for TIO.

Explanation

{ } # Anonymous block
 grep *.is-prime,2..$_ # List of primes up to n
 [\R,] # All sublists (2) (3 2) (5 3 2) (7 5 3 2) ...
 map {|[\+] $_}, # Partial sums for each, flattened
 +grep $_, # Count number of occurrences

Answer 10

MATL, 16 bytes

:"GZq@:g2&Y+G=vs

Try it at MATL Online!

Explanation

:" % Input (implicit): n. For each k in [1 2 ... n]
 G % Push n
 Zq % Primes up to that
 @:g % Push vector of k ones
 2&Y+ % Convolution, removing the edges
 G= % True for entries that equal n
 v % Concatenate vertically with previous results
 s % Sum
 % End (implicit). Display (implicit)

Answer 11

Python 2, (削除) 106 (削除ここまで) 104 bytes

P=k=o=1
p=[]
i=input()
exec'o+=P%k*sum(p)==i;P*=k*k;k+=1;p+=P%k*[k];exec"p=p[i<sum(p):];"*k;'*i
print~-o

Try it online!

Answer 12

Clean, (削除) 100 (削除ここまで) 98 bytes

import StdEnv,StdLib
$n=sum[1\\z<-inits[i\\i<-[2..n]|all(\j=i/j*j<i)[2..i-1]],s<-tails z|sum s==n]

Try it online!

Defines the function $ :: Int -> Int which works as explained below:

$ n // the function $ of n is
 = sum [ // the sum of
 1 // 1, for every 
 \\ z <- inits [ // prefix z of 
 i // i, for every
 \\ i <- [2..n] // integer i between 2 and n
 | and [ // where every
 i/j*j < i // j does not divide i
 \\ j <- [2..i-1] // for every j between 2 and i-1
 ]
 ]
 , s <- tails z // ... and suffix s of the prefix z
 | sum s == n // where the sum of the suffix is equal to n
 ]

(Explanation is for an older but logically identical version)

• ngm: Special commendation for getting output for 34421.

Answer 13

Java 10, (削除) 195 (削除ここまで) (削除) 194 (削除ここまで) (削除) 184 (削除ここまで) 182 bytes

n->{var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}for(x=L.size(),i=0;i<x;)for(k=i++,s=0;k<x;r+=s==n?1:0)s+=(int)L.get(k++);return r;}

-1 byte thanks to @ceilingcat.
-10 bytes thanks to @SaraJ.

Try it online.

Explanation:

n->{ // Method with integer as both parameter and return-type
 var L=new java.util.Stack();
 // List of primes, starting empty
 int i=1,k,x,s, // Temp integers
 r=0; // Result-counter, starting at 0
 for(;i++<n;){ // Loop `i` in the range [2, `n`]
 for(k=1; // Set `k` to 1
 i%++k>0;); // Inner loop which increases `k` by 1 before every iteration,
 // and continues as long as `i` is not divisible by `k`
 if(k==i) // If `k` is now still the same as `i`; a.k.a. if `i` is a prime:
 L.add(i);} // Add the prime to the List
 for(x=L.size(), // Get the amount of primes in the List
 i=0;i<x;) // Loop `i` in the range [0, amount_of_primes)
 for(s=0, // (Re)set the sum to 0
 k=i++;k<x; // Inner loop `k` in the range [`i`, amount_of_primes)
 r+=s==n? // After every iteration, if the sum is equal to the input:
 1 // Increase the result-counter by 1
 : // Else:
 0) // Leave the result-counter the same by adding 0
 s+=(int)L.get(k++);
 // Add the next prime (at index `k`) to the sum
 return r;} // And finally return the result-counter

---

It's basically similar as the Jelly or 05AB1E answers, just 190 bytes more.. XD
Here a comparison for each of the parts, added just for fun (and to see why Java is so verbose, and these golfing languages are so powerful):

1. Take the input: (Jelly: 0 bytes) implicitly; (05AB1E: 0 bytes) implicitly; (Java 10: 5 bytes) n->{}
2. Create a list of primes in the range [2, n]: (Jelly: 2 bytes) ÆR; (05AB1E: 2 bytes) ÅP; (Java 10: 95 bytes) var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}
3. Get all continuous sub-lists: (Jelly: 1 byte) Ẇ; (05AB1E: 1 byte) Œ; (Java 10: 55 bytes) for(x=L.size(),i=0;i<x;)for(k=i++;k<x;) and (int)L.get(k++);
4. Sum each sub-list: (Jelly: 1 byte) §; (05AB1E: 1 byte) O; (Java 10: 9 bytes) ,s and ,s=0 and s+=
5. Count those equal to the input: (Jelly: 1 byte) ċ; (05AB1E: 2 bytes) QO; (Java 10: 15 bytes) ,r=0 and r+=s==n?1:0
6. Output the result: (Jelly: 0 bytes) implicitly; (05AB1E: 0 bytes) implicitly; (Java 10: 9 bytes) return r;

• ngm: Special commendation for getting output for 34421.
• Kevin Cruijssen: @ngm :) Java may be bad at many things, but performance-wise it's pretty good usually.
• ngm: Even works on 218918. Times out with 3634531.
• Kevin Cruijssen: @ngm I'm actually surprised it's still fast enough to do the 218918 in 12.5 sec tbh, considering it will do 218918-2 = 218,916 iterations with inside an inner loop of: n iterations for every prime; 1 iteration for every even number; and somewhere between [2,p/2) iterations for every odd number (close to two billion iterations), after which it adds 19518 primes to the list in memory. And then it will loop an additional sum([0,19518]) = 190,485,921 times in the second nested loop.. 2,223,570,640 iterations in total to be exact.
• Kevin Cruijssen: @ceilingcat Thanks. Been able to golf 12 more bytes with @SaraJ's alternative prime check, minus the trailing %i since we're checking in the range [2, n], so I won't need to check i=1. :)

Answer 14

Japt -x, (削除) 17 (削除ここまで) 10 bytes

(削除) There's gotta be a shorter way than this! (削除ここまで) I was right!

Craps out on the last test case.

õ fj ã@¶Xx

Try it or run all test cases (except 34421)

õ fj ã@¶Xx :Implicit input of integer U
õ :Range [1,U]
 f :Filter
 j : Is prime?
 ã :Sub-arrays
 @ :Map each X
 ¶ : U is equal to
 Xx : X reduced by addition
 :Implicit output of sum of resulting array

Answer 15

Physica, 41 bytes

->x:Count[Sum@Sublists[PrimeQ$$[...x]];x]

Try it online!

How it works

->x:Count[Sum@Sublists[PrimeQ$$[...x]];x] // Full program.
->x: // Define an anonymous function with parameter x.
 [...x] // Range [0 ... x] (inclusive).
 $$ // Filter-keep those that...
 PrimeQ // Are prime.
 Sublists[...] // Get all their sublists.
Sum@ // Then sum each sublist.
Count[...;x] // Count the number of times x occurs in the result.

Answer 16

Haskell, 89 bytes

g n=sum[1|a<-[0..n],_<-filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]]

Try it online!

Alternative, 89 bytes

f n=length$do a<-[0..n];filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]

Try it online!

Answer 17

Wolfram Language (Mathematica), (削除) 42 (削除ここまで) 40 bytes

Count[Tr/@Subsequences@Prime@Range@#,#]&

Try it online!

Edit: -2 Bytes thanks to att :) !

• att: -2: Primes is Listable
• att: oops Prime not Primes :')

Answer 18

APL(NARS), 97 chars

r←d w;i;j;p;s
r←1⋄p←⍬
r←1πr⋄p×ばつ⍳w≥r
i×ばつ⍳(≢p)<j←i+←1⋄s←0
s+←p×ばつ⍳s<w⋄r+←s=w⋄→4

-- 13+たす7+たす18+たす5+たす19+たす30+たす 5=わ97

there is one loop for find the list of prime number <= argument w (but the last element of "p" is >w) and one loop the sum from index i, until find the w or a number >w; than increment i and begin another time until the index i is >(≢p). Below is the function with number of line used from goto →

 r←d w;i;j;p;s
1: r←1⋄p←⍬
2: r←1πr⋄p×ばつ⍳w≥r
3: i←r←0
4: ×ばつ⍳(≢p)<j←i+←1⋄s←0
5: s+←p×ばつ⍳s<w⋄r+←s=w⋄→4

test:

 d ̈⍳10
0 1 1 0 2 0 1 1 0 1 
 d ̈311 1151 34421 
5 4 6