New Order #3: 5 8 6

Question

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.

Task

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 code-golf, so the shortest answers in bytes wins

Answer 1

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.

Answer 2

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)

Answer 3

Haskell, 122 120 bytes

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

Answer 4

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.

Answer 5

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!

Answer 6

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.

Answer 7

Lua, 242 228 226 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!