# New Order #3: 5 8 6

## Introduction (may be ignored)

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the third challenge in this series (links to the first and second challenges).

In this challenge, we will arrange the natural numbers in rows of increasing length in such a way that the sum of each row is a prime. What I find really amazing about this, is that every natural number has a place in this arrangement. No numbers are skipped!

This visualisation of this arrangement looks like this:

row             numbers             sum
1                  1                  1
2                2   3                5
3              4   5   8             17
4            6   7   9  15           37
5          10 11  12  13  21         67
6        14  16 17  18  19  23      107
etc.


We can read the elements from the rows in this triangle. The first 20 elements are: 1, 2, 3, 4, 5, 8, 6, 7, 9, 15, 10, 11, 12, 13, 21, 14, 16, 17, 18, 19 (yes, there is a New Order song hidden in this sequence).

Since this is a "pure sequence" challenge, the task is to output $$\a(n)\$$ for a given $$\n\$$ as input, where $$\a(n)\$$ is A162371.

Given an integer input $$\n\$$, output $$\a(n)\$$ in integer format.

$$\a(n)\$$ is defined as the $$\n\$$th element of the lexicographically earliest permutation of the natural numbers such that, when seen as a triangle read by rows, for n>1 the sums of rows are prime numbers. Since the first lexicographical permutation of natural numbers starts with 1, $$\a(1)\$$ is 1. Note that by this definition $$\a(1) = 1\$$ and $$\a(1)\$$ is not required to be prime. This is OEIS sequence A162371.

Note: 1-based indexing is assumed here; you may use 0-based indexing, so $$\a(0) = 1; a(1) = 2\$$, etc. Please mention this in your answer if you choose to use this.

## Test cases

Input | Output
---------------
1     |  1
5     |  5
20    |  19
50    |  50
78    |  87
123   |  123
1234  |  1233
3000  |  3000
9999  |  9999
29890 |  29913


## Rules

• Input and output are integers (your program should at least support input and output in the range of 1 up to 32767)
• Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
• Default I/O rules apply.
• Default loopholes are forbidden.
• This is , so the shortest answers in bytes wins
• Can we output the sequence infinitely, or return a generator instead?
– Jo King
Mar 27, 2019 at 23:45
• Err, 1 is not a prime
– Jo King
Mar 27, 2019 at 23:58
• @JoKing about a(1)=1: I'll add that. That is indeed the exception. This is stated clearly in the OEIS entry, buy I failed tot mention it explicitly. I'll add it to the question. Thanks. Mar 28, 2019 at 5:36
• @JoKing note that the definition of the sequence only requires the sum of the row to be prime for n>1. Since the sequence is the first lexicographical permutation of the natural numbers, a(1) comes out as 1. So indeed, 1 is not prime but the challenge or the definition of the sequence doesn't say or require 1 to be prime... Mar 28, 2019 at 7:33
• Related sequence: A075348. Mar 28, 2019 at 7:51

# Jelly, 32 bytes

;®»ṀƊSÆn_S
ẎṀ©+LRḟẎḣL;Ç$ṭ 1Ç¡Fị@  Try it online! - very slow as it builds n rows first, for a faster version which doesn't, at 37 bytes, try this. # Perl 6, 80 77 bytes {({$!=@_;+(1...{$_∉$!&&(|$!,$_).rotor(1..*).one.sum.is-prime-1})}...*)[$_]}  Try it online! ### Explanation: { } # Anonymous code block ( ...*)[$_]   # Index into the infinite sequence
{                      }   # Where each element is
$!=@_; # Save the list of previous elements into$!
+(1...{             })    # Return the first number that
$_∉$!         # Has not appeared in the list so far
&&            # And
(|$!,$_)      # The new sequence
.rotor(1..*)  # Split into rows of increasing length
# And ignoring incomplete rows
.one          # Have exactly one row
.sum          # Where the sum
.is-prime-1   # Is not prime (i.e. just the first row)


import Data.Numbers.Primes
l%a|(p,q)<-splitAt l a,(s,k:t)<-span(not.isPrime.(+sum p))q=p++k:(l+1)%(s++t)
((1:1%[2..])!!)


Try it online! (has an extra 2 bytes for f=)

EDIT: Now uses 0-based indexing to save 2 bytes. Thanks @wastl for pointing that out, I must have missed it in the OP.

This was very fun to write! The helper function % takes a length l and a list of values it can use a. It returns an infinite list of values for the sequence. The length is one less than the length of the current triangle row and the list is infinite and pre-sorted. First we just yield the first l values from a and then look through the rest of a until we find the first (smallest) value that makes the sum prime. We break up the list around that value using span and some pattern matching. Now all we have to do is yield that new value and recur with the next line length l+1 and the remaining values in a. For the final result we prepend 1 (special case for n=0) and index into it with !!.

• I think you can remove the 0: as the challenge states you can use 0-based indexing. Mar 31, 2019 at 20:58

# Husk, 22 bytes

!¡§ḟ(ΛoṗΣtü¤≤LCN:)-Nø


Try it online! I was honestly somewhat surprised that CN worked as intended here. Heavily inspired by Jo King's answer.

### Explanation

!¡λḟ(ΛoṗΣtü¤≤LCN:⁰)-⁰N)ø  (Expanded; let X denote the argument.)
!                         Take element X of
¡                         the list created by repeatedly applying this function
to the prior list and appending its output,
ø    starting with an empty list:
-⁰N      Take the list of natural numbers not contained in the
argument,
ḟ                         and find the first element such that
ΛoṗΣ                     all sums are prime of
:⁰                the element appended to the argument,
CN                 cut into lengths of 1, 2, 3, etc.,
ü¤≤L                  filtered for increasing length,
t                     with its first element dropped.

• A late, but relatively short answer. The sortest to be exactly. Well done! You win! Oct 29, 2020 at 18:20

# JavaScript (ES6),  111  110 bytes

n=>{for(g=n=>{for(d=n;n%--d;);},i=l=0;i--||(k=s=0,i=l++),n--;g[k]=s+=r=k)for(;g[++k]|g(!i*++s)|d>1;);return r}


Try it online!

# Jelly, 46 bytes

S©‘æR®Ḥ‘¤_®ḟ;F¥Ṃ
FLḤRḟFḣ0ịLƊ;ç¥µW
1;Ç\$⁸½Ḥ¤¡Fị@


Try it online!

Times out for large n on tio, but works there for all but the last two examples.

# Lua, 242228226 211 bytes

s={}u={}i=0 n=0+...while i<n do
n=n-i
x,S=1,0
for j=1,i do
while u[x]do x=x+1 end
s[j]=x
S=S+x
u[x]=0
end
while u[x]or p do
x=x+1
d=S+x
p=F
for c=2,d-1 do
p=p or d%c<1
end
end
i=i+1
s[i]=x
u[x]=0
end
print(s[n])
`

Try it online!