Liczby Fibonacciego

Liczby Fibonacciego zaczynają się od f(1) = 1if(2) = 1 (niektórzy obejmuje f(0) = 0, ale to nie ma znaczenia do tego wyzwania. Następnie, dla n > 2, f(n) = f(n-1) + f(n-2).

Wyzwanie

Twoim zadaniem jest znalezienie i wydrukowanie pliku n -tej liczby dodatniej, którą można wyrazić jako iloczyn liczb Fibonacciego. Możesz wybrać opcję indeksowania 0 lub indeksowania 1, w zależności od tego, który bardziej Ci odpowiada, ale musisz to określić w swojej odpowiedzi.

Twoja odpowiedź musi również obliczyć 100. termin w rozsądnym czasie.

Przypadki testowe

n   result corresponding product (for reference)
1   1      1
2   2      2
3   3      3
4   4      2*2
5   5      5
6   6      2*3
7   8      2*2*2 or 8
8   9      3*3
9   10     2*5
10  12     2*2*3
11  13     13
12  15     3*5
13  16     2*2*2*2 or 2*8
14  18     2*3*3
15  20     2*2*5
16  21     21
17  24     2*2*2*3 or 3*8
18  25     5*5
19  26     2*13
20  27     3*3*3
100 315    3*5*21

Referencje

• Obowiązkowy OEIS A065108

Galaretka , 26 24 23 21 bajtów

ÆDf÷߀FðḊ¡
1ç#2+С1¤Ṫ

Wypróbuj online!

Jak to działa

1ç#2+С1¤Ṫ  Main link. Argument: n (integer)

        ¤   Combine the three links to the left into a niladic chain.
   2          Set the left argument and the return value to 2 (third positive
              Fibonacci number).
       1      Yield 1 (second positive Fibonacci number).
    +С       Compute the sum of the return value and right argument, replacing the
              return value with the sum and the right argument with the previous
              return value.
              Do this n times, collecting all return values in a list.
              This returns A, the first n Fibonacci numbers greater than 1.
1             Set the return value to 1.
 ç#           Call the helper link with left argument k = 1, 2, 3... and right
              argument A = [2, 3, 5...] until n of them return a truthy value.
              Collect the matches in a list.
           Ṫ  Tail; extract the last (n-th) match.


ÆDf÷߀FðḊ¡    Helper link. Left argument: k. Right argument: A

        Ḋ     Dequeue; yield r := [2, ..., k].
       ð ¡    If r in non-empty, execute the chain to the left. Return k otherwise.
ÆD              Yield the positive divisors of k.
   ÷            Divide k by all Fibonacci numbers in A.
  f             Filter; keep divisors that belong to k÷A, i.e., all divisors
                d for which k÷d belongs to A.
    ߀          Recursively call the helper link for each kept divisor d, with left
                argument d and right argument A.
      F         Flatten the result, yielding a non-empty array iff any of the
                recursive calls yielded a non-empty array or a number.
                If the left argument is 1, the helper link returns 1, so the
                array will be non-empty if the consecutive divisions by Fibonacci
                numbers eventually produced a 1.

Julia, 79 bajtów

!k=any(i->√(5i^2+[4,-4])%1∋k%i<!(k÷i),2:k)^~-k
<|(n,k=1)=n>0?n-!k<|-~k:~-k

Wypróbuj online!

tło

W Zaawansowanych problemach i rozwiązaniach H-187: Fibonacci jest kwadratem , o czym mówi wnioskodawca

gdzie L _n oznacza n- ^tą liczbę Lucasa i odwrotnie - jeśli

następnie n jest liczbą Fibonacciego, a m jest liczbą Lucasa.

Jak to działa

Definiujemy operatora binarnego <|do naszych celów. Nie jest zdefiniowane w najnowszych wersjach Julii, ale nadal jest rozpoznawane przez parser jako operator.

Gdy zostanie wywołany tylko z jednym argumentem ( n ), <|inicjuje k jako 1 . Chociaż n jest dodatnie, odejmuje ! K ( 1, jeśli k jest iloczynem liczb Fibonacciego, 0, jeśli nie) od n i rekurencyjnie wywołuje siebie, zwiększa k o 1 . Gdy n osiągnie wartość 0 , znaleziono żądaną liczbę produktów, więc <|zwraca poprzednią wartość k , tj. ~ -K = k - 1 .

Jeden operator !, na nowo zdefiniowany jako test dla produktów liczbowych Fibonacciego, spełnia swoje zadanie w następujący sposób.

• Jeśli k = 1 , k jest iloczynem liczb Fibonacciego. W tym przypadku zwiększamy wartość zwracaną any(...)do potęgi ~ -k = k - 1 = 0 , więc wynik będzie wynosił 1 .

• Jeśli k> 1 , wynikiem będzie wartośćany(....) , która zwróci wartość true wtedy i tylko wtedy, gdy predykat √(5i^2+[4,-4])%1∋k%i<!(k÷i)zwróci wartość true dla pewnej liczby całkowitej i takiej, że 2 ≤ i ≤ k .

  Warunki powiązane w łańcuchu predykatów są, jeśli k%inależą do √(5i^2+[4,-4])%1i k%isą mniejsze niż !(k÷i).

  • √(5i^2+[4,-4])%1bierze pierwiastek kwadratowy z 5i ² + 4 i 5i ² - 4 i oblicza ich reszty modulo 1 . Każdy moduł wynosi 0, jeśli odpowiednia liczba jest kwadratem idealnym, a liczba dodatnia mniejsza niż 1 w przeciwnym razie.

    Ponieważ k%izwraca liczbę całkowitą, może należeć do tablicy modułów tylko wtedy, gdy k% i = 0 (tj. K jest podzielne przez i ) i co najmniej jeden spośród 5i ² + 4 i 5i ² - 4 jest kwadratem idealnym (tj. i jest liczbą Fibonacciego).

  • !(k÷i)rekurencyjnie wywołuje 1 z argumentem k ÷ i (dzielenie całkowite), który będzie większy niż 0 wtedy i tylko wtedy, gdy k ÷ i jest iloczynem liczb Fibonacciego.

Przez indukcję ! ma pożądaną właściwość.

Python, 90 bajtów

f=lambda n,a=2,b=3:n<2or n%a<f(n/a)or n-a>0<f(n,b,a+b)
g=lambda k,n=1:k and-~g(k-f(n),n+1)

Główna funkcja ggeneruje kth produkt Fibonacciego, 1-indeksowany. Oblicza g(100)jak 315niemal natychmiast. Jest tak z ogólnym rekurencyjnym przepisem liczenia liczb w nposzukiwaniu kinstancji spełniających tę funkcję f. Każde takie wystąpienie obniża wymaganą liczbę, każ do osiągnięcia 0.

Funkcja pomocnicza fsprawdza liczbę jako produkt Fibonacciego. Rekurencyjnie generuje liczby Fibonacciego w opcjonalnych argumentach ai b. Zwraca „tak”, jeśli spełniony jest jeden z poniższych warunków:

• n<2. Oznacza to n==1, że trywialny produkt)
• n%a<f(n/a). Wymaga n%a==0a f(n/a)==True, czyli że njest wielokrotnością liczby Fibonacciego a, a usunięcie tego czynnikaa nadal daje produkt Fibonacciego.
• n-a>0<f(n,b,a+b), równoważne z n>a and f(n,b,a+b). Sprawdza, czy bieżąca testowana liczba Fibonacciego nie jest przynajmniej n, i działa pewna większa liczba Fibonacciego. Dzięki Dennisowi za 2 bajty oszczędnościowe zamiast zwarcia z nierównością and.

