Sekwencja Sylwestra


32

Sekwencja Sylvester, OEIS A000058 , jest sekwencją całkowitą zdefiniowaną następująco:

Każdy członek jest produktem wszystkich poprzednich członków plus jeden. Pierwszym członkiem sekwencji jest 2.

Zadanie

Utwórz najmniejszy możliwy program, który zajmuje n i oblicza n-ty ciąg Sekwensu Sylwestra. Obowiązują standardowe wejścia, wyjścia i luki. Ponieważ wynik rośnie bardzo szybko, nie należy oczekiwać, że którykolwiek z terminów spowoduje przepełnienie w wybranym języku.

Przypadki testowe

Możesz użyć zerowania lub jednego indeksowania. (Tutaj używam indeksowania zerowego)

>>0
2
>>1
3
>>2
7
>>3
43
>>4
1807

Jakie dane wejściowe powinny być obsługiwane? Wydajność rośnie dość szybko.
Geobits

1
@Geobits, z którymi masz do czynienia tak dużo, jak potrafi Twój język
Wheat Wizard

Czy tablica, która po zindeksowaniu nzwraca nthnumer sekwencji, jest akceptowana?
user6245072,

@ user6245072 Nie, musisz indeksować własne tablice
Wheat Wizard

Odpowiedzi:


26

Brain-Flak , 76 68 58 52 46 bajtów

<>(()())<>{({}[()])<>({({}[()])({})}{}())<>}<>

Wypróbuj online!

Zamiast tego używa tej relacji:

formuła

który pochodzi z tej relacji zmodyfikowanej na podstawie tej podanej w sekwencji:

a(n+1) = a(n) * (a(n) - 1) + 1.

Wyjaśnienie

Aby uzyskać dokumentację tego, co robi każde polecenie, odwiedź stronę GitHub .

W Brain-Flak są dwa stosy, które nazywam odpowiednio stosem 1 i stosem 2.

Dane wejściowe są przechowywane w Stosie 1.

<>(()())<>             Store 2 in Stack 2.

