4
$\begingroup$

I'm looking for an algorithm that is better than just checking every number in the Fib Sequence for divisibility.

Example: Find the first Fib number that is divisible by $x=223321$, with no remainders.

Answer: The $15720$th Fib Number, which is a $3285$ digit number.

I'm currently checking every digit, that gets to be too much too fast and makes it impossible to check larger numbers, like $x=1024240$.

Appreciate the read.

$\endgroup$
5
  • 1
    $\begingroup$ Do you know about the concept of modular arithmetic? The standard definition of the Fibonacci sequence can be run perfectly well $\bmod n$... $\endgroup$ – Steven Stadnicki Feb 14 '15 at 7:20
  • $\begingroup$ Already tried it, the numbers become much too large for a mod n program to run in a timely manner. $\endgroup$ – hogarth45 Feb 14 '15 at 7:31
  • 2
    $\begingroup$ Huh? If you do addition mod $n$, the number don't get any bigger than $n$. $\endgroup$ – bof Feb 14 '15 at 7:34
  • $\begingroup$ Are you saying to run a loop generating fib numbers then saying $Big Fib Num$ $mod$ $x$ $==$ $0$ $\endgroup$ – hogarth45 Feb 14 '15 at 7:38
  • $\begingroup$ @steven-stadnicki submit an answer so I can mark it as correct. $\endgroup$ – hogarth45 Feb 14 '15 at 7:44
9
$\begingroup$

Note first that it may help to factorise your large number if it is not prime. Here there is a fairly obvious factor $7$ ($203=210-7$) and you get $223321= 7 \times 31903$.

Now look at the Fibonacci Sequence modulo $7$, which goes $1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1 \dots$.

It is then easy to show that every eighth term is divisible by $7$. You will have to do less work if you know the theorem that if $F_1=F_2=1; F_{n+1}=F_n+F_{n-1}$ then $F_n\mid F_{kn}$.

Then you can use the same method with the second factor, which turns out to be $61 \times 523$. Then you know that the position in the sequence is divisible by $8$ and two other numbers - take the least common multiple to find the index.

So this gives lcm of $8, 15, 524$ which is $15720$


$1024240=2^4\times 5 \times 7 \times 31 \times 59$ so the index can be found a great deal more quickly using the factorisation.

So $16$ is a factor every $12^{th}$ number, $5$ gives $5$, $7$ gives $8$, $31$ gives $30$ and $59$ gives $58$.

So we need the least common multiple of $12,5,8,30,58$ - this makes it the $3480^{th}$ element of the sequence


Lemma $11$ of this paper shows that an odd prime divides one of $F_{p-1}, F_p, F_{p+1}$ and tells you which, and the paper gives information on how to compute the index when the prime factorisation is known.

To summarise $5\mid F_5$, and the option is $p-1$ where $p$ is congruent to $\pm 1 \bmod 5$, $p+1$ otherwise. But this need not be the least index for a prime, and doesn't deal with prime powers.

$\endgroup$
3
$\begingroup$

You can use the Fibonacci sequence mod 223321. When the sum gets to 0, that means it is divisible. A computer can easily do 1,000,000+ Fibonacci numbers in a few seconds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.