Project Euler 443 - GCD Sequence

Official link:

Thought Process

A bit of an unsatisfying solution for this problem. 

My thinking was simply that we need a smart way to find where the "jumps" (that is when gcd(n, g(n- 1)) > 1) are since if there is no jump then g(n) = g(n - 1) + 1

I first printed a table which finds when the jumps occur, and how big was the jump

For example the first jump happens at n = 6, and it took 2 increments of n to reach the jump, then the next jump is at n = 9 and it took 3 increments to reach the jump.

I then noticed a strange pattern in the decomposition of n where the "bigger" jumps occurred. For example at n = 17 our first big jumps occurs and it is 9*2 - 1, and n = 9 was our last jump and this happens to often to be a coincidence.

While looking for a pattern between the n at which big jumps occur, I noticed that they were all prime, I add a quick check and sure enough every big jump happens at a prime n and every other jump is not prime.

See the table below for details.

Using this it was easy to come up with a semi brute force solution.

For example lets say we are at n = 9, g = 18

One thing to note is that it seems there is only once case where this pattern does not work and that is when n = 6, since 2*6 - 1 = 11 is prime, but no jump happens there so I manually calculate g(5), g(6) and the do the process listed above

Interactive Code

Input an integer (yourinput)

Code will output g(yourinput)