Calculating how many 2's appear in the last digits of the first 2004 Fibonacci numbers.












-1












$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?










share|cite|improve this question











$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
















-1












$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?










share|cite|improve this question











$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














-1












-1








-1





$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?










share|cite|improve this question











$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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








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














  • 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










2 Answers
2






active

oldest

votes


















4












$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$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Apologies for the title, I didn't even realise
    $endgroup$
    – Klein Bottle
    Jan 12 at 1:59



















2












$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.






share|cite|improve this answer











$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











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
});


}
});














draft saved

draft discarded


















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









4












$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$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Apologies for the title, I didn't even realise
    $endgroup$
    – Klein Bottle
    Jan 12 at 1:59
















4












$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$.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Apologies for the title, I didn't even realise
    $endgroup$
    – Klein Bottle
    Jan 12 at 1:59














4












4








4





$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$.






share|cite|improve this answer









$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$.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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


















  • $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











2












$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.






share|cite|improve this answer











$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
















2












$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.






share|cite|improve this answer











$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














2












2








2





$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.






share|cite|improve this answer











$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.







share|cite|improve this answer














share|cite|improve this answer



share|cite|improve this answer








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


















  • $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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







Popular posts from this blog

Mario Kart Wii

The Binding of Isaac: Rebirth/Afterbirth

What does “Dominus providebit” mean?