wu :: forums « wu :: forums - Fabonacci that shares a common factor » Welcome, Guest. Please Login or Register. Sep 16th, 2024, 5:41am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Grimbal, Icarus, william wu, towr, Eigenray, SMQ, ThudnBlunder)    Fabonacci that shares a common factor « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Fabonacci that shares a common factor  (Read 4556 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board