Κυριακή, 12 Ιανουαρίου 2014

Του Μπονάτσι γιος

Θυμίζω πως η γνωστή ,και παινεμένη άμα τε και ξακουστή, ακολουθία αριθμών Φιμπονάτσι (Fibonacci) ορίζεται αναδρομικά ως:
$F_{1} =1$ , $F_{2} =1$ 
και
$F_{ \nu +1} = F_{ \nu } + F_{ \nu -1}    \forall  \nu  \geq 2$
$α)$ Ποιος είναι  ο μικρότερος θετικός ακέραιος $ν$ για τον οποίο ο $F_{ \nu}$ τελειώνει σε $5$ μηδενικά;
$β)$ Αποδείξτε πως δυο τυχαίοι διαδοχικοί αριθμοί Φιμπονάτσι είναι μεταξύ τους πρώτοι. Δηλαδή δεν έχουν κοινούς παράγοντες, ή αλλιώς, ο Μ.Κ.Δ των $F_{ \nu}$ και $F_{ \nu+1}$ είναι το $1$.

8 σχόλια:

  1. β) Ας υποθέσουμε ότι δύο διαδοχικοί αριθμοί Φιμπονάτσι, ο F(n) και ο F(n+1) έχουν κάποιον κοινό διαιρέτη δ>1. O δ θα πρέπει να διαιρεί και τη διαφορά τους F(n+1)-F(n) = F(n-1). Αφού όμως ο δ διαιρεί τους F(n) και F(n-1), θα πρέπει, με ανάλογη συλλογιστική, να διαιρεί και τη διαφορά τους, δηλαδή τον F(n-2), ομοίως και τον F(n-3), κ.ο.κ. και τον F(1)=1. Καταλήγουμε επομένως σε άτοπο και άρα η αρχική υπόθεση δεν ισχύει.

    ΑπάντησηΔιαγραφή
    Απαντήσεις
    1. Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.

      Διαγραφή
    2. Ωραίο το επαγωγικό σου επιχείρημα Θανάση που "πάει πίσω" μέχρι τους 2 πρώτους αρ.Φιμπονάτσι ,κι αφού αυτοί είναι οι 1 και 1, με κ.παράγοντα το ένα , όντως αποδεικνύει το ζητούμενο στο β). Και ουσιαστικά τώρα (με κάποια διαπλάτυνση και διερεύνηση..) έχουμε έτοιμο το εργαλείο που λύνει και το πιο δύσκολο ζήτημα α)...

      Διαγραφή
    3. Λεπτομέρεια, αλλά μιας και το σχολίασες, να πω κάτι ακόμα: Το αναδρομικό επιχείρημα στέκει ακόμα κι αν το σταματήσουμε στον F2=1 (χωρίς δηλαδή να ανατρέξουμε περαιτέρω στον F1), αφού ήδη με τον F2 φτάσαμε στο άτοπο ένας αριθμός δ>1, εξ υποθέσεως, να διαιρεί τον 1.

      Διαγραφή
  2. Δεν έχω υπόψη μου και δυσκολεύομαι να σκεφτώ τον τρόπο που θα μπορούσε να αξιοποιηθεί το στοιχείο β) για να καταλήξει κανείς στην απάντηση του α), αλλά θα προσπαθήσω να δώσω μια απάντηση, η οποία, αν δε μου έχει ξεφύγει κάτι σημαντικό, καταλήγει τουλάχιστον σε ένα ν, για το οποίο ο F(ν) λήγει σε 5 μηδενικά.

    Αξιοποιώ μιαν άλλη ιδιότητα της ακολουθίας, σύμφωνα με την οποία ο F(κ*λ) είναι πολλαπλάσιος των F(κ) και F(λ), για οποιουσδήποτε θετικούς ακέραιους κ και λ.

    Ο F που ζητάμε είναι πολλαπλάσιος του 10^5 = 2^5*5^5.

    Ο μικρότερος F που είναι πολλαπλάσιος του 2^5 είναι ο F(24)=46368.
    Ο μικρότερος F που είναι πολλαπλάσιος του 5^5 είναι ο F(3125). Αυτόν μάλλον θα δυσκολευόσαστε να τον διαβάσετε ακόμα κι αν μπορούσα να τον γράψω σε δεκαδική βάση.

    Σύμφωνα με την πιο πάνω ιδιότητα, ο F(24*3125) = F(75000) είναι πολλαπλάσιος και του F(24) και του F(3125), άρα και του 2^5 και του 5^5 και, τελικά, του 10^5.

    Επομένως, ο αριθμός Φιμπονάτσι με σειρά ν=75000 λήγει σε 5 μηδενικά. Επιφυλάσσομαι για το αν είναι ο μικρότερος.

    ΑπάντησηΔιαγραφή
  3. Πολύ ωραία Θανάση! Μπράβο.
    Κάνω την αρχή για την απόδειξη.
    Είναι σχετικά απλό να αποδειχθεί με Επαγωγή πως αν ο $κ$ διαιρεί τον $ν$ τότε ο $Fκ$ διαιρεί τον $Fν$.
    Καθώς λοιπόν ο $F(3)=2$ και $F(5)=5$ τότε $F(15)=2*5=0mod10$
    Άρα ,αν ο τυχαίος $ν$ είναι πολλαπλάσιο του 15 ,ο $F(ν)$ θα είναι πολλαπλάσιος του 10.
    Ο πρώτος $ν$ για τον οποίον $F(15ν)$ είναι πολ/σιος του 100 είναι 10. Ο πρώτος $ν$ για τον οποίον $F(150ν)$ είναι πολ/σιος του
    1000 είναι $ν= 5$, και ο πρώτος v ώστε ο F(750ν)πολ/σιος του 10000 είναι 10. Αρα ο $F(7500)$ είναι ο πρώτος Φιμπονάτσι που τελειώνει σε $4$ μηδενικά... :-)

    ΑπάντησηΔιαγραφή
  4. Θα έβαζα στοίχημα ότι ο μικρότερος ν για τον οποίο ο F(7500*ν) είναι πολλαπλάσιος του 100.000 είναι ο 10. Έχει κάμποση ανηφόρα πάντως η απόδειξη και δεν ξέρω αν μπορεί να κόψει κανείς δρόμο.

    Ευχαριστώ Γιώργο, έτσι κι αλλιώς πολύ ωραίο το θέμα!

    ΑπάντησηΔιαγραφή
  5. Aπολαύστε κάποια (ούτε το Βολφραμάλφα τα βγάζει όλα,αλλίμονο!) από τα $15674$ ψηφία του αρ.Φιμπονάτσι τάξης $75000$
    Eμείς πάντως ,κι ας μην τα δείχνει το μηχανάκι.., τώρα ξέρουμε πως τα 5 τελευταία του είναι $0$ :-)
    http://www.wolframalpha.com/input/?i=fibonacci+number+75000

    ΑπάντησηΔιαγραφή