Re: Liczby Fibonacciego rzędu N

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming, pl.sci.matematyka
Subject	Re: Liczby Fibonacciego rzędu N
Date	2016-05-14 16:51 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<nh7e1r$ina$1@node1.news.atman.pl> (permalink)
References	<nh4std$qlq$1@node2.news.atman.pl> <nh4t8e$qve$1@node2.news.atman.pl> <almarsoft.852113119506661590@news.plus.net>

Cross-posted to 2 groups.

Show all headers | View raw

On 14.05.2016 11:10, Roman W wrote:
> On Fri, 13 May 2016 17:52:46 +0200, Borneq <borneq@antyspam.hidden.pl>
> wrote:
>> W dniu 13.05.2016 o 17:46, Borneq pisze:
>> > Co to są liczby Fibonacciego - wiadomo, ale co to są liczby
> Fibonacciego
>> > któregoś rzędu?
>> Już wiem, normalne inicjowane są dwiema jedynkami , inne większą
>> liczbą

Pomijasz najistotniejsze. Element ciągu jest sumą nie dwóch,
ale k poprzednich elementów.
Niby oczywiste, ale można przeoczyć.

>> jedynek, i tak dla trzech:
>> 1+1+1=3 1+1+3=5 1+3+5=9
>> co nam daje 1 1 1 3 5 9 17 31 57
>
> Czy istnieje rozwiązanie analityczne dla rzędu N > 4?

Rozwiązanie liniowej rekurencji sprowadza się do znalezienia
pierwiastków wielomianu. To dla n>4 bywa upierdliwe;-)

Wiemy, że rozwiązaniami podstawowymi są ciagi geometryczne.
q^k

(rozwiążaniem jest kombinacja liniowa takich rozwiązań podstawowych
spałniająca warunki początkowe)

które spełniają rekurencję:

a[n]+a[n+1]+..a[k-1] = a[k]

czyli
1 + q + q^2.. + q^(k-1) = q^k

q^k - q^(k-1) - q^2 - q - 1 = 0  (1)

(q^k-1)/(q-1) = q^k

q^k -1 = q^(k+1) - q^k

0 = q^(k+1) - 2 q^k  + 1

Dla k=2

(q^2-q-1)

pierwiastkami są fi i bar{fi}

Zgadza się.

Do rzeczy...  wielomian (1) wygląda ładnie, ale
pierwiasków oczywistych nie widać. Mathematica ich też nie widzi
dla k>4:(

Do ataku nemerycznego można użyć równoważnego

-(q^k-1)/(q-1) + q^k

lub ładniejszego ale z dodatkowym sztucznym pierwiastkiem równym 1

  q^(k+1) - 2 q^k + 1

Patrząc na te wykresy widać, że pierwiastki są
jeden w okolicy liczby 2
k-1 w okolicach (zespolonych) pierwiastków z jedynki (z pominięciem
samej jedynki).

To daje nam jakościowe oszacowanie, jak szybko ten ciąg rośnie,
ale pewnie chceilibyśmy go policzyć.
Dokładnie policzyć element nr 3535436743678357 ;-) Modulo
10^18 niech dla ulatwienia bedzie.
Jechanie rekurencją odpada, a wspołczynniki wzoru 'analitycznego'
znamy być możę nie dostatecznie dokładnie, aby wyzanczyć liczbę
jednosci.

Tu przydatna jest pewna sztuczka, używana już przy Fibonaccim.

Weźmy macierz
A =
[1 1 1 1 1 1 1 1]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 1 0]

Opisuje ona iterację stanu z naszego ciągu. Jeśli wsadzimy w nią wektor
an, an-1... dostaniemy wektor an+1,an...

Jeśli zaczniemy od wektora jednostkowego v=[1;1;1;1;1;1;1]

Pierwszym elementem wektora (A^n)v
będzie n+k ty element ciągu Fib.

A^n obliczami potęgowaniem binarnym, log(n) mnożęj, każde
po k^3 dzialań, łączny koszt O(log(n) k^3)

pzdr
bartekltg

Thread

Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:46 +0200
  Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-13 17:52 +0200
    Re: Liczby Fibonacciego rzędu N Roman W <bloody_rabbitREMOVETHIS@gazeta.pl> - 2016-05-14 10:10 +0100
      Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-14 16:51 +0200
      Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 03:55 +0200
        Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:23 +0200
          Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:29 +0200
            Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-15 04:40 +0200
              Re: Liczby Fibonacciego rzędu N peter <ToJestTo@nic.nie.wiem> - 2016-05-15 11:37 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 18:55 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:00 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:42 +0200
                Re: Liczby Fibonacciego rzędu N Borneq <borneq@antyspam.hidden.pl> - 2016-05-16 09:16 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 14:35 +0200
                Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-16 16:57 +0200
          Re: Liczby Fibonacciego rzędu N bartekltg <bartekltg@gmail.com> - 2016-05-15 14:26 +0200

csiph-web