tło

Większość z was wie, co to jest liczba Fibonacciego . Niektórzy z was mogą wiedzieć, że wszystkie dodatnie liczby całkowite mogą być reprezentowane jako suma jednej lub więcej wyraźnych liczb Fibonacciego, zgodnie z twierdzeniem Zeckendorfa . Jeśli liczba wyrażeń w optymalnej reprezentacji liczb całkowitych Zeckendorfa jest liczbą nFibonacciego, nazwiemy n„potajemnie” Fibonacciego.

Na przykład:

139 = 89 + 34 + 13 + 3
This is a total of 4 integers. Since 4 is not a Fibonacci number, 139 is not secretly Fibonacci

140 = 89 + 34 + 13 + 3 + 1
This is a total of 5 integers. Since 5 is a Fibonacci number, 140 is secretly Fibonacci

Notatki

• Optymalną reprezentację Zeckendorfa można znaleźć za pomocą chciwego algorytmu. Po prostu weź największą liczbę Fibonacciego <= n i odejmij ją od n, aż osiągniesz 0
• Wszystkie liczby Fibonacciego mogą być reprezentowane jako suma 1 liczby Fibonacciego (sama). Ponieważ 1 jest liczbą Fibonacciego, wszystkie liczby Fibonacciego są również potajemnie Fibonacciego.

Wyzwanie

Wyzwaniem jest napisanie programu lub funkcji, która przyjmuje liczbę całkowitą i zwraca, czy ta liczba całkowita jest potajemnie Fibonacciego.

Wkład

Możesz przyjmować dane wejściowe w dowolnym rozsądnym formacie. Możesz założyć, że wejście będzie pojedynczą dodatnią liczbą całkowitą.

Wydajność

Wyprowadź jeden z dwóch różnych wyników dla tego, czy dane wejściowe są potajemnie Fibonacciego. Przykłady obejmują True/ False, 1/ 0itd.

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach! Standardowe luki są zabronione.

Przypadki testowe

Truthy (secretly Fibonacci)
1
2
4
50
140
300099

Falsey (NOT secretly Fibonacci)
33
53
54
139
118808

JavaScript (Node.js) , 54 bajty

x=>g(g(x))<2;g=(x,i=1,j=1)=>j>x?x&&g(x-i)+1:g(x,j,i+j)

Wypróbuj online!

Python 2 , 77 bajtów

def f(n):z=[bin(x).count('1')for x in range(n*n+1)if x&2*x<1];print z[z[n]]<2

Wypróbuj online!

Wykorzystuje to twierdzenie, że dwa opisy OEIS A003714 są równoważne:

Liczby fibryfikacyjne: jeśli $n = F(i_1) + F(i_2) + \dots + F(i_k)$ jest reprezentacją $n$ Zeckendorfa (tj. Zapisujemy $n$ w systemie liczb Fibonacciego), to $a(n) = 2^{i_1} + 2^{i_2} + \dots + 2^{i_k}$ . Również liczby, których reprezentacja binarna nie zawiera dwóch sąsiadujących $1$„s.

Generujemy wystarczającą liczbę * takich liczb, a następnie wykorzystujemy zjako odwzorowanie liczb całkowitych nieujemnych na „ile wyrażeń reprezentuje $n$ ?

Następnie pozostaje sprawdzić, czy z[n]jest liczbą Fibonacciego, tj z[z[n]] == 1.

^{* Przynajmniej $n^2+1$ wydaje się wystarczające, a eksperymentalnie wydaje się wystarczające. Udowodnię to później.}

Galaretka , 15 bajtów

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị

Łącze monadyczne przyjmujące nieujemną liczbę całkowitą, która daje wartość 1„Secretly Fibonacci” i 0inaczej.

Wypróbuj online! (zbyt mało wydajny dla większych przypadków testowych)

W jaki sposób?

‘ÆḞ€fRṪạµƬL’Ɗ⁺Ị - Link: integer, I
        µƬ      - perform the monadic link to the left as a function of the current I,
                - collecting up all the inputs until the results are no longer unique:
‘               -   increment I -> I+1
 ÆḞ€            -   nth Fibonacci number for €ach n in [1,I+1]
     R          -   range from 1 to I
    f           -   filter discard (discard Fibonacci numbers not in the range, i.e. > I)
      Ṫ         -   tail (get the largest)
       ạ        -   absolute difference with I
                - This gives us a list from I decreasing by Fibonacci numbers to 0
                - e.g. for 88 we get [88,33,12,4,1,0]
                -      because (88-33)+(33-12)+(12-4)+(4-1)+(1-0)=55+21+8+3+1=88 
          L     - length (the number of Fibonacci numbers required plus one)
           ’    - decrement (the number of Fibonacci numbers required)
            Ɗ   - treat the last three links (which is everything to the left) as a monad:
             ⁺  - ...and repeat it
                - i.e. get the number of Fibonacci numbers required for the number of
                -      Fibonacci numbers required to represent I.
                -      This is 1 if I is Secretly Fibonacci, and greater if not)
              Ị - insignificant? (is the absolute value of that <= 1?)

