Sekvensen är för meta

Leaky Nun 09/11/2017. 6 answers, 2.053 views
code-golf sequence

Vi börjar med en tom 1-indexerad sekvens:

_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,... 

I n: e steget fyller vi in ​​alla ett (n) ämne med heltal som är större än 1 och börjar med det första återstående blanket, där a (n) är n : n posten i sekvensen.

Efter det första steget:

2,_,3,_,4,_,5,_,6,_,7,_,8,_,9,_,10,_,11,_,12,_,13,_,... 

Observera att a (1) måste vara 2 eftersom det första heltalet som är större än 1 är 2.

I det andra steget fyller vi in ​​alla a (2) ämnen. Det kommer att framgå att a (2) måste vara 2.

2,2,3,_,4,3,5,_,6,4,7,_,8,5,9,_,10,6,11,_,12,7,13,_,... 

I det tredje steget fyller vi in ​​alla ett (3) ämne. Från sekvensen är a (3) = 3.

2,2,3,2,4,3,5,_,6,4,7,_,8,5,9,3,10,6,11,_,12,7,13,_,... 

I det fjärde steget fyller vi in ​​alla a (4) ämnen. Från sekvensen a (4) = 2.

2,2,3,2,4,3,5,2,6,4,7,_,8,5,9,3,10,6,11,3,12,7,13,_,... 

Så småningom:

2,2,3,2,4,3,5,2,6,4,7,2,8,5,9,3,10,6,11,3,12,7,13,2,... 

Uppgift

Med n, returnera n : n elementet i sekvensen.

De första 10.000.000 villkoren i sekvensen finns här .

Detta är . Kortaste svaret i byte vinner. Standard smutthål gäller.

5 Comments
Leaky Nun 06/20/2017
@LuisMendo Tack, jag har lagt till den.
Dead Possum 06/20/2017
Bara nyfiken, vilket fel gjorde mr.One att uteslutas från sekvens?
Leaky Nun 06/20/2017
@DeadPossum bra, om du fyller i var och en tom, så är du klar i ett steg.
2 Leaky Nun 06/20/2017
@DeadPossum Om a (n) är 1, fyller n-steget varje kvarvarande blank, vilket avslutar generationen.
1 Leaky Nun 06/20/2017
@QBrute Jag gav en lista över de första 10.000.000 kopplade i frågan; bara plotta dem.

6 Answers


Anders Kaseorg 06/20/2017.

Haskell , 80 67 byte

 g~(a:b)|let k!l=k:take(a-1)l++(k+1)!drop(a-1)l=2!g b
m=g m
(!!)$0:m 

Prova det online!

Haskell är det perfekta språket för att definiera en oändlig lista när det gäller sig själv.

5 comments
1 Julian Wolf 06/20/2017
Med tanke på att TIO-länken fungerar som förväntat, antar jag att min fråga borde istället vara: Kan du lägga till en förklaring till hur det fungerar?
2 Anders Kaseorg 06/20/2017
@JulianWolf Det låter som om du är obekant med let mönstervakter. pattern1 | let pattern2 = expr2 = expr1 pattern1 | let pattern2 = expr2 = expr1 betyder samma sak som pattern1 = let pattern2 = expr2 in expr1 (av samma skäl att [expr1 | let pattern2 = expr2] betyder samma sak som [let pattern2 = expr2 in expr1] ).
1 Ørjan Johansen 06/20/2017
Jag måste komma ihåg let mönstervakter (speciellt att de kan göra funktioner)! Dessutom är m=2:2:2`drop`g m en byte kortare.
1 Ørjan Johansen 06/20/2017
(!!)$0:m är två byte kortare.
1 Ørjan Johansen 06/20/2017
Faktum är att du kan släppa 2:2: saker helt med lite mer latskap: g ~(a:b)|... och m=g m .

Doorknob 06/20/2017.

C, 123 byte

 f(n)NO 

Prova det online!

genomgång

 f(n)NO 

genom kortslutning, och därefter av De Morgans lagar och det faktum att 0 är falsk i C:

 if (p[j] == 0 && ((k++) % p[i]) == 0) {
    p[j] = k / p[i] + 2;
} 

Detta anger väsentligen: "Om detta utrymme är tomt, öka k . Och om k tidigare var en multipel av stegstorleken, kör följande uttalande." Därför kör vi uttalandet på varje step size , vilket är exakt hur sekvensen beskrivs. Uttalandet i sig är enkelt; allt det gör är att generera 2 , 3 , 4 , ....

 n=p[n-1];} 

Med hjälp av den svåra återvändande utan retur som fungerar med gcc , returnerar vi det sista elementet av de första n termerna i sekvensen, vilket råkar vara nt termen.


Anders Kaseorg 06/20/2017.

Pyth, 29 bytes

M?tH?eJ.DtHg1GghG-tHhJ+2hJ2g1 

