 mersenneforum.org > Math Fibonacci and Lucas factors
 Register FAQ Search Today's Posts Mark Forums Read  2009-02-15, 20:51 #1 Raman Noodles   "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts Fibonacci and Lucas factors I just came across an excellent relationship between the properties of factors of Mersenne and Fibonacci Numbers. It will quite be obvious for already experienced people, but it is the first time, that I am coming across this fact. Can someone please point out to me, the proofs of the following theorems: (1) A proof that the nth Fibonacci Number is given by the following formula: Or is there any formula to instantly calculate the nth Fibonacci Number without using any floating point arithmetic at all? (2) As for Cunningham numbers, we have This can be easily proved by factoring as follows: I noticed that the same property holds for the Fibonacci Numbers and the Lucas Numbers too. How to prove it up, right that way? (3) For Mersenne Numbers, we have that Any factor of the Mersenne number will always be of the form if n is prime. Also that for Fermat Numbers, Any factor of the Fermat Number will always be of the form I have good proofs of these theorems for Mersenne and Fermat Numbers. Similarly, I noticed that for Fibonacci Numbers, any factor of the nth Fibonacci Number, fn will always be of the form if n is prime. How to prove this fact? For the Lucas Numbers Is it so, only of the form if n is prime? (4) Finally, thus I will need so for a proof of the most important theorem, that is the Fibonacci pseudoprime test, that is: If n is prime, then Last fiddled with by Raman on 2009-02-15 at 20:54   2009-02-15, 21:29   #2

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts Quote:
 Originally Posted by Raman (1) A proof that the nth Fibonacci Number is given by the following formula: Or is there any formula to instantly calculate the nth Fibonacci Number without using any floating point arithmetic at all?
Well, if you simply carry in that form through the calculations, instead of substituting a floating-point approximation, you find that all the odd powers of cancel out and you're left with an integer. Quote:
 (2) As for Cunningham numbers, we have This can be easily proved by factoring as follows: I noticed that the same property holds for the Fibonacci Numbers and the Lucas Numbers too. How to prove it up, right that way?
The Fibonacci formula above can be restated as

where a, b, and c are constants.

Substitute for .

Last fiddled with by cheesehead on 2009-02-15 at 21:31   2009-02-15, 21:53   #3
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts Quote:
 Originally Posted by cheesehead Well, if you simply carry in that form through the calculations, instead of substituting a floating-point approximation, you find that all the odd powers of cancel out and you're left with an integer. What I meant was that, a fast Fibonacci calculator, such as this
could calculate fn instantly, for the values of n, as high as 20000000.
I asked what arithmetic (without floating point) was responsible
for calculating that value without examining all the previous
Fibonacci numbers.

You haven't given me the proof for the Fibonacci number formula from
the following recurrence relation, at all, at once:

Indeed, I would like to see so a proof for (3) & (4), of course.

Last fiddled with by Raman on 2009-02-15 at 22:00   2009-02-15, 22:00 #4 CRGreathouse   Aug 2006 32·5·7·19 Posts The Lucas sequences, I believe, have recurrences that allow calculating element 2n from elements n and n+1 (or n and n-1, I can't remember). The Fibonacci numbers are just a special case. The fast calculations formulas are based on these relations. Last fiddled with by CRGreathouse on 2009-02-15 at 22:00   2009-02-15, 22:31   #5
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts Quote:
 Originally Posted by CRGreathouse The Lucas sequences, I believe, have recurrences that allow calculating element 2n from elements n and n+1 (or n and n-1, I can't remember). The Fibonacci numbers are just a special case. The fast calculations formulas are based on these relations.
I agree so.

Hence, the proofs of (1), (3) & (4) are being pending so, thus.

Last fiddled with by Raman on 2009-02-15 at 22:32   2009-02-15, 23:29   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

22×3×641 Posts Quote:
 Originally Posted by Raman What I meant was that, a fast Fibonacci calculator, such as this could calculate fn instantly, for the values of n, as high as 20000000. I asked what arithmetic (without floating point) was responsible for calculating that value without examining all the previous Fibonacci numbers.
I was joking, or presuming use of Maple, Mathematica or some other such software that could handle symbols.   2009-02-16, 07:19   #7
wpolly

Sep 2002
Vienna, Austria

21910 Posts Quote:
 Originally Posted by Raman I agree so.
should be   2009-02-17, 12:53   #8
Raman
Noodles

"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts Quote:
 Originally Posted by wpolly should be
Of course. Indeed, so, to summarize up, only.

And then finally, these two are the formula that helps so to accelerate the calculations
of the Fibonacci and Lucas Numbers, by without using any floating point arithmetic tools at all, thus.

for even indices,
along with

for odd indices.

As it is up so for modular exponentiation:

Ok, that (1) can be proved so by Mathematical Induction, though I prefer
to see a proof for it, by using derivation. If in case, you don't know how
that form will be, how will you derive it so, starting up right from the scratch, thus?

I accept up so the proof for (2)

where

for Fibonacci Numbers, and

for Lucas Numbers.

What about for the other 2 cases, of them? Why is nobody responding up so to (3) & (4) as yet, at all, after this case? Thus, are people still ignoring towards me up so? Of course, right that way, thus.

Last fiddled with by Raman on 2009-02-17 at 13:10 Reason: The use of tools for subscription purposes.   2009-02-17, 18:14 #9 fivemack (loop (#_fork))   Feb 2006 Cambridge, England 13×491 Posts I'm not responding to you because of your tone of voice; you are sounding as if the people on this forum are your servants, ready to bring you freshly-baked proofs when you clap your hands. We're not.   2009-02-17, 20:35   #10
CRGreathouse

Aug 2006

32×5×7×19 Posts Quote:
 Originally Posted by fivemack I'm not responding to you because of your tone of voice; you are sounding as if the people on this forum are your servants, ready to bring you freshly-baked proofs when you clap your hands.
Maybe we're going about this wrong. Perhaps we should be giving suggestions about how to find a mathematician willing to consult on the problem?   2009-02-21, 22:25 #11 Raman Noodles   "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts I am not ordering you to give me the proofs. Just give me hints simply on how to go ahead with the problem. These proofs cannot be found out anywhere in the web. I have to proceed on with my college project work. After thorough analysis of the p+1 Factoring algorithm, I need the following proofs: It will also be useful for Lucas Lehmer Test and Lucas Lehmer Riesel too. (1) If p is prime, then prove that (2) These two are the main results. But, well and good if it can also be proved that: (3) Any factor of the Lucas Sequence Number will always be of the form or , if p is prime. I now realize that, In the Pollard's p-1 test Since , so, we have that, for any multiplier k. If , then We should then compute thus, to give away the factor p, where are the primes till the B-limit, and that In the William's p+1 factoring algorithm, somewhat acts as a hybrid p+1 and p-1 test. Sometimes acts as p+1 algorithm when Acts as p-1 algorithm if If , then So that, If , then Compute If , then Thus, If , then Compute Last fiddled with by Raman on 2009-02-21 at 22:32   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 9 2017-06-28 16:56 sweety439 And now for something completely different 17 2017-06-13 03:49 jocelynl Math 2 2010-09-23 21:32 robert44444uk Math 3 2007-05-19 07:15 geoff Factoring 13 2005-12-23 01:59

All times are UTC. The time now is 01:05.

Sat May 8 01:05:30 UTC 2021 up 29 days, 19:46, 0 users, load averages: 1.31, 1.46, 1.49