Project Euler 455: Powers With Trailing Digits
Problem Description
Let f(n) be the largest positive integer x less than 109 such that the last 9 digits of nx form the number x (including leading zeros), or zero if no such integer exists.
For example:
- f(4) = 411728896 (4411728896 = …490411728896)
- f(10) = 0
- f(157) = 743757 (157743757 = …567000743757)
- Σf(n), 2 ≤ n ≤ 103 = 442530011399
Find Σf(n), 2 ≤ n ≤ 106.
Analysis
Well, just follow the instructions and employ Pypy to get it to run under 1 minute. This is not much different from other problems that deal with large numbers where the pow() function and the third modulus parameter are used.
I should work on improving the algorithm so I wouldn’t need Pypy to bail me out of a time constraint. It takes about 67 seconds in Python.
Project Euler 455 Solution
Runs < 32 seconds in Pypy.
Use this link to get the Project Euler 455 Solution Pypy source.
Afterthoughts
-
No afterthoughts yet.
Project Euler 455 Solution last updated
Hi and thanks for this reply.
I know your post is 10 years old but still trying 😀
Well done on this concise and elegant solution.
I’ve been trying to solve this puzzle, came up with a solution that is theoretically correct but does not scale for some ns.
I am trying to understand what property you use, when exponentiating in cascade like you do (eg for n =3, x1 is 3^(3^(3^…)
I am struggling to get an intuition about this.
Thank you very much!
Posted by clem | January 7, 2025, 1:51 AM