Powers With Trailing Digits

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⁶.

Written by gamwe6 who lives and works in San Francisco building useful things. You should follow him on Twitter