Project Euler 455: Powers With Trailing Digits

Problem Description

Let f(n) be the largest positive integer x less than 10⁹ such that the last 9 digits of n^x form the number x (including leading zeros), or zero if no such integer exists.

For example:

• f(4) = 411728896 (4^411728896 = …490411728896)
• f(10) = 0
• f(157) = 743757 (157⁷⁴³⁷⁵⁷ = …567000743757)
• Σf(n), 2 ≤ n ≤ 10³ = 442530011399

Find Σf(n), 2 ≤ n ≤ 10⁶.

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

Afterthoughts

No afterthoughts yet.