// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (12 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 455 Solution

Project Euler 455 Solution

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.
L, s = 1000000, 0

for n in xrange(2, L):
    x0, x1 = 0, n
    while x0 != x1 and x1:
        x0, x1 = x1, pow(n, x0, 10**9)
    s += x1

print "Project Euler 455 Solution =", s
download arrowUse this link to get the Project Euler 455 Solution Pypy source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|450186511399999|

Afterthoughts

    No afterthoughts yet.
Project Euler 455 Solution last updated

Discussion

No comments yet.

Post a comment