Introduction (peut être ignoré)

Mettre tous les nombres positifs dans son ordre régulier (1, 2, 3, ...) est un peu ennuyeux, n'est-ce pas? Voici donc une série de défis autour des permutations (remaniements) de tous les nombres positifs. Il s'agit du troisième défi de cette série (liens vers les premier et deuxième défis).

Dans ce défi, nous allons organiser les nombres naturels en rangées de longueur croissante de telle sorte que la somme de chaque ligne soit un nombre premier. Ce que je trouve vraiment étonnant à ce sujet, c'est que chaque nombre naturel a sa place dans cet arrangement. Aucun numéro n'est ignoré!

Cette visualisation de cet arrangement ressemble à ceci:

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.

Nous pouvons lire les éléments des lignes de ce triangle. Les 20 premiers éléments sont: 1, 2, 3, 4, 5, 8, 6 , 7, 9, 15, 10, 11, 12, 13, 21, 14, 16, 17, 18, 19 ( oui, il y a une chanson de New Order cachée dans cette séquence ).

Puisqu'il s'agit d'un défi de "séquence pure", la tâche consiste à sortir $a(n)$ pour un $n$ donné en entrée, où $a(n)$ est A162371 .

Tâche

Étant donné une entrée entière $n$ , sortie $a(n)$ au format entier.

$a(n)$ est défini comme le$n$ ième élément de la permutation lexicographiquement la plus ancienne des nombres naturels de sorte que, lorsqu'il est vu comme un triangle lu par des lignes, pour n> 1, les sommes des lignes sont des nombres premiers. Puisque la première permutation lexicographique des nombres naturels commence par 1,$a(1)$ est 1. Notez que selon cette définition,$a(1) = 1$ et$a(1)$ n'estpastenu d'être premier. Il s'agit de la séquence OEISA162371.

Remarque: l'indexation basée sur 1 est supposée ici; vous pouvez utiliser une indexation basée sur 0, donc $a(0) = 1; a(1) = 2$ , etc. Veuillez le mentionner dans votre réponse si vous choisissez de l'utiliser.

Cas de test

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

Règles

• L'entrée et la sortie sont des entiers (votre programme devrait au moins prendre en charge l'entrée et la sortie dans la plage de 1 à 32 767)
• Une entrée non valide (0, flottants, chaînes, valeurs négatives, etc.) peut entraîner une sortie imprévue, des erreurs ou un comportement (non) défini.
• Règles d'E / S par défaut s'appliquent.
• Les failles par défaut sont interdites.
• Il s'agit de code-golf , donc les réponses les plus courtes en octets l'emportent

Gelée , 32 octets

;®»ṀƊSÆn_S
ẎṀ©+LRḟẎḣL;Ç$ṭ
1Ç¡Fị@

Essayez-le en ligne! - très lent car il construit n lignesabord, pour une version plus rapide qui n'a pas, à 37 octets, essayez ceci .

Perl 6 , 80 77 octets

{({$!=@_;+(1...{$_∉$!&&(|$!,$_).rotor(1..*).one.sum.is-prime-1})}...*)[$_]}

Essayez-le en ligne!

Explication:

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

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

Essayez-le en ligne! (a 2 octets supplémentaires pourf= )

EDIT: utilise désormais l'indexation basée sur 0 pour économiser 2 octets. Merci @wastl de l'avoir signalé, je dois l'avoir manqué dans le PO.

C'était très amusant à écrire! La fonction d'assistance %prend une longueur let une liste de valeurs qu'elle peut utiliser a. Il renvoie une liste infinie de valeurs pour la séquence. La longueur est inférieure de un à la longueur de la ligne triangulaire actuelle et la liste est infinie et pré-triée. D'abord, nous produisons simplement les premières lvaleurs de apuis regardons le reste de a jusqu'à ce que nous trouvions la première (la plus petite) valeur qui rend la somme première. Nous divisons la liste autour de cette valeur en utilisant spanune correspondance de modèle. Maintenant, tout ce que nous avons à faire est de produire cette nouvelle valeur et de se reproduire avec la longueur de ligne suivante l+1et les valeurs restantes dans a. Pour le résultat final, nous ajoutons 1 (cas particulier pour n = 0) et l'indexons avec !!.

JavaScript (ES6),  111  110 octets

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}

Essayez-le en ligne!

Gelée , 46 octets

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

Essayez-le en ligne!

Expire pour les gros n sur tio, mais fonctionne pour tous les exemples sauf les deux derniers.

Lua , 242 228 226 211 octets

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

Essayez-le en ligne!