// youâ€™re reading...
(12 votes, average: 5.00 out of 5)
Loading...

## 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