Fibonacci's final digits cycle every 60 numbers
$begingroup$
How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?
References:
The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).
http://mathworld.wolfram.com/FibonacciNumber.html
fibonacci-numbers
$endgroup$
add a comment |
$begingroup$
How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?
References:
The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).
http://mathworld.wolfram.com/FibonacciNumber.html
fibonacci-numbers
$endgroup$
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59
add a comment |
$begingroup$
How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?
References:
The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).
http://mathworld.wolfram.com/FibonacciNumber.html
fibonacci-numbers
$endgroup$
How would you go about to prove that the final digits of the Fibonacci numbers recur after a cycle of 60?
References:
The sequence of final digits in Fibonacci numbers repeats in cycles of 60. The last two digits repeat in 300, the last three in 1500, the last four in , etc. The number of Fibonacci numbers between and is either 1 or 2 (Wells 1986, p. 65).
http://mathworld.wolfram.com/FibonacciNumber.html
fibonacci-numbers
fibonacci-numbers
edited Feb 26 '12 at 9:57
crazyGuy
asked Feb 26 '12 at 9:47
crazyGuycrazyGuy
16315
16315
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59
add a comment |
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
Notice that:
$F_{n+15} equiv 7F_n pmod{10}$ for $ngeq 1$.
Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15times 4 = 60$.
$endgroup$
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
|
show 3 more comments
$begingroup$
Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,dots=0,1,dots$ That is, a subsequence starting with $0,a,dots$ is $a$ times the sequence starting with $0,1,dots$
Consider the Fibonacci sequence $text{mod }2$:
$$
color{red}{0,1,1,}color{green}{0,1,1,dots}
$$
Thus, the Fibonacci sequence repeats $text{mod }2$ with a period of $3$.
Consider the Fibonacci sequence $text{mod }5$:
$$
color{red}{0,1,1,2,3,}color{green}{0,3,3,dots}
$$
Thus, the Fibonacci sequence is multiplied by $3pmod{5}$ each "period" of $5$. Since $3^4=1pmod{5}$, the Fibonacci sequence repeats $text{mod }5$ with a period of $20=4cdot5$.
Thus, the Fibonacci sequence repeats $text{mod }10$ with a period of $60=operatorname{LCM}(3,20)$.
$endgroup$
add a comment |
$begingroup$
Note that
$$
begin{pmatrix} F_{n+1}\ F_{n+2} end{pmatrix} = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix} begin{pmatrix} F_n \ F_{n+1} end{pmatrix}
$$
and
$$
begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix}^{60} equiv begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} mod 10.
$$
One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular
$$
begin{pmatrix} F_{n+60}\ F_{n+61} end{pmatrix} equiv begin{pmatrix} F_n \ F_{n+1} end{pmatrix} mod 10
$$
so the final digits repeat from that point onwards.
$endgroup$
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
add a comment |
$begingroup$
$F_{0}=F_1=F_{60}=F_{61}= 1 mod10$
By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.
$endgroup$
add a comment |
$begingroup$
I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).
Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:
1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......
Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?
If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.
It's very interesting.
$endgroup$
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f113536%2ffibonaccis-final-digits-cycle-every-60-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Notice that:
$F_{n+15} equiv 7F_n pmod{10}$ for $ngeq 1$.
Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15times 4 = 60$.
$endgroup$
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
|
show 3 more comments
$begingroup$
Notice that:
$F_{n+15} equiv 7F_n pmod{10}$ for $ngeq 1$.
Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15times 4 = 60$.
$endgroup$
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
|
show 3 more comments
$begingroup$
Notice that:
$F_{n+15} equiv 7F_n pmod{10}$ for $ngeq 1$.
Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15times 4 = 60$.
$endgroup$
Notice that:
$F_{n+15} equiv 7F_n pmod{10}$ for $ngeq 1$.
Also the order of $7$ mod $10$ is $4$ so the repetition in the digits of the Fibonacci numbers begins after place $15times 4 = 60$.
edited Dec 7 '18 at 17:40
thepiercingarrow
395216
395216
answered Feb 26 '12 at 10:02
frettyfretty
8,5181431
8,5181431
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
|
show 3 more comments
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
I got that recursion by just writing out the first $16$ Fibonacci numbers mod $10$ and noticing that you get $1,1,...,7,7,...$, this dictates that that next $13$ numbers must be $7$ times their corresponding numbers (mod $10$) in the first lot of $15$ numbers.
$endgroup$
– fretty
Feb 26 '12 at 10:03
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
How do we know that F_n+15 = 7F_n mod 10 ? and How do you get that 7 mod 10 is 4 ? thanks.
$endgroup$
– crazyGuy
Feb 26 '12 at 10:07
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
Write out the first 16 Fibonacci numbers mod 10: 1,1,...,7,7,... Now by the recursion of the fibonacci numbers the fact that this "multiple-repeat" has happened now tells us that the next 13 numbers must be the same as the 3rd-15th Fibonacci numbers but multiplied by $7$ mod 10. So an actual repeat will happen as soon as we have multipled by enough $7$'s to get $1$ mod 10. This is the "order" of $7$ mod $10$. It is easy to work out here, $7^2 equiv 4$ mod $10$ and $7^4 equiv 1$ mod $10$ so the order is $4$.
$endgroup$
– fretty
Feb 26 '12 at 10:13
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
@sic2 He's not saying that $7mod10$ is $4$, but rather that $7^4equiv 1mod 10$ and that this is not true for any smaller power of $7$, which is a consequence of Euler's theorem.
$endgroup$
– Alex Becker
Feb 26 '12 at 10:15
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
$begingroup$
Also this method generalises to the Fibonacci numbers mod $n$. Find the first $1,1,...,a,a,...$ then work out the order of $a$ mod $n$ and you will have your first place where it recurs.
$endgroup$
– fretty
Feb 26 '12 at 10:29
|
show 3 more comments
$begingroup$
Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,dots=0,1,dots$ That is, a subsequence starting with $0,a,dots$ is $a$ times the sequence starting with $0,1,dots$
Consider the Fibonacci sequence $text{mod }2$:
$$
color{red}{0,1,1,}color{green}{0,1,1,dots}
$$
Thus, the Fibonacci sequence repeats $text{mod }2$ with a period of $3$.
Consider the Fibonacci sequence $text{mod }5$:
$$
color{red}{0,1,1,2,3,}color{green}{0,3,3,dots}
$$
Thus, the Fibonacci sequence is multiplied by $3pmod{5}$ each "period" of $5$. Since $3^4=1pmod{5}$, the Fibonacci sequence repeats $text{mod }5$ with a period of $20=4cdot5$.
Thus, the Fibonacci sequence repeats $text{mod }10$ with a period of $60=operatorname{LCM}(3,20)$.
$endgroup$
add a comment |
$begingroup$
Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,dots=0,1,dots$ That is, a subsequence starting with $0,a,dots$ is $a$ times the sequence starting with $0,1,dots$
Consider the Fibonacci sequence $text{mod }2$:
$$
color{red}{0,1,1,}color{green}{0,1,1,dots}
$$
Thus, the Fibonacci sequence repeats $text{mod }2$ with a period of $3$.
Consider the Fibonacci sequence $text{mod }5$:
$$
color{red}{0,1,1,2,3,}color{green}{0,3,3,dots}
$$
Thus, the Fibonacci sequence is multiplied by $3pmod{5}$ each "period" of $5$. Since $3^4=1pmod{5}$, the Fibonacci sequence repeats $text{mod }5$ with a period of $20=4cdot5$.
Thus, the Fibonacci sequence repeats $text{mod }10$ with a period of $60=operatorname{LCM}(3,20)$.
$endgroup$
add a comment |
$begingroup$
Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,dots=0,1,dots$ That is, a subsequence starting with $0,a,dots$ is $a$ times the sequence starting with $0,1,dots$
Consider the Fibonacci sequence $text{mod }2$:
$$
color{red}{0,1,1,}color{green}{0,1,1,dots}
$$
Thus, the Fibonacci sequence repeats $text{mod }2$ with a period of $3$.
Consider the Fibonacci sequence $text{mod }5$:
$$
color{red}{0,1,1,2,3,}color{green}{0,3,3,dots}
$$
Thus, the Fibonacci sequence is multiplied by $3pmod{5}$ each "period" of $5$. Since $3^4=1pmod{5}$, the Fibonacci sequence repeats $text{mod }5$ with a period of $20=4cdot5$.
Thus, the Fibonacci sequence repeats $text{mod }10$ with a period of $60=operatorname{LCM}(3,20)$.
$endgroup$
Since each term in the Fibonacci sequence is dependent on the previous two, each time a $0pmod{m}$ appears in the sequence, what follows must be a multiple of the sequence starting at $F_0,F_1,dots=0,1,dots$ That is, a subsequence starting with $0,a,dots$ is $a$ times the sequence starting with $0,1,dots$
Consider the Fibonacci sequence $text{mod }2$:
$$
color{red}{0,1,1,}color{green}{0,1,1,dots}
$$
Thus, the Fibonacci sequence repeats $text{mod }2$ with a period of $3$.
Consider the Fibonacci sequence $text{mod }5$:
$$
color{red}{0,1,1,2,3,}color{green}{0,3,3,dots}
$$
Thus, the Fibonacci sequence is multiplied by $3pmod{5}$ each "period" of $5$. Since $3^4=1pmod{5}$, the Fibonacci sequence repeats $text{mod }5$ with a period of $20=4cdot5$.
Thus, the Fibonacci sequence repeats $text{mod }10$ with a period of $60=operatorname{LCM}(3,20)$.
edited Feb 26 '12 at 15:21
answered Feb 26 '12 at 14:25
robjohn♦robjohn
266k27306630
266k27306630
add a comment |
add a comment |
$begingroup$
Note that
$$
begin{pmatrix} F_{n+1}\ F_{n+2} end{pmatrix} = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix} begin{pmatrix} F_n \ F_{n+1} end{pmatrix}
$$
and
$$
begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix}^{60} equiv begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} mod 10.
$$
One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular
$$
begin{pmatrix} F_{n+60}\ F_{n+61} end{pmatrix} equiv begin{pmatrix} F_n \ F_{n+1} end{pmatrix} mod 10
$$
so the final digits repeat from that point onwards.
$endgroup$
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
add a comment |
$begingroup$
Note that
$$
begin{pmatrix} F_{n+1}\ F_{n+2} end{pmatrix} = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix} begin{pmatrix} F_n \ F_{n+1} end{pmatrix}
$$
and
$$
begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix}^{60} equiv begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} mod 10.
$$
One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular
$$
begin{pmatrix} F_{n+60}\ F_{n+61} end{pmatrix} equiv begin{pmatrix} F_n \ F_{n+1} end{pmatrix} mod 10
$$
so the final digits repeat from that point onwards.
$endgroup$
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
add a comment |
$begingroup$
Note that
$$
begin{pmatrix} F_{n+1}\ F_{n+2} end{pmatrix} = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix} begin{pmatrix} F_n \ F_{n+1} end{pmatrix}
$$
and
$$
begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix}^{60} equiv begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} mod 10.
$$
One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular
$$
begin{pmatrix} F_{n+60}\ F_{n+61} end{pmatrix} equiv begin{pmatrix} F_n \ F_{n+1} end{pmatrix} mod 10
$$
so the final digits repeat from that point onwards.
$endgroup$
Note that
$$
begin{pmatrix} F_{n+1}\ F_{n+2} end{pmatrix} = begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix} begin{pmatrix} F_n \ F_{n+1} end{pmatrix}
$$
and
$$
begin{pmatrix} 0 & 1 \ 1 & 1 end{pmatrix}^{60} equiv begin{pmatrix} 1 & 0 \ 0 & 1 end{pmatrix} mod 10.
$$
One can verify that $60$ is the smallest power for which this holds, so it is the order of the matrix mod 10. In particular
$$
begin{pmatrix} F_{n+60}\ F_{n+61} end{pmatrix} equiv begin{pmatrix} F_n \ F_{n+1} end{pmatrix} mod 10
$$
so the final digits repeat from that point onwards.
answered Feb 26 '12 at 10:03
WimCWimC
24.1k22962
24.1k22962
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
add a comment |
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
3
3
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
$begingroup$
The same matrix applies to the Lucas Numbers, however, $text{ mod }10$, they have a period of $12$. The fact that $begin{pmatrix} 0&1\1&1end{pmatrix}^{60}=begin{pmatrix}1&0\0&1end{pmatrix}text{ mod }10$, says that the period of a sequence satisfying $a_n=a_{n-1}+a_{n-2}$ divides $60$.
$endgroup$
– robjohn♦
Feb 26 '12 at 19:21
add a comment |
$begingroup$
$F_{0}=F_1=F_{60}=F_{61}= 1 mod10$
By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.
$endgroup$
add a comment |
$begingroup$
$F_{0}=F_1=F_{60}=F_{61}= 1 mod10$
By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.
$endgroup$
add a comment |
$begingroup$
$F_{0}=F_1=F_{60}=F_{61}= 1 mod10$
By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.
$endgroup$
$F_{0}=F_1=F_{60}=F_{61}= 1 mod10$
By inspection, these are the first two pairs of consecutive Fibonaccis for which this is true. Since the recurrence relation only takes into account the previous two terms and last digits only depend on previous last digits, this suffices to prove the claim.
edited Feb 26 '12 at 11:43
answered Feb 26 '12 at 11:18
Tom BoardmanTom Boardman
2,08322030
2,08322030
add a comment |
add a comment |
$begingroup$
I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).
Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:
1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......
Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?
If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.
It's very interesting.
$endgroup$
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
add a comment |
$begingroup$
I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).
Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:
1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......
Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?
If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.
It's very interesting.
$endgroup$
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
add a comment |
$begingroup$
I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).
Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:
1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......
Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?
If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.
It's very interesting.
$endgroup$
I have found that there is an 11 number grouping. You must reduce numbers to a single digit (13=4 or 55=10=1). After 24 numbers into the sequence it repeats. To go a little deeper, a 9 is in the twelfth and twenty- fourth sequence and the real number is also divisible by 12 in these positions (which coincidentally is every twelfth number in the sequence).
Now if you do the multiplication table of numbers 1 through 8 and reduce all numbers to a single digit, you will find that 1 and 8 correspond in reverse with each other. The same for 2 and 7, also 4 and 5. 3 and 6 are different. You will notice that for every number sequence it will repeat after a 9 appears. So, Fibonacci sequence would be this:
1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9,1,1,2,3,5,8,4,3,7,1,8,9,8,8,7,6,4,1,5,6,2,8,1,9......
Remember how I said 1 and 8, 2 and 7, 4 and 5 correspond with each other by reducing the multiplication table to single digits and all numbers repeat a sequence after a 9?
If you move the eleven number sequence between the nines and set 1,1,2,3... above the sequence 8,8,7,6... You will find that they all correspond with the reducing method afore mentioned.
It's very interesting.
edited Jun 26 '17 at 22:09
David Andrei Ned
1034
1034
answered Oct 24 '16 at 2:47
Michael BuntonMichael Bunton
112
112
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
add a comment |
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
What do you mean $11$-number grouping? Why are you reducing mod $9$ instead of mod $10$? How does this prove that it repeats with cycle $60$?
$endgroup$
– 6005
Oct 24 '16 at 2:58
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
I apologize. This was not to prove or disprove a 60 cycle repeat. Maybe I posted in the wrong area? I just found this sequence repeat and I thought I would give it to bigger brains and see what they can make of it.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:12
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
$begingroup$
11 number grouping means the first 11 numbers in the sequence. The twelfth number is 144 and that reduces to 9 i.e.(1+4+4=9). Then a second set of eleven numbers followed by a reduced 9.
$endgroup$
– Michael Bunton
Oct 24 '16 at 3:20
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f113536%2ffibonaccis-final-digits-cycle-every-60-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Why do you conjecture that? Do you have a reference that asserts the statement?
$endgroup$
– Giovanni De Gaetano
Feb 26 '12 at 9:52
$begingroup$
I added some references.
$endgroup$
– crazyGuy
Feb 26 '12 at 9:57
$begingroup$
Neat! Have a look at this link.
$endgroup$
– Juan S
Feb 26 '12 at 10:00
$begingroup$
Here is a link: oeis.org/A096363
$endgroup$
– Stefan Gruenwald
Dec 14 '18 at 20:59