Compute the minimum \$a(n)>a(n-1)\$ such that \$a(1)+a(2)+\dots+a(n)\$ is prime (OEIS A051935)

Question

Background

Consider the following sequence (A051935 in OEIS):

• Start with the term \$2\$.
• Find the lowest integer \$n\$ greater than \$2\$ such that \$2+n\$ is prime.
• Find the lowest integer \$n'\$ greater than \$n\$ such that \$2 + n + n'\$ is prime etc.

A more formal definition:

$$a_n=\begin{cases}2 & \text{if }n=0 \\ \min\{x\in\Bbb{N}\mid x>a_{n-1} \text{ and }\left(x+\sum_{i=0}^{n-1}a_i\right) \text{ is prime}\} & \text{otherwise}\end{cases}$$

The first few terms of the sequence are (please refer to these as test cases):

2, 3, 6, 8, 10, 12, 18, 20, 22, 26, 30, 34, 36, 42, 44, 46, 50, 52, 60, 66, 72, 74, ...

Task

Your task is to generate this sequence in any of the following ways:

• Output its terms indefinitely.
• Given \$n\$, output \$a_{n}\$ (\$n^{\text{th}}\$ term, \$0\$ or \$1\$ indexed).
• Given \$n\$, output \$\{a_1, a_2, \dots, a_n\}\$ (first \$n\$ terms).

You can compete in any programming language and can take input and provide output through any standard method, while taking note that these loopholes are forbidden by default. This is code-golf, so the shortest submission (in bytes) for every language wins.

Answer 1

Brachylog, 13 bytes

~l.<₁a₀ᵇ+ᵐṗᵐ∧

Try it online!

Output is the list of first n terms of the sequence.

?~l.<₁a₀ᵇ+ᵐṗᵐ∧    Full code (? at beginning is implicit)

?~l.              Output is a list whose length is the input
    <₁            Output is an increasing list
      a₀ᵇ+ᵐ       And the cumulative sum of the output
           ṗᵐ     Consists only of prime numbers
             ∧    No further constraints on output

Explanation for a₀ᵇ+ᵐ:
a₀ᵇ               Get the list of all prefixes of the list
                  Is returned in increasing order of length
                  For eg. [2, 3, 6, 8] -> [[2], [2, 3], [2, 3, 6], [2, 3, 6, 8]]
   +ᵐ             Sum each inner list  -> [2, 5, 11, 19]

Answer 2

Python 2, 63 62 bytes

n=f=a=b=1
while 1:
 f*=n;n+=1;a+=1
 if~f%n<a-b:print a;b=a;a=0

Try it online!

Answer 3

Jelly, 11 9 bytes

0Ḥ_ÆnɗСI

This is a full program that takes n as an argument and prints the first n terms of the sequence.

Try it online!

How it works

0Ḥ_ÆnɗСI  Main link. Argument: n

0          Set the return value to 0.
      С   Accumulating iterate. When acting on a dyadic link d and called with
           arguments x and y, the resulting quicklink executes
           "x, y = d(x, y), x" n times, returning all intermediate values of x.
           Initially, x = 0 and  y = n.
     ɗ       Drei; combine the three links to the left into a dyadic chain.
 Ḥ             Unhalve; double the left argument.
  _            Subtract the right argument.
   Æn          Compute the next prime.
           This computes the partial sums of the sequence a, starting with 0.
        I  Increments; compute the forward differences.

Answer 4

05AB1E v2, 10 bytes

2λλOD₁+ÅNα

Try it online!

This only works in the non-legacy version, the Elixir rewrite. Outputs an infinite stream of integers. There are some bugs with the prime test that have been fixed in the latest commits, but are not yet live on TIO. It does work locally, though. Here is a GIF of its execution on my machine, modified to output the first few terms rather than the whole stream.

How it works

2λ

Defines a recursive infinite sequence with base case \$2\$. The λ structure is among 05AB1E's very cool new features. Briefly speaking, it takes a function \$a(n)\$, setting \$a(0)\$ to the integer argument given, in this case \$2\$.

λO

In this portion of code, λ's role is different. Already being inside a recursive environment, it instead generates \$[a(0),a(1),\dots,a(n-1)]\$, the list of all previous results. Then, O sums them up.

D₁+

Duplicate the sum for later use and add \$a(n-1)\$ to the second copy.

ÅN

Generates the lowest prime stricly greater than the above sum.

α

Finally, retrieve the absolute difference between the prime computed above and the first copy of the sum computed earlier (the sum of all previous iterations).

The stream is then implicitly printed to STDOUT indefinitely.

Answer 5

Ruby -rprime, 34 bytes

2.step{|i|$.+=p(i)if($.+i).prime?}

Try it online!

Outputs indefinitely.

Answer 6

Pyth, 12 11 bytes

.f&P-;Z=-;Z

Try it online!

Saved 1 byte thanks to isaacg.

Generates the first n such numbers, using a 1 based index.

.f finds the first k integers that satisfy a particular criterion starting from zero. Here, the criterion is that the previous prime we calculated, ;, plus the current number, Z, is prime (P). If it is, we also update the last calculated prime using the short-circuiting behaviour of the logical and function (&). Unfortunately .f's default variable is Z which costs a byte in the update.

The trick that isaacg figured out was to store the negation of the last prime and test on that minus the current value. This is shorter in Pyth since the primality check is overloaded: on positive numbers it finds the prime factorisation while on negative numbers it determines if the positive value of the number is prime.

This more or less translates into:

