Brain Teaser #92: Solve Fibonacci Puzzle

  • Context: Undergrad 
  • Thread starter Thread starter davilla
  • Start date Start date
  • Tags Tags
    Brain
Click For Summary

Discussion Overview

The discussion revolves around identifying the smallest positive integer that does not evenly divide any Fibonacci number in the sequence starting from 1. Participants explore various hypotheses, proofs, and counterarguments related to the properties of Fibonacci numbers and their divisibility.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant proposes that the smallest positive integer could be 11, but another points out that 11 divides the tenth Fibonacci number, 55.
  • A participant argues that if a number n exists with the desired property, the Fibonacci numbers modulo n must eventually repeat, leading to the conclusion that n divides some Fibonacci numbers.
  • Another participant questions the assumption that every pair of Fibonacci numbers modulo n must repeat, suggesting that there could be pairs that never occur.
  • There is a discussion about the definition of "state" in the context of Fibonacci sequences, with some participants providing clarifications and alternative proofs involving directed graphs.
  • One participant emphasizes that the Fibonacci sequence's deterministic nature implies that once a state is repeated, it must enter a loop, which would include the state (1,1).
  • Another participant expresses confusion regarding the notation used in the proofs and seeks clarification on specific terms and concepts related to the graph representation of Fibonacci sequences.

Areas of Agreement / Disagreement

Participants express differing views on the assumptions and conclusions drawn about the Fibonacci sequence and its properties. There is no consensus on the smallest positive integer that does not divide any Fibonacci number, and the discussion remains unresolved.

Contextual Notes

Participants note limitations in their arguments, such as the dependence on definitions of states and the potential for unexamined assumptions in the proofs presented. Some mathematical steps remain unresolved, particularly regarding the behavior of Fibonacci numbers modulo n.

davilla
Messages
88
Reaction score
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:
Mathematics news on Phys.org
disregarding dividing by 1, could the smallest positive integer be 11?
 
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.
 
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].
 
Nate, please define the term state as you are using it in your proof.
 
is it the number 89?
 
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:
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:
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.
 

Similar threads

  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 3 ·
Replies
3
Views
4K
  • · Replies 7 ·
Replies
7
Views
9K
  • · Replies 4 ·
Replies
4
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
2
Views
2K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K