16
\$\begingroup\$

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 , so the shortest answers in bytes wins
\$\endgroup\$
  • \$\begingroup\$ Can we output the sequence infinitely, or return a generator instead? \$\endgroup\$ – Jo King Mar 27 at 23:45
  • 2
    \$\begingroup\$ Err, 1 is not a prime \$\endgroup\$ – Jo King Mar 27 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 Mar 28 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 Mar 28 at 7:33
  • 4
    \$\begingroup\$ Related sequence: A075348. \$\endgroup\$ – jimmy23013 Mar 28 at 7:51
4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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

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

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!

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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