to_find = input()
last_prime = 0
current = 0
results = []
while to_find > 0:
    if is_prime( current + last_prime ):
        results.append( current )
        to_find -= 1
        last_prime += current
    current += 1
print results

Answer 7

Perl 6, 45 bytes

2,{first (*+@_.sum).is-prime,@_[*-1]^..*}...*

Try it online!

Returns a lazy list that generates the sequence with no end.

Explanation:

This uses the Sequence operator ... which defines the sequence as:

2,  # The first element is 2
  {  # The next element is:
    first  # The first value that:
          (*+@_.sum).is-prime,  # When added to the sum is a prime
          @_[*-1]^..*  # And is larger than the previous element
  }
...*  # And continue the sequence indefinitely

Answer 8

JavaScript (ES6), 63 bytes

Returns the \$n^{th}\$ term, 1-indexed.

n=>(k=0,s=1,g=d=>s%d?g(d-1):d<2?--n?g(s-=k-(k=s)):s-k:g(s++))()

Try it online!

Answer 9

MATL, 21 bytes

O2hGq:"t0)yd0)+_Yqh]d

Try it online!

Output is the first n terms of the sequence.

Explanation:

Constructs a list of primes (with an initial 0), and at the end finds the returns the differences between successive primes in the list.

              % Implicit input, say n
O2h           % Push P = [0, 2] on the stack 
Gq:"          % for loop: 1 to n-1
  t0)           % Take the last element of P
                %  Stack: [[0, 2], [2]] (in first iteration)
  yd0)          % Take the difference between the last
                %   two elements of P
                %  Stack: [[0, 2], [2], [2]]
  +             % Add those up
                %  Stack: [[0, 2], [4]]
  _Yq           % Get the next prime higher than that sum
                %  Stack: [[0, 2], [5]]
  h             % Concatenate that to the list P
                %  Stack: [[0, 2, 5]]
]             % End for loop
d             % Get the differences between successive elements of
              %   the final list P

Answer 10

Haskell, 67 bytes

(1#1)2 2
(p#n)s k|p`mod`n>0,n-s>k=k:(p#n)n(n-s)|w<-p*n=(w#(n+1))s k

Try it online!

(1#1)2 2 is a functions that takes no input and outputs an infinite list.

---

old answer:

Haskell, 88 83 78 76 bytes

The primality test is from this answer and improved by Christian Sievers (-2 bytes).

-5 bytes thanks to W W.

2#2
(p#s)n|n<1=p|w<-until(\m->mod(product[1..m-1])m>0)(+1)$s+p+1=(w-s)#w$n-1

Try it online!

Answer 11

05AB1E (legacy), 12 bytes

0U[XN+DpiN,U

Try it online!

Explanation

0U              # initialize X as 0
  [             # start an infinite loop
   XN+          # add X to N (the current iteration number)
      Dpi       # if the sum is prime:
         N,     #   print N
           U    #   and store the sum in X

There are a couple of different 12-byte solutions possible.
This particular one could have been 10 bytes if we had a usable variable initialized as 0 (instead of 1 and 2).

Answer 12

Python 2, 119 bytes

f=lambda n,k=1,m=1:m%k*k>n or-~f(n,k+1,m*k*k)
def g(i):
 r=[2]
 for j in range(i):r+=[f(sum(r)+r[-1])-sum(r)]
 return r

Try it online!

Next Prime function f() taken from this answer.

Function g() takes a non-negative integer i and returns a list of all items in the sequence up to that index.

Answer 13

Python 2, 99 98 bytes

def f(n,s=2,v=2):
 k=s-~v
 while any(k%i<1for i in range(2,k)):k+=1
 return n and f(n-1,k,k-s)or v

Try it online!

1 byte thx to Mr. Xcoder.

Answer 14

Haskell, 101 99 97 bytes

The function l takes no arguments and returns an infinite list. Not as short as the more direct approach by @ovs (and I obviously stole some parts form their answer), but maybe still golfable?

Thanks @H.PWiz for -2 bytes!

import Data.List
p m=mod(product[1..m-1])m>0
l=2:[until(p.(+sum a))(+1)$last a+1|a<-tail$inits l]

Try it online!

Answer 15

Python 2, 82 80 bytes

s=p=2
i=input()
P=n=1
while i:
 P*=n;n+=1
 if P%n>0<n-s-p:p=n-s;s=n;i-=1
print p

Try it online!

This outputs the nth number of the sequence (0-based). By moving the print in the loop, this can be modified to output the first n items at the same bytecount: Try it online!

Answer 16

C (gcc), 100 99 bytes

• Saved a byte thanks to ceilingcat.

p(r,i,m,a,l){for(l=m=a=0;a-r;)m+=i=p(a++);while(r*!l)for(++i,l=a=2;a-m-i;)l=(m+i)%a++?l:0;r=r?i:2;}

Try it online!

Answer 17

PARI/GP 73 bytes

a(n)=v=[2];s=vecsum;while(n--,v=concat(v,nextprime(s(v)+v[#v]+1)-s(v)));v

1-indexed, output: first n terms

Answer 18

Pyth, 13 bytes

I%sjs.BQ2 2\1.?0

Simply converts a given input to binary and prints the respective output whether the sum of 1's in the output list is even or not. Made in about 5 seconds, and can probably be done in way fewer characters than I have, but hey, I tried.

Answer 19

Japt, 17 bytes

Outputs the nth term, 0-indexed.

@_+T j}aXÄT±X}g2ì

Try it