Calculating how many 2's appear in the last digits of the first 2004 Fibonacci numbers.
$begingroup$
I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use of calculator or programming software, that would be great.
The Fibonacci numbers are F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, … where the first two are both equal to 1, and from then on, each one is the sum of the two preceding it. Of the first 2004 Fibonacci numbers, how many have 2 as their last digit?
sequences-and-series modular-arithmetic fibonacci-numbers
$endgroup$
add a comment |
$begingroup$
I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use of calculator or programming software, that would be great.
The Fibonacci numbers are F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, … where the first two are both equal to 1, and from then on, each one is the sum of the two preceding it. Of the first 2004 Fibonacci numbers, how many have 2 as their last digit?
sequences-and-series modular-arithmetic fibonacci-numbers
$endgroup$
5
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35
add a comment |
$begingroup$
I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use of calculator or programming software, that would be great.
The Fibonacci numbers are F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, … where the first two are both equal to 1, and from then on, each one is the sum of the two preceding it. Of the first 2004 Fibonacci numbers, how many have 2 as their last digit?
sequences-and-series modular-arithmetic fibonacci-numbers
$endgroup$
I have had some trouble with the following question (It is from the Australian Mathematics Competition). If anyone would be able to produce a solution (with considerable working), that requires no use of calculator or programming software, that would be great.
The Fibonacci numbers are F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13, … where the first two are both equal to 1, and from then on, each one is the sum of the two preceding it. Of the first 2004 Fibonacci numbers, how many have 2 as their last digit?
sequences-and-series modular-arithmetic fibonacci-numbers
sequences-and-series modular-arithmetic fibonacci-numbers
edited Jan 12 at 2:03
Klein Bottle
asked Jan 11 at 21:15
Klein BottleKlein Bottle
22
22
5
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35
add a comment |
5
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35
5
5
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.
First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) mod 10$. Note that if there are $aneq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.
So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.
Our first few values are:
$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.
Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33times60$ Fibbonacci numbers modulo $10$ contain $33 times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.
$endgroup$
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
add a comment |
$begingroup$
I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.
Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...
The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.
Ps Made a mistake but go on with the same principle.
$endgroup$
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
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%2f3070348%2fcalculating-how-many-2s-appear-in-the-last-digits-of-the-first-2004-fibonacci-n%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.
First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) mod 10$. Note that if there are $aneq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.
So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.
Our first few values are:
$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.
Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33times60$ Fibbonacci numbers modulo $10$ contain $33 times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.
$endgroup$
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
add a comment |
$begingroup$
I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.
First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) mod 10$. Note that if there are $aneq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.
So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.
Our first few values are:
$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.
Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33times60$ Fibbonacci numbers modulo $10$ contain $33 times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.
$endgroup$
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
add a comment |
$begingroup$
I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.
First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) mod 10$. Note that if there are $aneq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.
So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.
Our first few values are:
$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.
Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33times60$ Fibbonacci numbers modulo $10$ contain $33 times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.
$endgroup$
I'll answer both the question in the title, and the one in the actual question, since most of the work is the same.
First, reduce everything modulo $10$. Then our sequence is given by the recurrence relation $F(n) = F(n-1) + F(n-2) mod 10$. Note that if there are $aneq b$ such that $F(a) = F(b)$ and $F(a+1) = F(b+1)$, then our sequence necessarily repeats with period $b-a$ thereafter.
So, we need only find such a repetition, which must happen in finite time, because there are only $10^2 = 100$ possible pairs of residues modulo $10$.
Our first few values are:
$1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5, 1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1$.
Now, notice, we have repeated: $1,1$ appears at both the first and second positions, and the 61st and 62nd. Thus, our pattern repeats in blocks of 60, each of which contain exactly four twos. Thus, the first $1980 = 33times60$ Fibbonacci numbers modulo $10$ contain $33 times 4 = 132$ twos. The $24$ after that are $1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8$, so contain one two, and the whole first $2004$ terms contain exactly $133$ twos. To answer the question in your title, the final digit of the $2004$th Fibbonacci number is $8$.
answered Jan 11 at 21:28
user3482749user3482749
4,057918
4,057918
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
add a comment |
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
$begingroup$
Apologies for the title, I didn't even realise
$endgroup$
– Klein Bottle
Jan 12 at 1:59
add a comment |
$begingroup$
I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.
Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...
The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.
Ps Made a mistake but go on with the same principle.
$endgroup$
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
add a comment |
$begingroup$
I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.
Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...
The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.
Ps Made a mistake but go on with the same principle.
$endgroup$
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
add a comment |
$begingroup$
I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.
Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...
The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.
Ps Made a mistake but go on with the same principle.
$endgroup$
I’d write down the last digits of the Fibonacci numbers until I see the same sequence of two digits repeat, and then it is easy.
Last digits are 1 1 2 3 5 8 3 1 4 5 9 4 3 7 0 7 7 4 1 5 6 1 7 8 5 3 8 1 9 0 9 9 8 7 5 2 7 9 6 5 1 6 7 3 0 7 7 4 ...
The 15/16th numbers have the same last digits as the 44/45th, and there is one number at position 35 with last digit 2. Just check if I counted right. The next numbers with last digit 2 are at 64, 93 and so on. Just a bit of maths now.
Ps Made a mistake but go on with the same principle.
edited Jan 11 at 21:30
answered Jan 11 at 21:28
gnasher729gnasher729
5,9871028
5,9871028
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
add a comment |
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
$begingroup$
You've got a slight arithmetic error: the last three digits you've written should be $3, 3, 6$, not $7, 7, 4$.
$endgroup$
– user3482749
Jan 11 at 21:30
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%2f3070348%2fcalculating-how-many-2s-appear-in-the-last-digits-of-the-first-2004-fibonacci-n%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
5
$begingroup$
The questions in the title and in the body are not the same...
$endgroup$
– zipirovich
Jan 11 at 21:24
$begingroup$
Hint: $pmod {10}$ the Fibonacci numbers almost have period $15$. Indeed $F_{15}equiv 0, F_{16}equiv F_{17}equiv 7pmod {10}$. From that you can easily calculate the true period. Counting the $2's$ is slightly more work, but still doable from that initial "quasi-period".
$endgroup$
– lulu
Jan 11 at 21:35