Author |
Topic: Fabonacci that shares a common factor (Read 4542 times) |
|
MUKAY
Newbie
Posts: 3
|
 |
Fabonacci that shares a common factor
« on: Jun 21st, 2012, 1:20pm » |
 Quote  Modify
|
Given a number M, find the smallest Fibonacci number that shares a common factor( other than 1 ) with it. A number is said to be a common factor of two numbers if it exactly divides both of them.
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Fabonacci that shares a common factor
« Reply #1 on: Jun 22nd, 2012, 8:39am » |
Quote Modify
|
Just compute the fibonacci sequence until gcd(f_i,M)!=1. Gcd is fast enough.
To avoid large numbers, you can compute the f_i mod M. But you'll have to recompute the actual f_i afterwards.
|
|
IP Logged |
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Fabonacci that shares a common factor
« Reply #2 on: Jun 23rd, 2012, 4:30am » |
Quote Modify
|
It's not obvious to me that every prime number is a factor of some Fibonacci number.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Fabonacci that shares a common factor
« Reply #3 on: Jun 23rd, 2012, 1:32pm » |
Quote Modify
|
Well, you'd find quickly enough, because you're bound to repeat modulo M. So it's not like you'd go on forever. [e]From observation, it seem p divides F(p-1) or F(p+1) (which isn't to say that's the first one)[/e]
Aside from that, you bring a good idea to mind; using the prime decomposition of M and running Grimbal's algorithm on the distinct primes (rather than M) should generally be much faster.
|
| « Last Edit: Jun 23rd, 2012, 2:08pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
0.999...
Full Member
Gender:
Posts: 156
|
|
Re: Fabonacci that shares a common factor
« Reply #4 on: Jun 24th, 2012, 6:14pm » |
Quote Modify
|
Ah, now I see that such a Fibonacci number must exist for every prime (the first iteration and therefore every one of the cycle mod p satisfies Fk (-1)k+1*Fx-k where x is the length of a cycle). In fact, if x from the note above is a multiple of four then Fx/2 can be divided by p. Combined with my conjecture that for every odd prime p different from 5, x is either p-1 or 2(p+1) we have towr's observation.
|
|
IP Logged |
|
|
|
Saravana
Newbie
Gender:
Posts: 2
|
|
Re: Fabonacci that shares a common factor
« Reply #5 on: Jun 30th, 2012, 1:04am » |
Quote Modify
|
How about calculating first fibonaci which has common divisor ( n= GCD(a,fi) ) and then calculating the GCD(n,2 <=x<=n ).
That gives least common divisor between a fibonaci no and the given no(M)
|
|
IP Logged |
|
|
|
akasina9
Newbie
x = 0x2B | ~ 0x2B. x is the question
Gender:
Posts: 9
|
|
Re: Fabonacci that shares a common factor
« Reply #6 on: Nov 16th, 2012, 12:04am » |
Quote Modify
|
on Jun 30th, 2012, 1:04am, Saravana wrote:How about calculating first fibonaci which has common divisor ( n= GCD(a,fi) ) and then calculating the GCD(n,2 <=x<=n ).
That gives least common divisor between a fibonaci no and the given no(M) |
|
The question is about finding the lowest Fibonacci number, and not the lowest common divisor.
your solution finds the lowest common divisor between the number found and the given number, which is not required at all.
Consider M = 14. We'll get fi = 21, n = 7. Also, you'll get your lowest common factor as 7.
But in fact the lowest common factor between 14 and and fibonaaci number is 2. 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print