Project Euler 700 - Eulercoin

Official link: https://projecteuler.net/problem=700

Thought Process

The first thing I checked was the gcd(1504170715041707, 4503599627370517) and it is indeed equal to 1, this means that there is a Multiplicative inverse, that is there is a number x such that 1504170715041707*x = 1 mod(4503599627370517), this x is equal to 3451657199285664.

I'm not sure if there is a name for this type of algorithm but I will call it a bi-directional search:

  1. Top to bottom search: See Equation (1) below:

    • Simply keep increasing n and see if x = 1504170715041707*n mod(4503599627370517) was smaller than the previous term.

    • This method generates the first 16 Eulercoins very quickly, the 16th Eulercoin is 15806432 and n was equal to 42298633, now obviously we cannot continue this method, because we need to go up till n = 3451657199285664 which would take years.

    • But 15806432 is much smaller and more manageable, and I thought of going the other direction.

  2. Bottom to top search: See Equation (2) below:

    • The last Eulercoin will be 1 when n = 3451657199285664, but we can reverse this process, if we increase the possible Eulercoin and check if n = 3451657199285664*(possible Eulercoin) mod(4503599627370517) is smaller than the previous n

    • For example lets test Eulercoin = 2 =>3451657199285664*(2) mod(4503599627370517) = 2399714771200811, and 2399714771200811 < 3451657199285664, this means that 2 is also an Eulercoin

    • This way we only need to check Eulercoin from 1 to 15806432, which is very manageable!

And with that we have bi-directionally searched both directions takes ~10 seconds

Interactive Code

No Interactive code for this problem, my code is given below