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

## 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, ...


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 , so the shortest submission (in bytes) for every language wins.

• Tips to avoid while writing challenges: The prime numbers. You could've used something else other than primality. – Okx Aug 17 '18 at 17:08
• @Okx I had a couple of reasons in mind when I choose primality this time: 1) There are some clever algorithms that are specific to this very sequence, like the one Dennis implemented 2) There is already an OEIS entry for this – Mr. Xcoder Aug 17 '18 at 17:13

# 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]


# 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!

# 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.


# 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.

# 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


# Ruby-rprime, 34 bytes

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


Try it online!

Outputs indefinitely.

# 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!

# 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

• Replace _+ with - and + with - for -1 byte. – isaacg Aug 18 '18 at 1:08
• @isaacg That's quite clever! I'll edit that in. – FryAmTheEggman Aug 18 '18 at 3:51

# 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]]
%  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


(1#1)2 2
(p#n)s k|pmodn>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.

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!

• You can do without ^2. That will change the predicate from testing is prime to testing is prime or 4, which doesn't matter in this application. – Christian Sievers Aug 17 '18 at 21:29

# 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).

# 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.

• – Mr. Xcoder Aug 17 '18 at 19:28

# 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.

• I know... I know... Me and my bitwise-tricks pedantry :) But you can save a byte with k=s-~v. – Mr. Xcoder Aug 17 '18 at 23:15
• @Mr. Xcoder: Your unholy bitwise sorcery will be the end of you yet! :) – Chas Brown Aug 17 '18 at 23:17

# 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!

# 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!

# C (gcc), 100 99 bytes

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!

# Japt, 17 bytes

Outputs the nth term, 0-indexed.

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


Try it