(34 votes, average: 4.71 out of 5)
Loading...
Project Euler 48: Find the last ten digits of 11 + 22 + ... + 10001000
Project Euler 48 Problem Description
Project Euler 48: The series, 11 + 22 + 33 + … + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.
Analysis
This problem is wanting us to calculate the series of self powers up to and including 1000 and report the last ten digits of this calculation. This solution includes leading zeros if appropriate so 10 characters are always printed. The HackerRank version specifically request no leading zeros to be printed.
With the capability of Python’s pow() function and native large integer support this can be solved using a simple loop to calculate the series and extract the last 10 digits using the mod() function.
Hackerrank Project Euler 48 increases the limit from 1000 to 2 million but that doesn’t do much in extending the challenge.
Project Euler 48 Solution
Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 48 Solution Python 2.7 source.
Afterthoughts
- Note a property of modular arithmetic:
(a+b) % n = ((a%n) + (b%n)) % n - See also, Project Euler 97 Solution:
- See also, Project Euler 188 Solution:
- The last iteration, 1000, would not affect the last 10 digits of the sum.
Here is my code in python. To reduce calculation time and manage memory I’ve set %10000000000 to keep adding only the last 10 digits each time. The code is in python:
i=1000 x=1 y=0 n=10000000000 while i>=1: j=1 x=1 while j<=i: x=x*i y+=(x%n) j+=1 i-=1 print(y%n)
Posted by SHIVANG | July 8, 2016, 11:03 AMHey I used your code but I had to change it as below in order for it to pass. It passed all test cases. Good job.
L = int(raw_input())
d = 10 # last d digits of series
s = sum(pow(n, n, 10**d) for n in range(1, L+1))
s = int(str(s)[-10:])
print “%d” % (s)
Posted by Ben | April 10, 2016, 11:43 AMI’ve noticed that changes have to be made to several of these solutions to pass on more robust contest platforms like Hackerrank.com.
Thanks for the info!
Posted by Mike Molony | April 10, 2016, 8:42 PMAfter looking at it closer I think you found a bug in trinket. I fixed it by removing the pow-mod calc. Weird results with it left in.
Posted by Mike Molony | April 10, 2016, 11:07 PMWell… I wouldn’t count this as a solution. Where exactly is the place that the solution uses the information that 1^1 + 2^2 + … + 10^10 = …? The brute-force approach is NOT a solution.
Posted by Darek | October 1, 2015, 5:11 AMYes, Darek, brute force is a solution. You don’t always have to be clever or unique when solving problems. Please, Darek, provide a faster Python solution to back you claim. I have added an image to this post to demonstrate my point.
Posted by Mike Molony | October 1, 2015, 10:25 PMFirst, I don’t attack you. You’ve got the wrong impression. I don’t argue with the author of the solution, I argue with the solution itself. It’s an important distinction. Try to read my argument once again. Second, if the claim is that brute-force is a solution, then a question comes to mind: Why the heck would the question author give additional information in the form of the first line equation? Third, the problem is not about the speed of calculation but about programming a good solution. Fourth, there are languages that don’t have support for arbitrary precision arithmetic. Why then would you insist on Python? Try to code a solution to this in SQL for instance! Sure, brute-force is one way to solve a problem (if the problem lends itself to such handling at all). But in this case clearly it’s not what was intended and this is why I still uphold my view.
Posted by Darek | October 2, 2015, 2:01 AMOne more thing… The solution, which I will post when I have time to work it out fully, will be based on the fact that (10a + d)^(10a + d) = (10a + d)^10a * (10a + d)^d and then you have to use the Netwon binomial theorem. Once one have it, you can incorporate the HINT that the author gives you at the very top of the question. No arbitrary precision arithmetic needed. This is what a proper solution should be. Of course, it’s better to give pseudo-code that will work in any programming language, than to have a solution that only works for SOME specific laguages. So, once I have it, it will be pseudo-code that I’m going to post.
Posted by Darek | October 2, 2015, 2:44 AMI am writing programs to solve problems everyday, mostly because I love doing so. When I can solve a problem that needs a quick fix or fast (deadline) solution and brute force works I will use it.
It’s easy to follow 5 years laters when I need to change something and if it is fast enough then why improve it.
Keep an open mind, Darek, to brute force as a possible valid solution. Yes, I know what the intention was by the problem setter, but all is fair when solving problems.
Also, I thought you’d like my fork graphic. Just a little comic relief.
Posted by Mike Molony | October 3, 2015, 1:16 AM