Nowe zamówienie nr 5: gdzie Fibonacci i Beatty spotykają się w Wythoff

16

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. Jest to piąte wyzwanie w tej serii (linki do pierwszego , drugiego , trzeciego i czwartego wyzwania).

W tym wyzwaniu spotkamy tablicę Wythoffa, która jest splecioną lawiną sekwencji Fibonacciego i sekwencji Beatty!

Te liczby Fibonacciego są prawdopodobnie dla większości z Was znany sekwencja. Biorąc pod uwagę dwie liczby początkowe i , następujące są podane przez: dla .F0F1FnFn=F(n1)+F(n2)n>2

Sekwencja Beatty , ponieważ parametr oznacza: dla . Jedną z właściwości sekwencji Beatty jest to, że dla każdego parametru r jest dokładnie jeden parametr s = r / (r-1) , tak że sekwencje Beatty dla tych parametrów są rozłączne i połączone ze sobą, obejmują wszystkie liczby naturalne z wyłączeniem 0 (np .: B ^ r \ cup B ^ {r / (r-1)} = \ Bbb {N} \ setminus \ {0 \} ).rBnr=rnn1rs=r/(r1)BrBr/(r1)=N{0}

Teraz nadchodzi zadziwiająca część: możesz stworzyć tablicę, w której każdy wiersz jest sekwencją Fibonacciego, a każda kolumna jest sekwencją Beatty. Ta tablica jest tablicą Wythoffa . Najlepsze jest to, że każda liczba dodatnia pojawia się dokładnie raz w tej tablicy! Tablica wygląda następująco:

   1    2    3    5    8   13   21   34   55   89  144 ...
   4    7   11   18   29   47   76  123  199  322  521 ...
   6   10   16   26   42   68  110  178  288  466  754 ...
   9   15   24   39   63  102  165  267  432  699 1131 ...
  12   20   32   52   84  136  220  356  576  932 1508 ...
  14   23   37   60   97  157  254  411  665 1076 1741 ...
  17   28   45   73  118  191  309  500  809 1309 2118 ...
  19   31   50   81  131  212  343  555  898 1453 2351 ...
  22   36   58   94  152  246  398  644 1042 1686 2728 ...
  25   41   66  107  173  280  453  733 1186 1919 3105 ...
  27   44   71  115  186  301  487  788 1275 2063 3338 ...
  ...

Element w wierszu m kolumnie n jest zdefiniowany jako:

Am,n={mφφ if n=1mφφ2 if n=2Am,n2+Am,n1 if n>2

gdzie φ to złoty współczynnik: φ=1+52 .

Jeśli podążymy za anty-przekątnymi tej tablicy, otrzymamy A035513 , który jest sekwencją docelową dla tego wyzwania (zauważ, że ta sekwencja jest dodawana do OEIS przez samego Neila Sloane !). Ponieważ jest to wyzwanie „czystej sekwencji”, zadaniem jest wyprowadzenie dla danego jako danych wejściowych, gdzie to A035513 .a(n)na(n)

Istnieją różne strategie, które możesz zastosować, aby dostać się do , co sprawia, że ​​wyzwanie (moim zdaniem) jest naprawdę interesujące.a(n)

Zadanie

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

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

Przypadki testowe

Input | Output
---------------
1     |  1
5     |  7
20    |  20
50    |  136
78    |  30
123   |  3194
1234  |  8212236486
3000  |  814
9999  |  108240
29890 |  637

Może być fajnie wiedzieć, że największym dla jesta(n)1n32767a(32642)=512653048485188394162163283930413917147479973138989971=F(256)2φ+F(255).

Zasady

  • Wejścia i wyjścia są liczbami całkowitymi
  • Twój program powinien co najmniej obsługiwać dane wejściowe w zakresie od 1 do 32767). Zauważ, że idzie w górę do 30 cyfr w tym zakresie ...a(n)
  • 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 , więc wygrywa najkrótsza odpowiedź w bajtach
agtoever
źródło
2
Co to jest tutaj odniesienie do nowego zamówienia?
Luis Mendo
2
@LuisMendo: lawina sekwencji Fibonacciego i Beatty, które tworzą tablicę Wythoffa ...
agtoever
Ach, zupełnie za tym tęskniłem! Teraz żałuję ...
Luis Mendo
1
Czy zmiennoprzecinkowa reprezentacja phi (lub rt (5)) i zastosowanie rekurencji spełni wymagania dotyczące zakresu?
Jonathan Allan
1
Proszę poprawić 9th przypadek testowy: to 999nie9999
J42161217

Odpowiedzi:

4

Galaretka , 27 24 bajtów

p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/

Wypróbuj online!

