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.

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

16 Answers 16

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
  • 2æR is same as ÆR – dylnan Aug 20 at 20:26
  • @dylnan nice one thanks! – Jonathan Allan Aug 20 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! – Giuseppe Aug 21 at 14:41
  • 1
    97 bytes – Giuseppe Aug 21 at 15:50
  • 1
    @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 ;) – digEmAll Aug 21 at 18:21
  • 1
    @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! – Giuseppe Aug 21 at 20:05
  • 1
    @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 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
  • 1
    Toeplitz matrix of primes and triangular part, very nice! – Luis Mendo Aug 20 at 21:44

Brachylog, 14 9 bytes

{⟦ṗˢs+?}ᶜ

Try it online!
Multiple test cases

(-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! – Kroppeb Aug 20 at 20:56
  • Realized I can replace the ;?= by ? and get {⟦ṗˢs+?}ᶜ (9 bytes) – Kroppeb Aug 20 at 20:58
  • @Kroppeb Of course! That's a much more elegant answer too. Thank you. – sundar Aug 20 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.

&`^((_)|¶)+¶[_¶]*(?<-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\$.

Husk, 9 8 bytes

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

#¹ṁ∫ṫ↑İp

Try it online!

Explanation

#¹ṁ∫ṫ↑İp  -- example input: 3
#¹        -- 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
  • As a full program, #¹ṁ∫ṫ↑İp should save 1 byte. – Mr. Xcoder Aug 20 at 21:01

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)

Java 10, 195 bytes

n->{var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;++i<=n;){for(k=2,x=i;k<x;x=x%k++<1?0:x);if(x>1)L.add(x);}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;}

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=2,        //   Set `k` to 2
        x=i;        //   And `x` to the current `i`
        k<x;        //   Inner loop as long as `k` is still smaller than `x`
        x=x%k++<1?  //    If `x` is divisible by `k`:
           0        //     Set `x` to 0
          :         //    Else:
           x);      //     Leave `x` the same
    if(x>1)         //   If `x` is now still the same as `i` (so not 0 nor 1);
                    //   a.k.a. Is `i` a prime:
      L.add(x);}    //    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: 102 bytes) var L=new java.util.Stack();int i=1,k,x;for(;++i<=n;){for(k=2,x=i;k<x;x=x%k++<1?0:x);if(x>1)L.add(x);}
  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;
  • 1
    Special commendation for getting output for 34421. – ngm Aug 21 at 14:56
  • @ngm :) Java may be bad at many things, but performance-wise it's pretty good usually. – Kevin Cruijssen Aug 21 at 15:42
  • 1
    Even works on 218918. Times out with 3634531. – ngm Aug 21 at 17:53
  • 1
    @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 Aug 21 at 18:09

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!

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)

  • 1
    Special commendation for getting output for 34421. – ngm Aug 21 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
 +grep $_,  # Count number of occurrences

Japt, 17 bytes

There's gotta be a shorter way than this!

Craps out on the last test case.

õ fj x@ZãYÄ x@¶Xx

Try it or run all test cases


Explanation

                      :Implicit input of integer U
õ                     :Range [1,U]
  fj                  :Filter primes
      @               :Map each integer at 0-based index Y in array Z
         YÄ           :  Y+1
       Zã             :  Subsections of Z of that length
             @        :  Map each array X
               Xx     :    Reduce by addition
              ¶       :    Check for equality with U
            x         :  Reduce by addition
     x                :Reduce by addition

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.

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!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.