Last Digit of the Sum of Fibonacci Numbers
I am trying to find the last digit of sum of Fibonacci Series. The below code is working fine but it is slow for large numbers. Ex - 99999
How can I optimize this?
n = int(input())
def Fib(n):
a, b = 0, 1
for i in range(n+2):
a, b = b, a + b
return (a-1) % 10
print(Fib(n))
python python-3.x fibonacci
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
add a comment |
I am trying to find the last digit of sum of Fibonacci Series. The below code is working fine but it is slow for large numbers. Ex - 99999
How can I optimize this?
n = int(input())
def Fib(n):
a, b = 0, 1
for i in range(n+2):
a, b = b, a + b
return (a-1) % 10
print(Fib(n))
python python-3.x fibonacci
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
1
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05
add a comment |
I am trying to find the last digit of sum of Fibonacci Series. The below code is working fine but it is slow for large numbers. Ex - 99999
How can I optimize this?
n = int(input())
def Fib(n):
a, b = 0, 1
for i in range(n+2):
a, b = b, a + b
return (a-1) % 10
print(Fib(n))
python python-3.x fibonacci
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
I am trying to find the last digit of sum of Fibonacci Series. The below code is working fine but it is slow for large numbers. Ex - 99999
How can I optimize this?
n = int(input())
def Fib(n):
a, b = 0, 1
for i in range(n+2):
a, b = b, a + b
return (a-1) % 10
print(Fib(n))
python python-3.x fibonacci
python python-3.x fibonacci
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
edited Jan 2 at 20:14
Eugene Yarmash
85.5k23185265
85.5k23185265
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
asked Jan 2 at 14:44
Loveleen AroraLoveleen Arora
111
111
1
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05
add a comment |
1
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05
1
1
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05
add a comment |
3 Answers
3
active
oldest
votes
Here's code optimized specifically for the last digit:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
It works by getting only the last digit of the next term and adding that to the result. It then gets the last digit of the result and sets it to itself. It repeats until it gets to the term number and returns a one-digit number :D
Fun Fact:
Try the above function on 99. Returns 0. What about 999? 0. 9999? 0. Continue this :D
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
add a comment |
Look at this table: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
notice that fib(60) last digit is 0 and fib(61) last digit is 1, that is same as fib(0) and fib(1), thus starting at 60 last digits starts to repeat, so you can calculate last digit for fib(n%60) rather than fib(n).
For example last digit is same for fib(115) and fib(55) and equal to 5.
answered Jan 2 at 16:06
DaweoDaweo
1,02025
add a comment |
The series of final digits of Fibonacci numbers repeats with a cycle of 60. So, instead of calculating F(n+2), you could calculate F((n+2) % 60). To keep the numbers within the integer range, calculate the sum modulo 10:
def fib(n):
n = (n + 2) % 60
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 10
return 9 if a == 0 else a - 1
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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
},
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%2fstackoverflow.com%2fquestions%2f54008328%2flast-digit-of-the-sum-of-fibonacci-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
Here's code optimized specifically for the last digit:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
It works by getting only the last digit of the next term and adding that to the result. It then gets the last digit of the result and sets it to itself. It repeats until it gets to the term number and returns a one-digit number :D
Fun Fact:
Try the above function on 99. Returns 0. What about 999? 0. 9999? 0. Continue this :D
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
add a comment |
Here's code optimized specifically for the last digit:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
It works by getting only the last digit of the next term and adding that to the result. It then gets the last digit of the result and sets it to itself. It repeats until it gets to the term number and returns a one-digit number :D
Fun Fact:
Try the above function on 99. Returns 0. What about 999? 0. 9999? 0. Continue this :D
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
add a comment |
Here's code optimized specifically for the last digit:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
It works by getting only the last digit of the next term and adding that to the result. It then gets the last digit of the result and sets it to itself. It repeats until it gets to the term number and returns a one-digit number :D
Fun Fact:
Try the above function on 99. Returns 0. What about 999? 0. 9999? 0. Continue this :D
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
Here's code optimized specifically for the last digit:
def fib(n):
a, b = 0, 1
r = 1
if n < 1:
return 0
for i in range(n - 1):
a, b = b, (a + b)%10
r += b
r %= 10
return r
It works by getting only the last digit of the next term and adding that to the result. It then gets the last digit of the result and sets it to itself. It repeats until it gets to the term number and returns a one-digit number :D
Fun Fact:
Try the above function on 99. Returns 0. What about 999? 0. 9999? 0. Continue this :D
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
edited Jan 2 at 15:06
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
answered Jan 2 at 14:50
GeeTransitGeeTransit
694216
694216
add a comment |
add a comment |
Look at this table: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
notice that fib(60) last digit is 0 and fib(61) last digit is 1, that is same as fib(0) and fib(1), thus starting at 60 last digits starts to repeat, so you can calculate last digit for fib(n%60) rather than fib(n).
For example last digit is same for fib(115) and fib(55) and equal to 5.
answered Jan 2 at 16:06
DaweoDaweo
1,02025
add a comment |
Look at this table: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
notice that fib(60) last digit is 0 and fib(61) last digit is 1, that is same as fib(0) and fib(1), thus starting at 60 last digits starts to repeat, so you can calculate last digit for fib(n%60) rather than fib(n).
For example last digit is same for fib(115) and fib(55) and equal to 5.
answered Jan 2 at 16:06
DaweoDaweo
1,02025
add a comment |
Look at this table: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
notice that fib(60) last digit is 0 and fib(61) last digit is 1, that is same as fib(0) and fib(1), thus starting at 60 last digits starts to repeat, so you can calculate last digit for fib(n%60) rather than fib(n).
For example last digit is same for fib(115) and fib(55) and equal to 5.
answered Jan 2 at 16:06
DaweoDaweo
1,02025
Look at this table: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
notice that fib(60) last digit is 0 and fib(61) last digit is 1, that is same as fib(0) and fib(1), thus starting at 60 last digits starts to repeat, so you can calculate last digit for fib(n%60) rather than fib(n).
For example last digit is same for fib(115) and fib(55) and equal to 5.
answered Jan 2 at 16:06
DaweoDaweo
1,02025
answered Jan 2 at 16:06
DaweoDaweo
1,02025
answered Jan 2 at 16:06
DaweoDaweo
1,02025
answered Jan 2 at 16:06
DaweoDaweo
1,02025
1,02025
add a comment |
add a comment |
The series of final digits of Fibonacci numbers repeats with a cycle of 60. So, instead of calculating F(n+2), you could calculate F((n+2) % 60). To keep the numbers within the integer range, calculate the sum modulo 10:
def fib(n):
n = (n + 2) % 60
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 10
return 9 if a == 0 else a - 1
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
add a comment |
The series of final digits of Fibonacci numbers repeats with a cycle of 60. So, instead of calculating F(n+2), you could calculate F((n+2) % 60). To keep the numbers within the integer range, calculate the sum modulo 10:
def fib(n):
n = (n + 2) % 60
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 10
return 9 if a == 0 else a - 1
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
add a comment |
The series of final digits of Fibonacci numbers repeats with a cycle of 60. So, instead of calculating F(n+2), you could calculate F((n+2) % 60). To keep the numbers within the integer range, calculate the sum modulo 10:
def fib(n):
n = (n + 2) % 60
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 10
return 9 if a == 0 else a - 1
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
The series of final digits of Fibonacci numbers repeats with a cycle of 60. So, instead of calculating F(n+2), you could calculate F((n+2) % 60). To keep the numbers within the integer range, calculate the sum modulo 10:
def fib(n):
n = (n + 2) % 60
a, b = 0, 1
for i in range(n):
a, b = b, (a + b) % 10
return 9 if a == 0 else a - 1
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
edited Jan 2 at 20:13
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
answered Jan 2 at 15:11
Eugene YarmashEugene Yarmash
85.5k23185265
85.5k23185265
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f54008328%2flast-digit-of-the-sum-of-fibonacci-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
1
The Fibonacci sequence grows very quickly (exponentially), which causes Python to resort to arbitrary precision types. You will need modulo math rules to keep the numbers within 32/64-bit integer range.
– meowgoesthedog
Jan 2 at 14:47
There is a way... Check my answer below.
– GeeTransit
Jan 2 at 15:05