Brain Teaser #92: Solve Fibonacci Puzzle

  • Thread starter davilla
  • Start date
  • Tags
    Brain
In summary: NateTG has proven that the Fibonacci sequence mod n must be a single loop, so if we assume that the first repeated state is not 1,1, then every other state must be a loop, too.In summary, NateTG has shown that the Fibonacci sequence mod n must be a single loop, and that the first repeated state must not be 1,1.
  • #1
davilla
88
0
Brain Thumper #6

Find the smallest positive integer that does not evenly divide any Fibonacci number in the sequence starting 1, 1, 2, 3, 5, 8, 13, 21, etc.
 
Last edited:
Physics news on Phys.org
  • #2
disregarding dividing by 1, could the smallest positive integer be 11?
 
  • #3
catch.yossarian said:
disregarding dividing by 1
1 evenly divides a Fibonacci number (in fact it divides every Fibonacci number) so there's no reason to list it as an exception.


catch.yossarian said:
could the smallest positive integer be 11?
Sorry, 11 divides the tenth Fibonacci number, 55.
 
  • #4
There are no suitable numbers.

Let's assume, for a moment that there is some number, n with the desired property. Then we can look at the Fibonacci numbers modulo that number.

Since there are at most n different residues, and the state of the fibonacci sequence is determined by two consecutive values, there are at most [tex]n^2[/tex] states that the fibonacci sequence can be in.

Moreover, if I have [tex]F_k[/tex] and [tex]F_{k+1}[/tex] I know that [tex]F_{k-1}=F_{k+1}-F_{k}[/tex] for [tex]k>2[/tex] - so at any particular location (barring the start), the sequence is determined in both directions.

Now, since the number of possible states is finite, the sequence must, at some point, return to a state that it previously had, and because the sequence is deterministic in both directions, you have that the sequence mod n must be a single loop.

Now, in order loop back to the start [tex]1,1[/tex] the sequence must eventually get to [tex]-1,1,0...[/tex].

Since the sequence hits a value that is zero mod [tex]n[/tex] n divides some of the numbers.

In more concrete terms, given some [tex]n>0[/tex] there is at least one Fibonacci number in the first [tex]n^2[/tex] fibonacci numbers that is divisible by [tex]n[/tex].
 
  • #5
Nate, please define the term state as you are using it in your proof.
 
  • #6
is it the number 89?
 
  • #7
NateTG with the point!

In computer science, state is a term for the configuration of a program or an abstract computing machine at a given point in time as the collection of all of its data values. With analogous components, the meaning is the same in electrical engineering.

For a mathematician, the proof might be easier to understand using existential instantiation. There are only finitely many pairs (F(k), F(k+1)) mod n, so for some k there must be a j > k such that F(j) = F(k) and F(j+1) = F(k+1), mod n. Inductively we can prove that F(j+i) = F(k+i) mod n for every i where the expression is defined. Hence F(j-k) = 0 mod n.
 
Last edited:
  • #8
I'm missing something here. How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

For example, F(5) = 1, mod 4 and F(6) = 0, mod 4. I think you're saying that we know that there must be some j>5 such that F(j) = 1, mod 4 and F(j+1) = 0, mod 4. But how do we know that? (Or is that not what you are saying at all?)

I don't doubt that NateTG's conclusion is correct. I'm just having trouble following the proof.
 
Last edited:
  • #9
gnome said:
How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

NateTG concludes that "the sequence mod n must be a single loop" based on determinism of the minimal state, a consecutive pair of Fibonacci numbers mod n. If you consider a directed graph where each node is a state, determinism in both directions means that there's no branching forward or backward, so the only possibility for a finite graph is a loop.

In the variation I gave, it wasn't assumed that every pair (F(k), F(k+1)) mod n that occurs is repeated. This turns out to be the case, of course, but from the fact that there are a finite number, we only know that some pair must be repeated somewhere: "for some k there must be a j" such that j is a repeat of k. The induction with i must be carried backwards.
 
Last edited:
  • #10
gnome said:
I'm missing something here. How can we assume that every pair (F(k), F(k+1)) mod n is necessarily repeated simply because there is a finite number of pairs? How do we know that there isn't one such pair that is never repeated?

There are pairs that never occur. For example, every pair of consecutive fibonacci numbers is coprime, so the state 0,0 never occurs mod any number greater than 1.

There are a finite number of states that the finbonnaci sequence can be in, so at some point, it must repeat a state. (Where states are consecutive pairs.) Obviously once it's repeated, it's stuck in the loop.

Now, let's assume that the first repeated state is not 1,1. Then we can look at the first two occurances of a,b. So we have
1,1...a,b...a,b
where none of the ...'s contain a,b or 1,1
Now, consider that you can go to the left from the left hand a,b, since you know the sequence is ...b-a,a,b and then ...2a-b,b-a,a and then ...3a-2b,2a-b,b-a. But then we have the situation that that sequence (going to the left) gets to 1,1 before it gets to a,b for the first ... and gets to a,b before it gets to 1,1 on the second ... This is a contradiction, since the sequences must be the same.

Therefore, the first repeated state must be 1,1.
 
  • #11
gnome said:
Nate, please define the term state as you are using it in your proof.

In that context, I mean pairs of consecutive values of the Fibonacci numbers.

If you would like, here's a clearer proof using a directed graph as davilla suggested:

Let's assume, by contradiction, that some n with the desired property exists.

Now, construct a directed graph with [tex]n^2[/tex] nodes, and an arbitrary bijection from the ordered pairs [tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex] to the nodes in this graph. So now I can refer to vertices as [tex]v_{(a,b)} [/tex] with [tex] (a,b) \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]. Then place edges from each vertex [tex]v_{(a,b)}[/tex] to the vertex [tex]v_{(b,a+b)}[/tex] (Where the addition is mod n).

