Wprowadzenie (może zostać zignorowane)

Umieszczenie wszystkich liczb dodatnich w regularnej kolejności (1, 2, 3, ...) jest trochę nudne, prawda? Oto szereg wyzwań związanych z permutacjami (przetasowaniami) wszystkich liczb dodatnich. To trzecie wyzwanie z tej serii (linki do pierwszego i drugiego wyzwania).

W tym wyzwaniu ułożymy liczby naturalne w rzędach o coraz większej długości w taki sposób, aby suma każdego rzędu była liczbą pierwszą. To, co wydaje mi się naprawdę niesamowite w tym, to to, że każda liczba naturalna ma miejsce w tym układzie. Żadne liczby nie są pomijane!

Ta wizualizacja tego układu wygląda następująco:

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.

Możemy odczytać elementy z rzędów w tym trójkącie. Pierwsze 20 elementów to: 1, 2, 3, 4, 5, 8, 6 , 7, 9, 15, 10, 11, 12, 13, 21, 14, 16, 17, 18, 19 ( tak, jest utwór New Order ukryty w tej sekwencji ).

Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie $a(n)$ dla danego $n$ jako danych wejściowych, gdzie $a(n)$ to A162371 .

Zadanie

Biorąc pod uwagę liczbę całkowitą $n$ , wypisz $a(n)$ w formacie liczb całkowitych.

$a(n)$ jest zdefiniowane jako$n$ ty element leksykograficznie najwcześniejszej permutacji liczb naturalnych, tak że, gdy jest widziany jako trójkąt odczytywany przez rzędy, dla n> 1 sumy rzędów są liczbami pierwszymi. Od pierwszego leksykograficznej permutacji liczb naturalnych startów 1, ( 1 ) jest 1. Należy pamiętać, że ta definicja A ( 1 ) = 1 i ( 1 ) jestniemuszą być pierwsza. To jest sekwencja OEISA162371.$a(1)$$a(1) = 1$$a(1)$

Uwaga: tutaj zakłada się indeksowanie 1; możesz użyć indeksowania opartego na 0, więc $a(0) = 1; a(1) = 2$ itd. Podaj to w swojej odpowiedzi, jeśli zdecydujesz się na to.

Przypadki testowe

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

Zasady

• Dane wejściowe i wyjściowe są liczbami całkowitymi (twój program powinien co najmniej obsługiwać dane wejściowe i wyjściowe w zakresie od 1 do 32767)
• Niepoprawne dane wejściowe (0, liczby zmiennoprzecinkowe, ciągi, wartości ujemne itp.) Mogą prowadzić do nieprzewidzianych wyników, błędów lub (nie) zdefiniowanego zachowania.
• Obowiązują domyślne reguły we / wy .
• Domyślne luki są zabronione.
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach

Galaretka , 32 bajty

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

Wypróbuj online! - bardzo wolno, ponieważ najpierw buduje n wierszy, dla szybszej wersji, która nie ma 37 bajtów tego wypróbować .

Perl 6 , 80 77 bajtów

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

Wypróbuj online!

Wyjaśnienie:

{                                  }  # 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 bajtów

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

Wypróbuj online!(ma dodatkowe 2 bajty f=)

EDYCJA: Teraz używa indeksowania opartego na 0, aby zapisać 2 bajty. Dzięki @wastl za zwrócenie na to uwagi, musiałem przegapić to w OP.

Pisanie tego było bardzo fajne! Funkcja pomocnika %wymaga długości li listy wartości, których może użyć a. Zwraca nieskończoną listę wartości dla sekwencji. Długość jest o jeden mniejsza niż długość bieżącego rzędu trójkątów, a lista jest nieskończona i wstępnie posortowana. Najpierw podajemy pierwsze lwartości, aa następnie przeglądamy resztę, aż znajdziemy pierwszą (najmniejszą) wartość, która sprawi, że suma będzie liczbą pierwszą. Rozbijamy listę wokół tej wartości za pomocą spani trochę dopasowania wzorca. Teraz wszystko, co musimy zrobić, to uzyskać tę nową wartość i powrócić do następnej długości linii l+1i pozostałych wartości w a. Aby uzyskać wynik końcowy, dodajemy 1 (specjalny przypadek dla n = 0) i indeksujemy do niego za pomocą !!.

JavaScript (ES6),  111  110 bajtów

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}

Wypróbuj online!

Galaretka , 46 bajtów

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

Wypróbuj online!

Przekroczono limit czasu dla dużego n na tio, ale działa tam dla wszystkich oprócz dwóch ostatnich przykładów.

Lua , 242 228 226 211 bajtów

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

Wypróbuj online!