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

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 . Standard rules apply.

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

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

Jelly,  6  5 bytes

-1 thanks to dylnan

ÆRẆ§ċ

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

How?

ÆR    - primes from 2 to n inclusive
Ẇ   - all contiguous substrings
§  - sum each
ċ - count occurrences of n
• 2æR is same as ÆR Aug 20, 2018 at 20:26
• @dylnan nice one thanks! Aug 20, 2018 at 20:28

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 !
• that's a clever way of coming up with primes up to x! Aug 21, 2018 at 14:41
• 97 bytes Aug 21, 2018 at 15:50
• @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 ;) Aug 21, 2018 at 18:21
• @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! Aug 21, 2018 at 20:05
• @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.
– ngm
Aug 21, 2018 at 20:24

05AB1E, 6 bytes

Code

ÅPŒOQO

Uses the 05AB1E encoding. Try it online!

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

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
• Toeplitz matrix of primes and triangular part, very nice! Aug 20, 2018 at 21:44

Brachylog, 14 9 bytes

{⟦ṗˢs+?}ᶜ

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

Explanation:

{⟦ṗˢs+?}ᶜ
{      }ᶜ     Count the number of ways this predicate can succeed:
⟦            Range from 0 to input
ṗˢ          Select only the prime numbers
s         The list of prime numbers has a substring (contiguous subset)
+        Whose sum
?       Is the input
• You can golf it by calculating ⟦ṗˢ inside the loop. I got this {⟦ṗˢs+;?=}ᶜ Test suite: Try it online! Aug 20, 2018 at 20:56
• Realized I can replace the ;?= by ? and get {⟦ṗˢs+?}ᶜ (9 bytes) Aug 20, 2018 at 20:58
• @Kroppeb Of course! That's a much more elegant answer too. Thank you. Aug 20, 2018 at 21:26

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.

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) • Special commendation for getting output for 34421. – ngm Aug 21, 2018 at 14:56 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

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!