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

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


  • 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
  • \$\begingroup\$ Can we output the sequence infinitely, or return a generator instead? \$\endgroup\$
    – Jo King
    Commented Mar 27, 2019 at 23:45
  • 2
    \$\begingroup\$ Err, 1 is not a prime \$\endgroup\$
    – Jo King
    Commented Mar 27, 2019 at 23:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – agtoever
    Commented Mar 28, 2019 at 5:36
  • \$\begingroup\$ @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... \$\endgroup\$
    – agtoever
    Commented Mar 28, 2019 at 7:33
  • 4
    \$\begingroup\$ Related sequence: A075348. \$\endgroup\$
    – jimmy23013
    Commented Mar 28, 2019 at 7:51

7 Answers 7


Jelly, 32 bytes


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


Try it online!


{                                  }  # 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)

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)

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

  • 1
    \$\begingroup\$ I think you can remove the 0: as the challenge states you can use 0-based indexing. \$\endgroup\$
    – wastl
    Commented Mar 31, 2019 at 20:58

Husk, 22 bytes


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


!¡λḟ(Λ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
   ḟ                         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.
  • \$\begingroup\$ A late, but relatively short answer. The sortest to be exactly. Well done! You win! \$\endgroup\$
    – agtoever
    Commented 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


Try it online!

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


Lua, 242 228 226 211 bytes

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

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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