R , 83 bajty

function(n){T=1:0
while(n>T)T=c(T[1]+T[2],T)
while(n){n=n-T[T<=n][1]
F=F+1}
F%in%T}

Wypróbuj online!

C # (.NET Core) , 124 115 98 bajtów

a=>{int n=0,b,c;for(;a>0;a-=b,n++)for(b=c=1;c<=a;b=c-b)c+=b;for(b=c=1;c<n;c+=b)b=c-b;return c==n;}

Wypróbuj online!

-3 bajty: zmieniono pętlę while na for (dzięki Olivier Grégoire )
-6 bajtów: zmieniono powrót do użycia zmiennej, zainicjowano b i c poza pętlami (dzięki Kevin Cruijssen )
-17 bajtów: zmieniono warunek w drugiej pętli, aby przejść, jeśli poza pętlą i łączymy ze zwracanymi, ponownie używanymi zmiennymi b i c w ostatniej pętli (dzięki raznagul )

Nie golfowany:

a => {
    int n = 0, b, c;                        // initialize variables

    for(; a > 0; a -= b, n++)               // increase n until a is 0
        for(b = c = 1; c <= a; b = c - b)   // set b and c to 1 for each a; set second largest Fibonacci number until largest Fibonacci number reaches a
            c += b;                         // set largest Fibonacci number of current sequence

    for(b = c = 1; c < n; c += b)           // while e is less than or equal to n, continue incrementing largest (e) Fibonacci number in the sequence
        b = c - b;                          // increment second-largest (d) Fibonacci number

    return c == n;                          // if c equals n, a is a secret Fibonacci number
}

Perl 6 , 58 bajtów

{(1,&[+]...*>$_)∋($_,{$^n-(1,&[+]...^*>$n).tail}...0)-1}

Wypróbuj online!

1, &[+] ... * > $_ jest po prostu sekwencją Fibonacciego, zatrzymaną w dogodnym nieskończonym miejscu (liczba wejściowa).

$_, { $^n - (1, &[+] ...^ * > $n).tail } ... 0jest ciągiem liczb, zaczynającym się od liczby wejściowej, i każdym kolejnym elementem uzyskanym przez odjęcie największej liczby Fibonacciego mniejszej lub równej poprzedniemu elementowi od poprzedniego elementu. Sekwencja kończy się, gdy 0zostanie osiągnięta. Na przykład, jeśli $_jest 140, to ta sekwencja jest 140, 51, 17, 4, 1, 0.

Odejmując jedną z tej sekwencji, traktujemy ją jako liczbę, jej długość, a różnicą jest liczba liczb Fibonacciego, które razem dodane dają liczbę wejściową. Następnie numer ten jest sprawdzany pod kątem członkostwa w pierwszej sekwencji Fibonacciego.

Perl 6 , 48 bajtów

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}

Wypróbuj online!

Przekształca dane wejściowe na listę Reprezentacji Zeckendorfa wielokrotnie, aż osiągnie jedną liczbę, a następnie sprawdza, czy długość sekwencji była mniejsza niż 4.

Środkowa funkcja Zenckendorf pochodzi głównie z odpowiedzi Seana z kilkoma ulepszeniami.

Wyjaśnienie:

{4>($_,{$_,{$_-(1,&[+]...*>$_)[*-2]}...^0}...1)}
{                                              } # Anonymous code block
                                          ...     # Define a sequence:
    $_  # That starts at the input
      ,{                                 }  # Each element is defined by:
                                   ... # Another sequence that:
        $_,   # Starts at the previous element
            $_-   # The previous element minus
                1,&[+]...*     # The Fibonacci sequence
                          >$_  # Ending when it is larger than the previous element
               (             )[*-2]  # The second from last element
          {                        }...^0  # Run until 0, discarding the last element
         # This returns the length of the Zeckendorf Representation
                                         ...1  # Run this until it is length 1
 4>(                                         )  # Return true if the length of the sequence is smaller than 4

Na przykład, sekwencja dla 2jest, 2 1ponieważ 2jest już liczbą Fibonacciego. Sekwencja dla 140jest 140 5 1, a ponieważ 5 jest liczbą Fibonacciego, zwraca wartość true. Sekwencja dla 33jest 33 4 2 1, a ponieważ 4nie jest liczbą Fibonacciego, sekwencja ma długość 4.

05AB1E , 14 bajtów

ΔDÅFθ-¼}¾ÅF¾<å

Wypróbuj online . Brak zestawu testów dla wszystkich przypadków testowych, ponieważ counter_variablenie można zresetować do zera. Jednak wszystkie ręcznie zweryfikowałem i są poprawne.

Wyjaśnienie:

