Loops: Fibonacci Greatest Common Divisors | Matlab Examples

Matlab Tutorials | Examples

Practice 6:

Loops: Fibonacci Greatest Common Divisors

The Fibonacci numbers are Nature’s numbering system. Given the first two Fibonacci numbers, f0=0 and f1=1, all remaining Fibonacci numbers can be derived iteratively by making use of the following formula:

f(n)= f(n-1) + f(n-2) The first few terms of the series goes as follows:

n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

fn

0

1

1

2

3

5

8

13

21

34

55

89

144

233

377

As the series goes to infinity, the ratio between adjacent terms converges to roughly 0.618034, an irrational number called the “golden ratio” or the “divine proportion.”

The Fibonacci sequence and the Golden Ratio appear in many systems around us, from the geometry of the DNA molecule (and the human body), to the physiology of plants and animals, even to the collective behaviour patterns of investors on financial markets. See http://www.world-mysteries.com/sci_17.htm for more information.

An interesting observation is that the greatest common divisor (GCD) of any two Fibonacci numbers appears to be another Fibonacci number. Look at the following examples:

gcd(f6, f9) = gcd(8, 34) = 2= f3 gcd(f6, f12) = gcd(8, 144) = 8= f6 gcd(f7, f14) = gcd(13, 377) = 13 = f7 gcd(f10, f7) = gcd(55, 13) = 1= f1

Write a MATLAB program that does the following:

  1. Gets two positive integer numbers, m and n from the user. If either number is not a positive integer, asks for that number again, until a proper value is given.
  2. Using loop constructs finds the mth and nth Fibonacci numbers fm and fn (do NOT use built-in MATLAB functions; do NOT utilize arrays).
  3. Finds the greatest common divisor of fm and fn, by making use of loop constructs (do NOT use built-in functions for finding the GCD or factoring the numbers; do not utilize arrays; use of basic functions such as MOD(), REM(), FLOOR(), etc. are permitted).
  1. Determines whether the GCD value is another Fibonacci number fk. If so, prints the k value on the screen, if not, displays “GCD property of Fibonacci numbers refuted!” (do NOT use built-in MATLAB functions; do NOT utilize arrays).
  2. Asks the user if s/he wants to try another pair. If yes, does the same operation again from step 1, otherwise quits the program.

 

Leave a Reply

Your email address will not be published. Required fields are marked *