Algorithms

Solution for Project Euler Problem #700: Eulercoin

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 the 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 whenever 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.

A step Multiple steps

Every time a point lands on the green area – we've got a new Eulercoin. We can reduce the green area size and start again.

A point landed in green area Green area shrunk

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.

A shift Multiple shifts

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 our circle gets smaller. It shrinks to a size of step. That's because we want to shift every point.

Reduced scope Multiple reduced scopes

It turns out we need to solve the same problem with smaller parameters. That's recursion. 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 when someone posts solutions), so please let me know if you know some good puzzles.

Tags: , , ,

Comments