Δ      }          # Loop until the top of the stack no longer changes
 D                #  Duplicate the top of the stack
                  #  (implicitly the input in the first iteration)
  ÅF              #  Get a list of all Fibonacci numbers lower than this number
    θ             #  Get the last item (largest one)
     -            #  Subtract it from the number
      ¼           #  Increase the counter_variable by 1 every iteration
        ¾         # After the loop, push the counter_variable
         ÅF       # Get all Fibonacci numbers below this counter_variable
           ¾<     # Push the counter_variable again, and subtract 1
             å    # Check if this value is in the list of Fibonacci numbers
                  # (and output implicitly)

UWAGA: counter_variableByłoby to 5dla danych wejściowych 139i 6danych wejściowych 140, ponieważ aby Δ-loop sprawdził, czy stos pozostaje taki sam, oczywiście wykonuje dodatkową iterację.

Haskell , 64 bajty

s=(<2).r.r
f=1:scanl(+)1f
r 0=0
r z=1+r(z-last(takeWhile(<=z)f))

Wypróbuj online!

Retina 0.8.2 , 61 bajtów

.+
$*
M`((?>\2?)(\1|\G.))*..|.
.+
$*
^(((?>\3?)(\2|^.))*.)?.$

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

.+
$*

Konwertuj na unary.

M`((?>\2?)(\1|\G.))*..|.

Policz liczbę potrzebnych liczb Fibonacciego.

Pierwsza alternatywa dotyczy liczb Fibonacciego, które są co najmniej 2. Przy pierwszym przejściu \2jeszcze nie istnieje, ale na szczęście jest opcjonalna, więc nie musimy jej dopasowywać. \1też nie istnieje, ale na szczęście mamy alternatywę, \G.która pasuje do jednej postaci na początku meczu. Oba \2i \1dlatego przyjmują wartość 1.

Po kolejnych przejściach \2istnieje, więc staramy się go dopasować. Tym razem, jeśli się nie powiedzie, to \1również się nie powiedzie (ponieważ jest większy niż \2), ale jeśli się powiedzie, (?>)zapobiega cofnięciu, więc jeśli \2pasuje, ale \1nie próbujemy tego \1. ( \G1zawsze kończy się niepowodzeniem, ponieważ przeszliśmy wcześniej od początku łatki.) W końcu \2przyjmuje poprzednią wartość parametru \1while \1przyjmuje sumę dwóch wartości.

Dlatego dopasowujemy jak najwięcej liczb Fibonacciego, jak to możliwe, dodając z biegiem czasu. Ponieważ częściowe sumy sekwencji 1, 2, 3, 5...są 0, 1, 3, 6, 11...tj. 2 mniejsze niż liczby Fibonacciego, kończymy dopasowując 2 na końcu.

To oczywiście nie pasuje do samego 1, więc alternatywa obsługuje tę skrzynkę.

.+
$*

Konwertuj na unary.

^(((?>\3?)(\2|^.))*.)?.$

Sprawdź, czy jest to liczba Fibonacciego. Wykorzystuje to ten sam pomysł, co w pierwszym teście, ale używa go ^zamiast \Gi musimy również dokładnie dopasować, więc używa opcjonalnego przechwytywania zamiast zmiany, ponieważ jest to bardziej golfistyczne (ale zwiększa liczbę przechwytywania o 1).

Siatkówka , 35 bajtów

.+
*
2}C`((?>\2?)(\1|\G.))*..|.
^1$

Wypróbuj online! Link zawiera przypadki testowe. Wyjaśnienie:

.+
*

Konwertuj na unary.

C`((?>\2?)(\1|\G.))*..|.

Policz liczbę potrzebnych liczb Fibonacciego. (Zapętlanie zarówno konwersji, jak i liczby oszczędza cały bajt przed uzyskaniem liczby pojedynczej).

2}

Wykonaj poprzednie kroki łącznie dwa razy. Pobiera to liczbę Fibonacciego potrzebną do zsumowania liczby Fibonacciego.

^1$

Jeśli liczba była potajemnie Fibonacciego, wynik wynosi 1.

Python 2 , 146 137 bajtów

lambda a:len(g(len(g(a))))<2
f=lambda n:n<3or f(n-2)+f(n-1)
def g(a,n=1):j=f(n-1);return[j]if a-j<1else[j]+g(a-j)if a-f(n)<0else g(a,n+1)

Wypróbuj online!

f () to funkcja rekurencyjna, która zwraca wartość n-tej liczby Fibonacciego. Zaczerpnięte z tej odpowiedzi .

g () jest funkcją rekurencyjną, która zwraca reprezentację Zeckendorfa podanej liczby jako listę liczb całkowitych.

Ponieważ wszystkie liczby Fibonacciego będą miały długość powrotu jednego elementu z g (), h () sprawdza, czy długość g () z g (n) == 1.

EDYCJA: Zapisano 9 bajtów dzięki nedla2004 . Ciągle zapominam, że lambdas nie zawsze są najlepszym rozwiązaniem ...