Łącze monadyczne z wykorzystaniem indeksowania 1. Dzięki @JonathanAllan za lepszy sposób uzyskiwania wiersza i kolumn z ni oszczędzania 3 bajtów. W najkrótszej formie jest zbyt wolny, aby mógł być większy w TIO, więc następujące Wypróbuj online! zmniejsza rozmiar początkowej listy wierszy i kolumn kosztem trzech bajtów.

Wyjaśnienie

p`                       | Cartesian product of the range from 1..input with itself   
  SÞ                     | Sort by sum
    ⁸ị                   | Find the tuple at the position indicated by the input - this is the row and column
      ð               ð/ | Start a new dyadic chain using the row as the left and column as the right argument
       ’                 | Increase the row by 1
        ;    ¥           | Concatenate to:
         ×Øp             |   row × φ
            Ḟ            |   rounded down
              ×     ¤    | Multiply this pair by
                  ÆḞ     |   the Fibonacci numbers at positions
               ⁹         |   column index and
                r‘       |   column index plus one
                     S   | sum

Uwaga: jest to oparte na opisie kodu Python na stronie OEIS.

Nick Kennedy
źródło
1
...×⁹r‘ÆḞ¤Sð/zapisuje jeden w wersji amalgamacji ( TIO )
Jonathan Allan
6

R , 143 130 124 123 bajtów

function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]}

Wypróbuj online!

T(n,1)=n1;T(n,0)=nϕ;T(n,k)=T(n,k1)+T(n,k2)splitskistnieje tylko po to, aby zapobiec wymuszeniu drop=Fargumentacji w m[-1:-2,]sprawie n=1.

Podziękowania dla Neila za wskazanie 1-bajtowego golfa.

R , 150 138 132 bajtów

function(n){T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]}

Wypróbuj online!

T(n,k)=Fib(k+1)nϕ+Fib(k)(n1)splitsnth

Dzięki Robinowi Ryderowi za T[2]=1podstęp w generowaniu sekwencji Fibonacciego.


Oba rozwiązania są wysoce nieefektywne, tworząc nxnmacierz (najprawdopodobniej) doubles, ponieważ R promuje integer(32-bit podpisany) doubleautomatycznie po przepełnieniu, ale drugie powinno być znacznie szybsze. Przyjmowanie njako bignum powinno działać automatycznie, przy użyciu połączenia gmp::as.bigz(n), gdyby utrata precyzji doublebyła niepokojąca, a wtedy byłby język R + gmp.

Giuseppe
źródło
Czy możesz użyć (1+5^.5)/2zamiast (.5+5^.5/2)?
Neil
@Neil ... tak, mogę. Dziękuję Ci! Tylko edytuję go do pierwszego, chyba że znajdę sposób na grę w golfa na drugim miejscu.
Giuseppe,
2

Galaretka , 30 bajtów

p`SÞ⁸ịð;Øp,²;\¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/

Wypróbuj online!
Jest to trochę powolne, ale ogromną poprawę wprowadzono z prefiksemḤ½Ċ(podwójne, pierwiastek kwadratowy, sufit), jak w tym zestawie testów .

Jonathan Allan
źródło
2
masz rację! 740496902jest wynikiem dla999
J42161217
Połączenie pierwszej części twojej i drugiej części daje 25 bajtów . Nie jestem pewien, który z nas powinien mieć połączoną wersję!
Nick Kennedy
@NickKennedy - fajnie, idź!
Jonathan Allan
2

Węgiel drzewny , 54 bajty

Nθ≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθF⁺²⁻θη⊞υΣ…⮌υ²I⊟υ

Wypróbuj online! Link jest do pełnej wersji kodu. 0-indeksowane. Używa tylko arytmetyki liczb całkowitych, więc działa dla dowolnych dużych wartości. Wyjaśnienie:

Nθ

Wejście q.

≔⁰ηW‹ηθ«≦⊕η≧⁻ηθ»

Oblicz antydiagonalny, odejmując coraz większe liczby q, co kończy się docelową liczbą wierszy m.

⊞υ¹Fθ⊞υ⁻⁺³ι§υ⊖§υι

Oblicz pierwsze m+1warunki A019446 , chociaż interesuje nas tylko mth.

⊞υθF⁺²⁻θη⊞υΣ…⮌υ²

Oblicz pierwsze n+4warunki uogólnionej serii Fibonacciego, która zaczyna się od [a(m), m]. Terminy tej sekwencji są mterminami A019446 , A001477 , A000201 , A003622 , A035336 ; te dwie ostatnie są pierwszymi dwiema kolumnami tablicy Wythoffa, a zatem sekwencja ta jest kontynuowana wraz z resztą trzeciego mrzędu tablicy.

I⊟υ

Podaj żądany termin.

Neil
źródło