{                      while(Stack_1 != 0){
  ({}[()])                 Stack_1 <- Stack_1 - 1;
  <>                       Switch stack.
  ({({}[()])({})}{}())     Generate the next number in Stack 2.
  <>                       Switch back to Stack 1.
}

<>                     Switch to Stack 2, implicitly print.

Dla algorytmu generowania:

({({}[()])({})}{}())      Top <- (Top + Top + (Top-1) + (Top-1) + ... + 0) + 1

(                  )      Push the sum of the numbers evaluated in the process:

 {            }               while(Top != 0){
  ({}[()])                        Pop Top, push Top-1    (added to sum)
          ({})                    Pop again, push again  (added to sum)
                              }

               {}             Top of stack is now zero, pop it.
                 ()           Evaluates to 1 (added to sum).

Alternatywna wersja 46-bajtowa

Używa tylko jednego stosu.

({}<(()())>){({}<({({}[()])({})}{}())>[()])}{}

Wypróbuj online!


1
Jeszcze tylko 10 bajtów, aby pokazać, że twórcy java powinni przejść do mózgu
Rohan Jhunjhunwala

1
@RohanJhunjhunwala Obawiam się, że to niemożliwe ...
Leaky Nun

@LeakyNun wciąż warto o tym myśleć. Brain Flak ma pewną moc i jest zaskakująco zwięzły
Rohan Jhunjhunwala

5
Wersja z jednym stosem jest również czysta. Co wydaje się być ważnym punktem dla modułowości kodu w przypadku flakingu mózgu.
Wheat Wizard

Łał. To niezwykle imponująca odpowiedź.
DJMcMayhem


12

Sześciokąt , 27 bajtów

1{?)=}&~".>")!@(</=+={"/>}*

Rozłożony:

    1 { ? )
   = } & ~ "
  . > " ) ! @
 ( < / = + = {
  " / > } * .
   . . . . .
    . . . .

Wypróbuj online!

Wyjaśnienie

Rozważmy sekwencję b(a) = a(n) - 1i zróbmy małą aranżację:

b(a) = a(n) - 1
     = a(n-1)*(a(n-1)-1) + 1 - 1
     = (b(n-1) + 1)*(b(n-1) + 1 - 1)
     = (b(n-1) + 1)*b(n-1)
     = b(n-1)^2 + b(n-1)

Ta sekwencja jest bardzo podobna, ale możemy odroczyć przyrost do samego końca, co powoduje zapisanie bajtu w tym programie.

Oto kod źródłowy z adnotacjami:

wprowadź opis zdjęcia tutaj
Utworzono za pomocą HexagonyColorer Timwi .

A oto schemat pamięci (czerwony trójkąt pokazuje początkową pozycję i orientację wskaźnika pamięci):

wprowadź opis zdjęcia tutaj
Utworzono za pomocą EsotericIDE firmy Timwi .

Kod zaczyna się na szarej ścieżce, która otacza lewy róg, więc początkowy bit liniowy jest następujący:

1{?)(
1      Set edge b(1) to 1.
 {     Move MP to edge N.
  ?    Read input into edge N.
   )(  Increment, decrement (no-op).

Następnie kod uderza w <gałąź, która wskazuje początek (i koniec) głównej pętli. Dopóki krawędź N ma wartość dodatnią, zielona ścieżka będzie wykonywana. Ta ścieżka owija się wokół siatki kilka razy, ale w rzeczywistości jest całkowicie liniowa:

""~&}=.*}=+={....(

Nie .ma operacji, więc rzeczywisty kod to:

""~&}=*}=+={(
""             Move the MP to edge "copy".
  ~            Negate. This is to ensure that the value is negative so that &...
   &           ...copies the left-hand neighbour, i.e. b(i).
    }=         Move the MP to edge b(i)^2 and turn it around.
      *        Multiply the two copies of b(i) to compute b(i)^2.
       }=      Move the MP back to edge b(i) and turn it around.
         +     Add the values in edges "copy" and b(i)^2 to compute
               b(i) + b(i)^2 = b(i+1).
          ={   Turn the memory pointer around and move to edge N.
            (  Decrement.

Po zmniejszeniu Ndo 0tej wartości wykonywana jest czerwona ścieżka:

")!@
"     Move MP back to edge b(i) (which now holds b(N)).
 )    Increment to get a(N).
  !   Print as integer.
   @  Terminate the program.

Czy potrafisz na tym uruchomić swojego bruteforcera?
CalculatorFeline,

@CalculatorFeline Brutalny forcer potrafi w rozsądnym czasie wykonać co najwyżej 7-bajtowe programy (a nawet tylko z kilkoma założeniami). Nie widzę, aby było to możliwe zdalnie w 7 bajtach.
Martin Ender

Więc? Co jest złego w próbowaniu?
CalculatorFeline,

@CalculatorFeline Lenistwo. Brutalny forcer zawsze wymaga drobnej ręcznej modyfikacji, której nie mogę sobie pozwolić na praktycznie zerową szansę, że coś znajdzie. Niektóre wersje skryptu są jednak dostępne na GitHub, więc każdy może je wypróbować.
Martin Ender,

Jak mam to zrobić?
CalculatorFeline

9

J, 18 14 12 bajtów

Ta wersja dzięki randomra. Później postaram się napisać szczegółowe wyjaśnienie.

0&(]*:-<:)2:

J, 14 bajtów

Ta wersja dzięki milom. Użyłem przysłówka mocy ^:zamiast programu, jak poniżej. Więcej wyjaśnień w przyszłości.

2(]*:-<:)^:[~]

J, 18 bajtów

2:`(1+*/@$:@i.)@.*

0-indeksowane.

Przykłady

   e =: 2:`(1+*/@$:@i.)@.*
   e 1
3
   e 2
7
   e 3
43
   e 4
1807
   x: e i. 10
2 3 7 43 1807 3263443 10650056950807 113423713055421862298779648 12864938683278674737956996400574416174101565840293888 1655066473245199944217466828172807675196959605278049661438916426914992848    91480678309535880456026315554816
   |: ,: x: e i. 10
                                                                                                        2
                                                                                                        3
                                                                                                        7
                                                                                                       43
                                                                                                     1807
                                                                                                  3263443
                                                                                           10650056950807
                                                                              113423713055421862298779648
                                                    12864938683278674737956996400574416174101565840293888
165506647324519994421746682817280767519695960527804966143891642691499284891480678309535880456026315554816

Wyjaśnienie

Oto program, który wygląda następująco:

           ┌─ 2:
           │    ┌─ 1
       ┌───┤    ├─ +
       │   └────┤           ┌─ / ─── *
── @. ─┤        │     ┌─ @ ─┴─ $:
       │        └─ @ ─┴─ i.
       └─ *

(Otrzymanej po zastosowaniu (9!:7)'┌┬┐├┼┤└┴┘│─'czym 5!:4<'e')

Rozkład:

       ┌─ ...
       │
── @. ─┤
       │
       └─ *

Używając górnej gałęzi jako gerunda G, a dolnej jako selektora F, jest to:

e n     <=>     ((F n) { G) n

Wykorzystuje funkcję stałą 2:kiedy 0 = * n, to znaczy, gdy znak jest równa zero (a więc njest zero). W przeciwnym razie korzystamy z tego widelca:

  ┌─ 1
  ├─ +
──┤           ┌─ / ─── *
  │     ┌─ @ ─┴─ $:
  └─ @ ─┴─ i.

Który stanowi jeden plus następująca seria:

            ┌─ / ─── *
      ┌─ @ ─┴─ $:
── @ ─┴─ i.

Rozkładając się dalej, jest to iloczyn produktu ( */) w porównaniu z odniesieniem własnym ( $:) w stosunku do zakresu ( i.).


2
Możesz również użyć przysłówka mocy, aby uzyskać 2(]*:-<:)^:[~]14 bajtów przy użyciu formuły a(0) = 2i a(n+1) = a(n)^2 - (a(n) - 1). Aby obliczyć większe wartości, 2na początku trzeba będzie zaznaczyć jako rozszerzoną liczbę całkowitą.
mile

Oba rozwiązania są bardzo miłe. Myślę, że nie byłem świadomy v`$:@.uformatu rekurencyjnego. Zawsze korzystałem z ^:vformatu, który często jest bardziej złożony. @miles Nigdy też nie użyłem tej (]v)sztuczki. Zrozumienie tego zajęło mi dobre 5 minut.
randomra

1
Dla kompletności trzeci rodzaj zapętlenia (14 bajtów metodą mil): 2(]*:-<:)~&0~](lub 2:0&(]*:-<:)~]). I łącząc je 13 bajtów ]0&(]*:-<:)2: .
randomra

12 bajtów: 0&(]*:-<:)2:. (Przepraszam, nie powinienem grać w golfa w komentarzach.)
randomra

@randomra To naprawdę miłe użycie więzi. Musiałem przeczytać stronę, aby dowiedzieć się dokładnie, co się stało, ponieważ normalnie można by pomyśleć, że czasownik środkowy otrzymuje trzy argumenty.
mil

9

Perl 6 , 24 bajtów

{(2,{1+[*] @_}...*)[$_]}
{(2,{1+.²-$_}...*)[$_]}

Wyjaśnienie

# bare block with implicit parameter 「$_」
{
  (
    # You can replace 2 with 1 here
    # so that it uses 1 based indexing
    # rather than 0 based
    2,

    # bare block with implicit parameter 「@_」
    {
      1 +

      # reduce the input of this inner block with 「&infix:<*>」
      # ( the input is all of them generated when using a slurpy @ var )
      [*] @_

      # that is the same as:
      # 「@_.reduce: &infix:<*>」
    }

    # keep calling that to generate more values until:
    ...

    # forever
    *

  # get the value as indexed by the input
  )[ $_ ]
}

Stosowanie:

my &code = {(2,{1+[*] @_}...*)[$_]}

say code 0; # 2
say code 1; # 3
say code 2; # 7
say code 3; # 43
say code 4; # 1807

# you can even give it a range
say code 4..7;
# (1807 3263443 10650056950807 113423713055421844361000443)

say code 8;
# 12864938683278671740537145998360961546653259485195807
say code 9;
# 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443
say code 10;
# 27392450308603031423410234291674686281194364367580914627947367941608692026226993634332118404582438634929548737283992369758487974306317730580753883429460344956410077034761330476016739454649828385541500213920807

my $start = now;
# how many digits are there in the 20th value
say chars code 20;
# 213441

my $finish = now;
# how long did it take to generate the values up to 20
say $finish - $start, ' seconds';
# 49.7069076 seconds

Kawałek tablicy z $_? Co to za czary?
Zaid

8

Haskell, 26 bajtów

f n|n<1=2|m<-f$n-1=1+m*m-m

Przykład użycia: f 4-> 1807.


7

Java 7, 46 42 bajtów

int f(int n){return--n<0?2:f(n)*~-f(n)+1;}

Używa indeksowania 0 ze zwykłą formułą. Zamieniłem n*n-nna n*(n-1)chociaż, ponieważ Java nie posiada poręczną operatora energii, a f()rozmowy były coraz długo.


3
f(n)*~-f(n)powinno działać.
Dennis

1
Jak zapomnieć o tej sztuczce za każdym razem ? Jeśli nie ma tego na stronie ze wskazówkami, to na pewno będzie.
Geobits

2
return--n<0oszczędza jeszcze jeden bajt.
Dennis





5

Brain-Flak , 158 154 bajtów

Dziurawa Zakonnica mnie tu pobiła

({}<(()())>){({}[()]<<>(())<>([]){{}<>({}<<>(({}<>))><>)<>({<({}[()])><>({})<>}{})<>{}([])}{}<>({}())([]){{}({}<>)<>([])}{}<>>)}{}([][()]){{}{}([][()])}{} 

Wypróbuj online!

Wyjaśnienie

Umieść dwa pod wejściem a (0)

({}<(()())>) 

Gdy wartość wejściowa jest większa od zera, odejmij jedną od wartości wejściowej i ...

{
({}[()]

Bezgłośnie...

<

Umieść jeden na drugim stosie, aby działał jako katalizator mnożenia <> (()) <>

Podczas gdy stos nie jest pusty

 ([])
 {
  {}

Przesuń górę listy i skopiuj

  <>({}<<>(({}<>))><>)

Pomnóż katalizator przez kopię

  <>({<({}[()])><>({})<>}{})<>{}
  ([])
 }
 {}

Dodaj jeden

 <>({}())

Przenieś sekwencję z powrotem na właściwy stos

 ([])
 {
 {}
 ({}<>)<>
 ([])
 }
 {}
 <>
>)
}{}

Usuń wszystkie oprócz dolnego elementu (tj. Ostatni utworzony numer)

([][()])
{
{}
{}
([][()])
}
{}

5

C, 32 bajty

f(n){return--n?f(n)*~-f(n)+1:2;}

Wykorzystuje indeksowanie 1. Przetestuj na Ideone .



5

R, 44 42 41 bajtów

2 bajty oszczędzają dzięki JDL

1 bajt zapisany dzięki user5957401

f=function(n)ifelse(n,(a=f(n-1))^2-a+1,2)

1
Z opisu problemu nie wynika jasno, ale o ile nnie jest to warunek ujemny, warunek można zredukować z n>0do just n.
JDL

@JDL Nicea! Dzięki !
Mamie

f(n-1)ma 6 bajtów. Myślę, że oszczędzasz bajt, przypisując go do czegoś. tj.ifelse(n,(a=f(n-1))^2-a+1,2)
user5957401,

5

Oaza , 4 bajty (niekonkurujące)

Prawdopodobnie mój ostatni język z rodziny golfistów! Nie konkuruje, ponieważ język jest późniejszy niż wyzwanie.

Kod:

²->2

Alternatywne rozwiązanie dzięki Zwei :

<*>2

Wersja rozszerzona:

a(n) = ²->
a(0) = 2

Wyjaśnienie:

²    # Stack is empty, so calculate a(n - 1) ** 2.
 -   # Subtract, arity 2, so use a(n - 1).
  >  # Increment by 1.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online!


Ostatni język golfa? Nie zamierzasz więcej robić? D:
Conor O'Brien

@ ConorO'Brien Prawdopodobnie teraz nie mam pomysłów :(
Adnan

Zanim spojrzałem na to wyzwanie, b<*>2skorzystałem za(n-1)*(a(n-1)+1)-1
Zwei

@Zwei Very schludny! Możesz faktycznie pominąć, bponieważ zostanie to automatycznie wypełnione (zamiast danych wejściowych) :).
Adnan

1
Tak, zauważyłem to po opublikowaniu. Dziwi mnie, jak dobrze ten język działa w tym celu, mimo że jest przeznaczony do sekwencji.
Zwei

3

Python, 38 36 bajtów

2 bajty dzięki Dennisowi.

f=lambda n:0**n*2or~-f(n-1)*f(n-1)+1

Ideone to!

Zamiast tego używa tej relacji zmodyfikowanej w stosunku do podanej w sekwencji:

a(n+1) = a(n) * (a(n) - 1) + 1

Wyjaśnienie

0**n*2zwraca 2kiedy n=0i gdzie 0indziej, ponieważ 0**0jest zdefiniowany jako 1Python.


3

Cheddar , 26 bajtów

n g->n?g(n-=1)**2-g(n)+1:2

Wypróbuj online!

Całkiem idiomatycznie.

Wyjaśnienie

n g ->    // Input n, g is this function
  n ?     // if n is > 1
    g(n-=1)**2-g(n)+1   // Do equation specified in OEIS
  : 2     // if n == 0 return 2

Teraz 4 razy (prawie)
Leaky Nun

Dlaczego usunąłeś link TIO?
Leaky Nun

@LeakyNun oh, musiałeś edytować podczas gdy ja byłem
Downgoat





2

Galaretka , 7 bajtów

²_’
2Ç¡

Wypróbuj online!

Zamiast tego używa tej zależności podanej w sekwencji: a(n+1) = a(n)^2 - a(n) + 1

Wyjaśnienie

2Ç¡   Main chain, argument in input

2     Start with 2
  ¡   Repeat as many times as the input:
 Ç        the helper link.


²_’   Helper link, argument: z
²     z²
  ’   z - 1
 _    subtraction, yielding z² - (z-1) = z² - z + 1

2

C, 46 bajtów

s(n,p,r){for(p=r=2;n-->0;p*=r)r=p+1;return r;}

Ideone to!

Służy pjako tymczasowe przechowywanie produktu.

Zasadniczo zdefiniowałem dwie sekwencje p(n)oraz r(n), gdzie r(n)=p(n-1)+1i p(n)=p(n-1)*r(n).

r(n) jest wymaganą sekwencją.


1
Czy jest jakiś powód, dla którego nie używasz tej samej relacji z odpowiedzi w Pythonie? To powinno być o wiele krótsze ...
Dennis

@Dennis To jest bardziej interesujące.
Leaky Nun

@Dennis I tę odpowiedź można przenieść
Leaky Nun

2

R, 50 46 44 bajtów

    n=scan();v=2;if(n)for(i in 1:n){v=v^2-v+1};v

Zamiast śledzić całą sekwencję, po prostu śledzimy produkt, który przestrzega podanej kwadratowej reguły aktualizacji, o ile n> 1 n> 0. (Sekwencja ta wykorzystuje „zaczynają się od jednego zera” konwencją)

Korzystanie z konwencji początkowej zerowej pozwala zaoszczędzić kilka bajtów, ponieważ możemy użyć if (n) zamiast if (n> 1)


2

Meduza , 13 bajtów

p
\Ai
&(*
><2

Wypróbuj online!

Wyjaśnienie

Zacznijmy od podstaw:

(*
<

To jest hak, który definiuje funkcję f(x) = (x-1)*x.

&(*
><

To składa się z poprzedniego haka z funkcją przyrostu, więc daje nam funkcję g(x) = (x-1)*x+1.

\Ai
&(*
><

Na koniec generuje to funkcję, hktóra jest iteracją poprzedniej funkcji g, tyle razy ile podano na wejściu liczb całkowitych.

\Ai
&(*
><2

I na koniec, zastosujemy tę iterację do wartości początkowej 2. U pgóry po prostu drukuje wynik.

Alternatywa (także 13 bajtów)

p
>
\Ai
(*
>1

To odracza przyrost do samego końca.


2

C, 43 , 34 , 33 bajtów

1-indeksowany:

F(n){return--n?n=F(n),n*n-n+1:2;}

Test główny:

int main() {
  printf("%d\n", F(1));
  printf("%d\n", F(2));
  printf("%d\n", F(3));
  printf("%d\n", F(4));
  printf("%d\n", F(5));
}

2

Brachylog , 13 bajtów

0,2|-:0&-y+*+

Wypróbuj online!

Zamiast tego używa tej relacji:

formuła

który pochodzi z tej relacji zmodyfikowanej na podstawie tej podanej w sekwencji:

a(n+1) = a(n) * (a(n) - 1) + 1.


2

Mathematica, 19 bajtów

Nest[#^2-#+1&,2,#]&

Lub 21 bajtów:

Array[#0,#,0,1+1##&]&

ArrayRoztwór magiczne. Szkoda, ##0to nie jest rzecz. ;)
Martin Ender


1

Faktycznie , 14 12 bajtów

Użyto 0-indeksowania. Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

2#,`;πu@o`nF

Ungolfing:

2#              Start with [2]
  ,`     `n     Take 0-indexed input and run function (input) times
    ;           Duplicate list
     πu         Take product of list and increment
       @o       Swap and append result to the beginning of the list
           F    Return the first item of the resulting list

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.