I've looked at the sequences created by repeatedly adding the digital root of a number to the number until it becomes prime. This is the pseudo-code for the program I've used:
n = 0
best = 0
repeat
n = n + 1
if n mod 3 = 0 then n = n + 1
c = 0
n1 = n
repeat
n1 = n1 + digital_root(n1)
c = c + 1
until isprime(n1)
if c > best then
showsequence
best = c
endif
until stop
The successive records for the longest sequence all seem to begin with primes (including 1 as a prime and excluding multiples of 3, which never produce primes in base 10). For example:
1 + 1 = 2.
2 + 2 = 4; 4 + 4 = 8; 8 + 8 = 16; 16 + 7 = 23.
19 + 1 = 20; 20 + 2 = 22; 22 + 4 = 26; 26 + 8 = 34; 34 + 7 = 41.
(N.B. digital root of 19 = 1, because 1 + 9 = 10 → 1 + 0 = 1)
43 + 7 = 50; 50 + 5 = 55; 55 + 1 = 56; 56 + 2 = 58; 58 + 4 = 62; 62 + 8 = 70; 70 + 7 = 77; 77 + 5 = 82; 82 + 1 = 83.
Successive records:
1 takes 1 step to create 2
2 takes 4 steps to create 23
19 takes 5 steps to create 41
43 takes 9 steps to create 83
113 takes 12 steps to create 167
479 takes 15 steps to create 547
953 takes 20 steps to create 1049
1303 takes 22 steps to create 1399
[...]
1057181 takes 89 steps to create 1057579
Is this pattern real or have I misunderstood something? If it is real, is there a simple explanation for it?
Yes, this pattern has a simple explanation. On an intuitive level, if a record started from a non-prime $n$, then you might be able to go back a step to a number that would generate $n$ on the next step, so that the record-breaker would actually be less than $n$. (This doesn't work for primes because a "previous number" for a prime would have at most one step until it reached a prime, and wouldn't be a record-breaker.) In-depth details/supporting facts below.
The operation here is adding the digital root. I'll define $d(n)$ to be the digital root of $n$ and $f(n)$ to be $n+d(n)$.
Fact 0: $f(n)=2n-9\lfloor(n-1)/9\rfloor$.
Note that as wikipedia mentions, $d(n)=n-9\lfloor(n-1)/9\rfloor$ (where $\lfloor m\rfloor$ denotes the floor).
Fact 1: Given $n>9$, $n=f(m)$ for at most one number $m<n$.
Since digital roots are in the range of $1$ through $9$, the only possibilities for $m$ are in $\{n-9,\ldots,n-1\}$. However, the digital roots of those numbers are going forwards through the cycle $(1,2,3,4,5,6,7,8,9)$ at some starting point $D$, we have that $\{f(n-9),\ldots,f(n-1)\}=\{n-9+D,n-8+D+1,\ldots,n-1+d+8\}=n+D+\{-9,-7,-5,-3,-1,1,3,5,7\}$ are all distinct modulo $9$, so that only one of them is congruent to $n$ modulo $9$.
Fact 2: Given $n>9$, $n=f(m)$ for precisely $m=n-d(5n)$.
$d(5n)=5n-5n\lfloor(5n-1)/9\rfloor$ for $n=10,11,\ldots$ repeats in the pattern $5,1,6,2,7,3,8,4,9,\ldots$. And for $n=5,6,\ldots$, $d(n)=5,6,7,8,9,1,2,3,4,\ldots$. By periodicity, it suffices to check that this works in the first 9 cases: $(10-d(5*10))+d(10-d(5*10))=5+d(5)=f(5)=10$, $f(10)=11$, $f(6)=12$, $f(11)=13$, $f(7)=14$, $f(12)=15$, $f(8)=16$, $f(13)=17$, $f(9)=18$.
(Note: Facts 1 and 2 apply for $n=2,3,4,5,6,7,8,9$ by manual checking.)
Record-breakers greater than $1$ must be prime.
Suppose $n>1$ is not a prime but breaks a record. Then by Fact 2, $f(n-d(5n))=n$ so that $n-d(5n)<n$ would take one more step than $n$ to get to the same prime (since $n$ isn't prime). This contradicts the fact that $n$ is a record-breaker since a lower number takes more steps.