Funkcja gmoże być o jeden bajt krótsza jako

lambda k:filter(f,range(k*k+1))[k]

jeśli g(k)zawsze jest co najwyżej k*k, co nie jestem pewny, jest asymptotycznie prawdziwe. Granica 2**kwystarcza, ale potem g(100)trwa zbyt długo. Może zamiast tego gmożna wykonać rekurencję f.

Perl 6 ,  95  93 bajtów

{(1..*).grep({$/=$_;map {->{$/%$_||($//=$_);$/}...*!%%$_;0},reverse 2,3,&[+]...*>$_;2>$/})[$_]}
{(1..*).grep({$/=$_;map {->{$/%$_||($//=$_);$/}...*%$_;0},reverse 2,3,&[+]...*>$_;2>$/})[$_]}

(Indeks 0)

Test:

my &fib-prod = {(1..*).grep({$/=$_;map {->{$/%$_||($//=$_);$/}...*%$_;0},reverse 2,3,&[+]...*>$_;2>$/})[$_]}

say fib-prod 0 ..^ 20;
# (1 2 3 4 5 6 8 9 10 12 13 15 16 18 20 21 24 25 26 27)
say time-this { say fib-prod 100 -1; };
# 315
# 1.05135779

sub time-this (&code) {
  my $start = now;
  code();
  now - $start;
}

Wyjaśnienie:

{
  (1..*).grep(
    {
      $/ = $_; # copy the input ($_) to $/
      map { # map used just for side effect
        ->{
          $/ % $_    # if $/ is divisible by the current fib factor
        ||
          ($/ /= $_) # divide it out once
        ;
          # return the current value in $/
          $/
        }
        ... # repeat until that returns:
        * !%% $_ # something that is not divisible by the current fib factor
        ;0
      },
      # the possible fibonacci factors plus one, reversed
      # ( the extra is to save one byte )
      reverse 2,3,&[+] ... *>$_;

      # is the end result of factoring equal to 1
      # ( for the grep above )
      2 > $/
    }
  )[ $_ ] # get the value at 0-based index
}

Python 3, 175 170 148 bajtów

Dzięki @Dennis za -22 bajty

j=x=int(input())
y=1,1
exec('y+=y[-2]+y[-1],;'*x)
i=c=0
while c<x:
    if j>=x:j=0;i+=1;t=i
    if t%y[~j]<1:t/=y[~j];j-=1
    if t<2:c+=1;j=x
    j+=1
print(i)

Pobiera dane wejściowe ze STDIN i drukuje do STDOUT. Jest to jeden indeks. Obliczenie setnego terminu zajmuje około jednej dziesiątej sekundy.

Jak to działa

j=x=int(input())                Get term number x from STDIN and set Fibonacci number index
                                j to x to force initialisation of j later 
y=1,1                           Initialise tuple y with start values for Fibonacci sequence
exec('y+=y[-2]+y[-1],;'*x)      Compute the Fibonacci sequence to x terms and store in y
i=c=0                           Initialise test number i and term counter c
while c<x:                      Loop until x th term is calculated
    if j>=x:j=0;i+=1;t=i        Initialise Fibonacci number index j, increment i and
                                initialise temp variable t for looping through all j for
                                some i. Executes during the first pass of the loop since
                                at this point, j=x
    if t%y[~j]<1:t/=y[~j];j-=1  Find t mod the j th largest Fibonacci number in y and if no
                                remainder, update t by dividing by this number.
                                Decrementing j means that after a later increment, no
                                change to j occurs, allowing for numbers that are 
                                divisible by the same Fibonacci number more than once by
                                testing again with the same j
    if t<2:c+=1;j=x             If repeated division by ever-smaller Fibonacci numbers
                                leaves 1, i must be a Fibonacci product and c is
                                incremented. Setting j equal to x causes j to be reset
                                to 0 during the next loop execution
    j+=1                        Increment j
print(i)                        i must now be the x th Fibonacci product. Print i to STDOUT

Wypróbuj na Ideone

Python 2, 120 107 bajtów

g=lambda k:1/k+any(k%i==0<g(k/i)for i in F)
F=2,3;k=0;n=input()
while n:F+=F[k]+F[-1],;k+=1;n-=g(k)
print k

Przetestuj na Ideone .

Jak to działa

Inicjalizujemy F jako krotkę (2, 3) (pierwsze dwie liczby Fibonacciego większe niż 1 ), k jako 0 i n jako liczbę całkowitą odczytaną ze STDIN.

Chociaż n jest dodatnie, wykonujemy następujące czynności:

• Dołącza następna liczba Fibonacciego, obliczony jako F [K] + C [1] , to znaczy suma dwóch ostatnich elementów F na krotki F .

• Przyrost k .

• Odejmij g (k) od n .

g zwraca 1 wtedy i tylko wtedy, gdy k jest iloczynem liczb Fibonacciego, więc gdy n osiągnie 0 , k jest n- ^tą liczbą Fibonacciego i wypisujemy ją do STDOUT.

g osiąga swój cel w następujący sposób.

• Jeśli k wynosi 1 , jest to iloczyn liczb Fibonacciego i 1/kupewnia się, że zwracamy 1 .

• Jeśli k jest większe niż 1 , nazywamy g(k/i)rekurencyjnie dla wszystkich liczb Fibonacciego I w F .

  g(k/i)rekursywnie sprawdza, czy k / i jest iloczynem liczby Fibonacciego. Jeśli g(k/i)zwraca 1 i i dzieli równomiernie k , k% i = 0, a warunek pozostaje k%i<g(k/i), więc g zwróci 1 wtedy i tylko wtedy, gdy istnieje liczba Fibonacciego taka, że k jest iloczynem tej liczby Fibonacciego i innego iloczynu liczb Fibonacciego.

JavaScript (ES6), 136

W ten sposób grałem w golfa dość wolno, obliczając termin 100 w około 8 sekund na moim komputerze.

(n,F=i=>i>1?F(i-1)+F(i-2):i+1,K=(n,i=1,d,x)=>eval('for(;(d=F(i++))<=n&&!(x=!(n%d)&&K(n/d)););x||n<2'))=>eval('for(a=0;n;)K(++a)&&--n;a')

Mniej golfowy i szybszy (unikanie eval)

n=>{
  F=i=> i>1 ? F(i-1)+F(i-2) : i+1; // recursive calc Fibonacci number
  K=(n,i=1,d,x)=>{ // recursive check divisibility
    for(; (d=F(i++))<=n && !(x=!(n%d)&&K(n/d)); );
    return x||n<2
  };
  for(a=0; n; )
    K(++a) && --n;
  return a
}

Test

X=(n,F=i=>i>1?F(i-1)+F(i-2):i+1,K=(n,i=1,d,x)=>eval('for(;(d=F(i++))<=n&&!(x=!(n%d)&&K(n/d)););x||n<2'))=>eval('for(a=0;n;)K(++a)&&--n;a')

function test() {
  var i=+I.value
  O.textContent=X(i)
}

test()

<input id=I value=100 >
<button onclick="test()">Go</button><pre id=O></pre>

Haskell, 123 bajty

f=2:scanl(+)3f
m((a:b):c)=a:m(b?(a#c))
v#((a:b):c)|v==a=b?(v#c)
_#l=l
y?(z:e)|y>z=z:y?e
a?b=a:b
l=1:m[[a*b|b<-l]|a<-f]
(l!!)

Bardzo leniwy, nieskończony!

Być może nie jest to najkrótsza droga, ale musiałem wypróbować to podejście, uogólnienie dość dobrze znanej metody obliczania listy liczb hamujących. fjest listą liczb Fibonacciego zaczynającą się od 2. Dla zwięzłości powiedzmy, że lol (lista list) jest nieskończoną listą uporządkowanych nieskończonych list, uporządkowanych według ich pierwszych elementów. mjest funkcją scalania lol, usuwania duplikatów. Wykorzystuje dwie funkcje pomocnicze infix. ?wstawia nieskończoną posortowaną listę do lol. #usuwa wartość z LOL, która może pojawić się jako nagłówek pierwszych list, ponownie wstawiając pozostałą listę za pomocą ?.

Na koniec lznajduje się lista liczb, które są iloczynami liczb Fibonacciego, zdefiniowana jako 1, po której następuje scalenie wszystkich list uzyskanych przez pomnożenie przez lliczbę Fibonacciego. Ostatni wiersz podaje wymaganą funkcję (jak zwykle bez wiązania jej z nazwą, więc nie kopiuj jej w obecnej postaci), używając !!do indeksowania listy, co powoduje, że funkcja jest indeksowana.

Nie ma problemu z obliczeniem 100. lub 100 000. liczby.

Łuska , 13 bajtów

Zauważ, że Łuska jest nowsza od tego wyzwania. Jednak to i najbardziej przydatna funkcja dla tego golfa ( Ξ) nie zostały stworzone z myślą o tym wyzwaniu.

S!!Ṡ¡ȯuΞIṪ*İf

Wypróbuj online!

Bardziej wydajna wersja na 14 bajtów:

Wypróbuj online!

Python 2, 129 128 125 123 121 bajtów

g=lambda k:1/k|any(abs(round(5**.5*i)**2-5*i*i)==4>k%i<g(k/i)for i in range(k+1))
f=lambda n,k=1:n and f(n-g(k),k+1)or~-k

Przetestuj na Ideone .