Project Euler 443 - GCD Sequence

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

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.

I simply increment n and keep a record of g, that is g = g(n - 1),
Then if gcd(n, g) > 1 then we are at a jump
1. then if 2n - 1 is a prime number then the next jump occurs at 2n - 1
2. This means that all the numbers between n and 2n - 2 do not have a jump, hence we can add gcd(n, g) + n - 2 to g
3. We can then directly increment n to 2n-1.
If 2n - 1 is not prime, then we just add gcd(n, g) to g

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

Now gcd(9, g) = 9 > 1
1. We check if 2*9 - 1 = 17 is prime, which it is, hence we know that the next jump is going to happens at n = 17.
2. Knowing where the next jump is we know that g(16) = 2*9 - 2 - 9 + g(9) = 7 + g(9) = 7 + gcd(9, g) + g = 7 + 9 + g as desired
3. Then set n = 17 and we continue with n = 17, g = 34 just as we want.

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)

Page updated

Google Sites

Report abuse