Problem: Imagine a sequence 1504170715041707*n mod 4503599627370517 where n is an integer increasing from 1. Find the subsequence of this sequence where every next element is smaller than a previous one.
All the solutions I’ve read about include brute force calculations. I found a better one and I can’t stop myself from posting it.
Formal problem description:
Leonhard Euler was born on 15 April 1707.
Consider the sequence 1504170715041707n mod 4503599627370517.
An element of this sequence is defined to be an Eulercoin if it is strictly smaller than all previously found Eulercoins.
For example, the first term is 1504170715041707 which is the first Eulercoin. The second term is 3008341430083414 which is greater than 1504170715041707 so is not an Eulercoin. However, the third term is 8912517754604 which is small enough to be a new Eulercoin.
The sum of the first 2 Eulercoins is therefore 1513083232796311.
Find the sum of all Eulercoins.
An obvious solution would be running operation x = (x + 1504170715041707) % 4503599627370517 in the loop and saving x as Eulercoin every time when it’s smaller than the previous one. This approach can find the first few Eulercoins relatively fast but it will take more time for every next one. Our input numbers are coprime so it may take up to 4503599627370517 iterations to find the last Eulercoin.
We need to find a better way.
Let’s rephrase the task: we already know some Eulercoins and all we want to find is the next value.
We can imagine the range from 0 to 4503599627370516 as a circle with 0 on top. A point is jumping on the circle surface with a step size of 1504170715041707.
Every time a point lands on a green area – we’ve got a new Eulercoin. We can reduce the green area size and start again.
We can find an interesting pattern: every time a point completes a full circle – it looks like we moved the first point back at the shift distance. Even more, we shifted every point on the circle.
Shift is always smaller than step. Can we use it instead of step in order to find an answer faster?
Yes, we can. If we reverse jumping direction and replace step with shift – we’ll face the same problem except we’ll have step size as a circle size. That’s because we want to shift every point.
It turns out we need to recursively solve the same problem with smaller parameters. The complexity of finding every new Eulercoin would be log2(4503599627370517) in the worst case, that’s not much.
A solution in Scala looks like this:
import scala.collection.View.Unfold
val x: Long = 1504170715041707L
val m: Long = 4503599627370517L
def nextCoin(step: Long, limit: Long, max: Long): Option[Long] = {
if (limit == 1) {
None
} else if (step < limit) {
Some(step)
} else {
val shift = max – max / step * step
nextCoin(shift, limit, step).map(limit – _)
}
}
val coins = new Unfold[Long, Long](m)(last => nextCoin(x, last, m).map(x => x -> x)).toList
println(coins)
println(coins.sum)
Of course, it can be optimized by finding all the Eulercoins in one go or adding tail recursion optimization, but even in this state solution finishes immediately after running.
Do you want more solutions in this blog? I won’t continue with project Euler (they don’t like it) so please let me know if you know some good puzzles.
Permanent link to this post here
