IBM Ponder This #305 · September 2023

This riddle was proposed by Marco Bellocchi - thanks Marco!

Define a sequence $a_1,a_2,a_3$ recursively by setting $a_n=a_{n-1}+\text{gcd}(n,a_{n-1})$ where $\text{gcd}(x,y)$ denotes the greatest common divisor (GCD) of the pair of numbers x, y.
For example, when $a_1=11$ we have $a_2=12$ since $\text{gcd}(2,11)=1$, and we have $a_3=15$ because $\text{gcd(3,12)=3}$.
Continuing, we arrive at the sequence:

11, 12, 15, 16, 17, 18, 19, 20, 21, 22, 33, 36,...

We now look at the sequence of differences beginning from $n=2$, $d_n=a_n-a_{n-1}=\text{gcd}(n,a_{n-1})$:

1, 3, 1, 1, 1, 1, 1, 1, 1, 11, 3, ...

(i.e., $d_2=1$ is the first element of the sequence, $d_3=3$ is the second, etc.)

A curious property enjoyed by this sequence is that it contains only the number 1 and the prime numbers 3, 11. If we continue this sequence long enough and erase all the occurrences of 1, we arrive at this sequence

3, 11, 3, 23, 3, 47, 3, 5, 3, 101, 3, 7, 11, 3, 13, 233, 3, 467, 3, 5, 3, 941, 3, 7, 1889, ...

which contains only prime numbers. It can be proven that indeed, when $a_1=11$, all elements of the sequence obtained in this manner will be prime.

Returning to the original difference sequence, it is easy to see that $3=d_3=d_{12}=d_{24}=d_{48}=d_{51}$ and these are the first 5 occurrences of 3 in the sequence. Hence, 3 appears for the fifth time for $n=51$.

Your goal: For the sequence defined by $a_1=531$, find the value of $n$ for which 5 appears for the tenth time.

In addition, find values $k,n$ such that for the sequence defined by the initial value $a_1=k$, we have $d_n>1$ but not a prime.

A Bonus "*" will be given for finding, for the sequence defined by $a_1=531$, the value of $n$ for which 5 appears for the 200th time.

Solution

Best opened after a real attempt

To be added.