Prova det online

Hur det fungerar

Istället för att lura sig runt med listor använder den en vanlig rekursiv formel.

M                                def g(G, H):
 ?tH                                 if H - 1:
      J.DtHg1G                           J = divmod(H - 1, g(1, G))
    ?e                                   if J[-1]:
              ghG-tHhJ                       return g(G + 1, H - 1 - J[0])
                                         else:
                      +2hJ                   return 2 + J[0]
                                     else:
                          2              return 2
                           g1Q   print(g(1, eval(input()))) 

xnor 06/20/2017.

Haskell , 67 byte

 0%j=2
i%j|d<-div i$f j=last$d+2:[(i-d-1)%(j+1)|d*f j 

Prova det online!

En rekursiv aritmetisk lösning som visade sig i princip samma metod som Anders Kaseorgs Pyth-svar .

Denna kod är täckt av vårtor - fula delar som ser ut som om de kunde bli golfade bort, men jag såg inte hur.

Funktionen i%j vill verkligen använda en vakt för att kontrollera om mod i(f j)>0 och utvärdera ett av motsvarande två uttryck. Men båda uttrycken använder div i(f j) . Bindning som i ett vakt gör det inte tillämpligt på båda sidor. Såvitt jag vet kan en vakt inte göras för att "distribuera" över andra vakter. let och where är för långa. Så använder koden last att välja ett av två uttryck medan skyddet binder variabeln. Usch.

Helst skulle vi använda divMod eftersom både div och mod används, men (d,m)<-divMod ... är ett långt uttryck. Vi istället hackigt kolla på moden är nonzero genom att se om div värdet gånger divisorn saknar det ursprungliga värdet.

0%j=2 fallet skulle inte behövas om Haskell kortsluts div 0 , vilket det inte gör. .pred omvandlar den 1-indexerade ingången till nollindexerad, annars skulle det finnas -1 korrigeringar överallt.

4 comments
Ørjan Johansen 06/21/2017
Om du aktiverar % 1-indexerad behöver du fem bytekorrigering - som bara binder. Du kan emellertid inline f till % utan kostnad, och f blir anonym så att du sparar två byte totalt.
xnor 06/21/2017
@ ØrjanJohansen Vad menar du här med inline? Jag kan inte se hur man ändrar referenser till f utan att förlora byte.
Ørjan Johansen 06/21/2017
divMod verkar vara en byte billigare, eftersom det tillåter förgrening med !!(0^m) . Hittills har jag: 1%j=2;i%j|(d,m)<-divMod(i-1)$j%1=[(i-d-1)%(j+1),d+2]!!(0^m);‌​(%1)
Ørjan Johansen 06/21/2017
Som du ser, förutsätter inlining 1-reindexing, som tar bort .pred .

Arnauld 06/20/2017.

JavaScript (ES6), 98 93 91 byte

En rekursiv funktion som slutar så snart resultatet är tillgängligt.

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

Alternativ version, 90 byte

Suggested by Shaggy for -1 byte

Den här måste kallas med f(n)() . Även om motsvarande inlägg i meta för närvarande ger ett positivt betyg, är denna syntax uppenbarligen omtvistad.

 n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0)) 

demo

 f=(n,p,a=[...Array(n)])=>a[n-1]||f(n,-~p,a.map(c=>c?c:i?i++%(a[p]||2)?c:++v:(i=1,v=2),i=0))

for(n = 1; n <= 50; n++) {
  console.log('a[' + n + '] = ' + f(n));
} 

2 comments
Shaggy 06/20/2017
n=>g=(p,a=[...Array(n)])=>a[n-1]||g(-~p,a.map(c=>c?c:i?i++%k‌​?c:++v:(i=1,v=2),i=0‌​,k=a[p]||2)) borde fungera för 92 byte. Ring det med f(n)() .
Arnauld 06/20/2017
@Shaggy tack! Tillagt som en alternativ version.

Xanderhall 06/20/2017.

Java 8, 124 byte

(i)->{int j=1,a[]=new int[i+1],k,s,n;for(;a[i]<2;){for(k=0,n=2;a[++k]>0;);for(s=a[j++]|2*k;k<=i;k+=s)a[k]=n++;}return a[i];} 

Lambda uttryck.

Skapar ett heltal och fyller hela tiden tills nth-värdet blir befolket.

Fördeklarera variabler överst för att minska så många deklarationer som möjligt eftersom varje int kostar 4 byte av rymden i motsats till att lägga till ,n som är 2.

Vid den jätte iterationen av beräkningen måste antalet "blankor" som man måste hoppa över är lika med a[j] (eller 2, om blank). Det går ut att om det första tomma utrymmet vi måste fylla i är i k , får k * a[j] oss "steg" ( s ).

Related questions

Hot questions

Language

Popular Tags