Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
What pattern?${}$ –  gammatester Feb 13 at 11:00
    
@gammatester The pattern is that each starting point for a record number of steps is itself prime. –  Mark S. Feb 23 at 23:21

1 Answer 1

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.

share|improve this answer
    
+1 for sure - quite nicely-put! –  Steven Stadnicki Feb 24 at 0:22
1  
@Mark S. Thanks v. much for answer -- and sorry for being so long in saying so. I thought I'd be informed by email when an answer was made, so didn't see it at the time. –  user127879 Jun 30 at 8:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.