All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Fibo and GCD (Posted on 2013-05-02) Difficulty: 3 of 5
Prove:
The GCD (greatest common divisor) of any two Fibonacci numbers: is also a Fibonacci number!
Derive:
A formula for GCD(fm, fn).
What is the GCD(f6, f21)?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts a table | Comment 1 of 2

The headings at the top and side show m (or n) and F(m) (or n). The body contains the GCD.

            1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
            1   1   2   3   5   8  13  21  34  55  89 144 233 377 610 987
  1     1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
  2     1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
  3     2   1   1   2   1   1   2   1   1   2   1   1   2   1   1   2   1
  4     3   1   1   1   3   1   1   1   3   1   1   1   3   1   1   1   3
  5     5   1   1   1   1   5   1   1   1   1   5   1   1   1   1   5   1
  6     8   1   1   2   1   1   8   1   1   2   1   1   8   1   1   2   1
  7    13   1   1   1   1   1   1  13   1   1   1   1   1   1  13   1   1
  8    21   1   1   1   3   1   1   1  21   1   1   1   3   1   1   1  21
  9    34   1   1   2   1   1   2   1   1  34   1   1   2   1   1   2   1
 10    55   1   1   1   1   5   1   1   1   1  55   1   1   1   1   5   1
 11    89   1   1   1   1   1   1   1   1   1   1  89   1   1   1   1   1
 12   144   1   1   2   3   1   8   1   3   2   1   1 144   1   1   2   3
 13   233   1   1   1   1   1   1   1   1   1   1   1   1 233   1   1   1
 14   377   1   1   1   1   1   1  13   1   1   1   1   1   1 377   1   1
 15   610   1   1   2   1   5   2   1   1   2   5   1   2   1   1 610   1
 16   987   1   1   1   3   1   1   1  21   1   1   1   3   1   1   1 987
 17  1597   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 18  2584   1   1   2   1   1   8   1   1  34   1   1   8   1   1   2   1
 19  4181   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 20  6765   1   1   1   3   5   1   1   3   1  55   1   3   1   1   5   3
 21 10946   1   1   2   1   1   2  13   1   2   1   1   2   1  13   2   1
 22 17711   1   1   1   1   1   1   1   1   1   1  89   1   1   1   1   1
 23 28657   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
 24 46368   1   1   2   3   1   8   1  21   2   1   1 144   1   1   2  21
 25 75025   1   1   1   1   5   1   1   1   1   5   1   1   1   1   5   1

produced by

   10    dim Fib(25)
   20    Fib(1)=1:Fib(2)=1
   30    for I=3 to 25
   40      Fib(I)=Fib(I-2)+Fib(I-1):print Fib(I);
   50    next I:print
   60    print gcd(Fib(6),Fib(21))
   65     print "         ";:for I=1 to 16:print using(4,0),I; next:print
   66     print "         ";:for I=1 to 16:print using(4,0),Fib(I); next:print:print
   70    for Row=1 to 25
   75     print using(3,0),Row;:print using(6,0),Fib(Row);
   80     for Col=1 to 16
   90        print using(4,0),gcd(Fib(Row),Fib(Col));
  100     next:print
  110    next

Edited on May 3, 2013, 12:26 am
  Posted by Charlie on 2013-05-03 00:25:28

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information