Let's call this the Fibonacci mod n state graph.

By construction there is only one edge out of any vertex.

Now, given an arbitrary vertex [tex]v_{(a,b)}[/tex] the only vertex that has an edge to that vertex is [tex]v_{(b-a,a)}[/tex] (with subtraction mod n).

That means that every vertex has only one line in, and one line out.

Now, traveling along these edges starting with [tex]v_{(1,1)}[/tex] gives consecutive values of the Fibonacci sequence. Since there is a finite number of vertices, and an infinite number of values in the FIbonacci squenece, the path must eventually loop.

Now, let's assume that the first repeated vertex is not [tex]v_{(1,1)}[/tex]. Then there must be two edges leading into that vertex. One from the path from [tex]v_{(1,1)}[/tex] to that vertex, and another for the path from that vertex to itself (we know that the two are disjoint because this vertex is the first repeated vertex), but this contradicts that there is only one edge into any vertex. Therefore, the first repeated vertex is [tex]v_{(1,1)}[/tex].

This means that the fibonacci sequence mod n eventually hits ...,1,1 but that means that the fibonnaci sequence also hits ...,0,1,1 so there is a fibonacci number divisible by n./
 
Last edited:
  • #12
Thanks very much for the explanations. I can follow the first. I follow the second in the sense that I can visualize a graph which I think is the graph you are describing. But my understanding of notation leaves much to be desired.

Does this
>>[tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]

mean the same as this:
given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i ≤ n and 0 < j ≤ n ?​

As to the node you refer to as
>>
[tex]v_{(a,b)} (a,b) \in\mathbb{Z}_n[/tex]

can I interpret that as follows:
given two consecutive fibonacci numbers fa, fb and some integer n, in your node (a,b), a = fa mod n and b = fb mod n?​


But I'm puzzled by your child nodes [tex]v_{(a,a+b)}[/tex]. Did you mean to write [tex]v_{(b,a+b)}[/tex]? If not, then I must be misunderstanding the meaning of [tex]v_{(a,b)}[/tex]
so please help me out.
 
  • #13
gnome said:
Thanks very much for the explanations. I can follow the first. I follow the second in the sense that I can visualize a graph which I think is the graph you are describing. But my understanding of notation leaves much to be desired.

Does this
>>[tex]p \in \mathbb{Z}_n \times \mathbb{Z}_n[/tex]

mean the same as this:
given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i ≤ n and 0 < j ≤ n ?​

Yes. [tex]\mathbb{Z}_n[/tex] is a notation for the intgers mod in, and [tex]\times[/tex] in that context is the cartesian product. (Technically it provides addition and subtraction, but I was explicit about that.)

As to the node you refer to as
>>
[tex]v_{(a,b)} (a,b) \in\mathbb{Z}_n[/tex]

can I interpret that as follows:
given two consecutive fibonacci numbers fa, fb and some integer n, in your node (a,b), a = fa mod n and b = fb mod n?​

That should definitely have been better. I meant that I can refer to [tex]v_{(a,b)}[/tex] where [tex]a[/tex] and [tex]b[/tex] are in [tex]\mathbb{Z}_n[/tex].

But I'm puzzled by your child nodes [tex]v_{(a,a+b)}[/tex]. D.id you mean to write [tex]v_{(b,a+b)}[/tex]? If not, then I must be misunderstanding the meaning of [tex]v_{(a,b)}[/tex]
so please help me out.

Once again, my error. I will correct those in the post, thank you.
 
Last edited:
  • #14
Then I should have written

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i < n and 0 < j < n​

not "≤ n", correct?

Thanks, NateTG.
 
  • #15
gnome said:
Then I should have written

given three integers i,j,n, the set of all ordered pairs (i,j) such that 0 < i < n and 0 < j < n​

not "≤ n", correct?

Actually, either 0 &leq; i < n or 0 < i &leq; n work. Since [tex]0 \equiv n[/tex](mod n) they're equivalent. But one side must be &leq;. (Since the fibonacci sequence hits 0 mod n, those definitely need to be there.)
 
  • #16
Duh...of course. :rolleyes:

0 ≤ i < n and 0 ≤ j < n

Thanks again.
 

FAQ: Brain Teaser #92: Solve Fibonacci Puzzle

What is the Fibonacci sequence?

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. The sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on.

How do I solve the Fibonacci puzzle?

To solve the Fibonacci puzzle, you need to figure out the next number in the sequence by adding the two previous numbers. For example, if the sequence is 0, 1, 1, 2, the next number would be 3 (1+2=3).

What is the significance of the Fibonacci sequence?

The Fibonacci sequence has many real-life applications, such as in mathematics, art, and nature. It can be found in the patterns of flower petals, the arrangement of leaves on a stem, and even in the proportions of the human body.

How can I use the Fibonacci sequence in problem-solving?

The Fibonacci sequence can be used to solve various problems, such as calculating the growth of rabbit populations or predicting stock prices. It can also be used as a tool for organizing and understanding information in a logical way.

Is there a formula for finding the nth number in the Fibonacci sequence?

Yes, there is a formula for finding the nth number in the Fibonacci sequence. It is called Binet's Formula and it goes like this: F(n) = (1/sqrt(5)) * (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n). However, it is much easier to simply add the two previous numbers to find the next one in the sequence.

Similar threads

Replies
1
Views
915
Replies
11
Views
1K
Replies
4
Views
4K
Replies
7
Views
8K
Replies
1
Views
1K
Replies
8
Views
2K
Replies
4
Views
3K
Back
Top