3
$\begingroup$

Preface: I don't have any background in number theory, but I tried researching this first.

The other day I noticed that if I start with the number $11$ and add $18$ to it repeatedly, most of the subsequent numbers (at least at the start) also have a digit sum of 2 if I repeatedly reduce the digit sum until I have a single number.

i.e. \begin{align*} 11 &\rightarrow 1 + 1 = 2 \\ 11+18 = 29 &\rightarrow 2 + 9 = 11 \rightarrow 1 + 1 = 2 \\ 29 + 18 = 47 &\rightarrow 4 + 7 = 11 \rightarrow 1 + 1 = 2 \end{align*}

Also, most of the numbers in this period of 18 are prime!

Then I realized that I could do the same digit sum classification with the numbers $[1, 2, 4, 5, 7, 8]$ respectively, and it looks like I am accounting for all primes (and some non primes) by adding $18$ to some starting value. (sum below means digit sum)

    1 start , sum 1  11 start, sum 2  13 start, sum 4  17 start, sum 8  \
0                 1               11               13               17   
1                19               29               31               35   
2                37               47               49               53   
3                55               65               67               71   
4                73               83               85               89   
5                91              101              103              107   
6               109              119              121              125   
7               127              137              139              143   
8               145              155              157              161   
9               163              173              175              179   
10              181              191              193              197   

    5 start, sum 5  7 start, sum 7  
0               23               7  
1               41              25  
2               59              43  
3               77              61  
4               95              79  
5              113              97  
6              131             115  
7              149             133  
8              167             151  
9              185             169  
10             203             187 

If I make a mask where $\text{True}$ indicates the number is prime

    1 start , sum 1  11 start, sum 2  13 start, sum 4  17 start, sum 8  \
0              True             True             True             True   
1              True             True             True            False   
2              True             True            False             True   
3             False            False             True             True   
4              True             True            False             True   
5             False             True             True             True   
6              True            False            False            False   
7              True             True             True            False   
8             False            False             True            False   
9              True             True            False             True   
10             True             True             True             True   

    5 start, sum 5  7 start, sum 7  
0             True            True  
1             True           False  
2             True            True  
3            False            True  
4            False            True  
5             True            True  
6             True           False  
7             True           False  
8             True            True  
9            False           False  
10           False           False 

So then I pushed a Sieve of Eratosthenes algorithm past $10 ^ 8$ and witnessed that the membership frequency of the next $1000$ primes were near-equal across the 6 different classes below, and all looked to be accounted for. I would also be curious to see how the frequency of composites in the series increase (as I'm sure they do) as the series gets longer.

Question

This seems like it would be a technique to reduce the number of values one would have to check to generate prime numbers. Is there a name for a technique like this (assuming my maths aren't entirely wrong here), and is ther some special quality about the number $18$ that allows me to add it like this to get digit sums like below?

$\endgroup$
  • 4
    $\begingroup$ You've run into the property that a number $x$ and the sum of its digits have the same remainder modulo $9$. Of course, since the procedure terminates, you'll always end up with a number in $\{0,1,2,3,4,5,6,7,8\}$. Prime numbers $\ge5$ cannot have remainders $0$, $3$ or $6$, otherwise they'd be in the form $p=9h+3$ (or $6$ or $0$) and thus multiples of three. A special instance of this fact is taught in primary school as "divisibility criteria by $3$ or $9$". $\endgroup$ – user228113 Sep 3 '17 at 15:17
  • $\begingroup$ @G.Sassatelli That pretty much clears up my moment of wonder. if you wanted to put that comment in an answer I would be happy to accept it, but in any case thank you! $\endgroup$ – Eric Hansen Sep 3 '17 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.