Is this rule of sums of digits (1 to 9 repeating) named? also method for div by 3?

M.T. Cranium

I was doing some work on prime number identification rules and happened to come up with two interesting results that are probably known already and named, but in which case I was wondering, what are they named?

First rule is this -- keep adding the digits of numbers until you reduce to any one-digit final reduction (1 to 9). Then the numbers from 1 to infinity will be a never-ending series of 1 to 9.

For example, 10 reduces to 1, then 11 to 18 will reduce to 2 to 9.

Then 19 reduces to 10 and then 1, 20 to 27 reduce to 2 to 9.

etc etc

3007 = 10 = 1, 3008 = 11 = 2, ... 3015 = 9.

478225 = 28 = 10 = 1
478226 = 29 = 11 = 2
etc

This observation is the foundation of another rule which is that all multiples of 3 reduce in this same way to a multiple of 3 (3 6 or 9). And all other numbers do not.

This is fairly elementary to prove if the former conjecture is correct, since all multiples of 3 will fall in 3rd, 6th and 9th positions in the sequences.

So this got me to thinking, if I want to test a large odd number to be a multiple of 3, aside from dividing it by 3 I can also find out this way.

87231502229152890722341153

reduces to 94 which reduces to 13 or 4, so this is not a multiple of 3.

However, here's something even faster, every time there's a 9 count that as zero, so the number adds up to 76 (13 or 4).

Also faster, just ignore all 3s and 6s in the chain of digits, and the zeroes, in this case that reduces the number to 8721522215287224115 (67 or 13 or 4).

(why ignore the 3s and 6s? because a number 3 x 10^n would be a multiple of 3 so to remove that from the number will not change the logic).

(why ignore the zeroes? because we are testing the sum of digits)

Another time reducer in this method ... start summing from the left, each time you get a multiple of 3, start over.

87231502229152890722341153
87 = 15
231 = 6
5022 = 9
291 = 12
528 = 15
9
072 = 9
234 = 9
1153 = 10

(10 is 1 greater than a multiple of 3 as with 4).

This predicts that multiples of 3 will be

87231502229152890722341155
87231502229152890722341161

Is there a simpler method? One is to remove the multiples of 3 and zero, then count the other digits. Remove every cluster of three. Taking the first number, first I remove the zeroes, 3s, 6s and 9s

8721522215287224111

There are five 1's so leave 2 of those

8725222528722411

There are seven 2's so all but one of those can all go

87555872411

There are three 5's so those can all go

87762411 is the remnant

That adds up to 36 = 9.

---

Looking at primes, I noticed that there are very few exceptions to this rule, if digits add up to powers of 2, including 1, then it's a prime. And if the sum is 5 or 7 (these are the only numbers left once you remove multiples of 3) many of these are primes, but the frequency drops off faster.

I will post examples next.

But first, interested to know if my conjectures about multiples of 3 are familiar under another name or system? (see post 3, I discovered that this method is even faster than I thought).

M.T. Cranium

PRIMES and NON-PRIMES illustrating the frequency of tests verifying, to 247
_____________________________________________________________

PRIMES _______________ Non-primes (excluding multiples of 3 or 5)

(starting with 5) ________ multiples of 3 excluded as per rules in post #1

5, 7 __________________ multiples of 5 end in 5

11 = 2 _________________ ... ... ... ... ... ____ frequency of exceptions (>2)

13 = 4 ... ... ... ... ... ... ... ... 49 = 13 = 4 ______1 in 14
17 = 8 ... ... ... ... ... ... ... ... 77 = 14 = 5 ______2 in 20
19 = 10 = 1 ... ... ... ... ... ... 91 = 10 = 1 ______3 in 24
23 = 5 ... ... ... ... ... ... ... ..119 = 11 = 2 ______4 in 30
29 = 11 = 2 ... ... ... ... ... ..121 = 4 __________ 5 in 31
31 = 4 ... ... ... ... ... ... ... . 133 = 7 __________ 6 in 33
37 = 10 = 1 ... ... ... ... ... . 143 = 8 __________ 7 in 36
41 = 5 ... ... ... ... ... ... ... . 161 = 8 __________ 8 in 40
43 = 7 ... ... ... ... ... ... ... . 169 = 16 _________ 9 in 42
47 = 11 = 2 ... ... ... ... ... . 187 = 16 ________ 10 in 47
53 = 8 ... ... ... ... ... ... ... . 203 = 5 _________ 11 in 52
59 = 14 = 5 ... ... ... ... ... . 209 = 11 = 2 _____ 12 in 53
61 = 7 ... ... ... ... ... ... ... . 217 = 10 = 1 _____ 13 in 55
67 = 13 = 4 ... ... ... ... ... . 221 = 5 __________14 in 56
71 = 8 ... ... ... ... ... ... ... . 247 = 13 = 4 _____ 15 in 63
73 = 10 = 1
79 = 16
83 = 11 = 2
89 = 17 = 8
97 = 16
101 = 2
103 = 4
107 = 8
109 = 10 = 1
113 = 5
127 = 10 = 1
131 = 5
137 = 11 = 2
139 = 13 = 4
149 = 14 = 5
151 = 7
157 = 13 = 4
163 = 10 = 1
167 = 14 = 5
173 = 13 = 4
179 = 17 = 8
181 = 10 = 1
191 = 11 = 2
193 = 13 = 4
197 = 17 = 8
199 = 19 = 10 = 1
211 = 4
223 = 7
227 = 11 = 2
229 = 13 = 4
233 = 8
239 = 14 = 5
241 = 7

The frequency of non-excluded non-primes eventually becomes greater than half. I have no real idea of what proportion it reaches in larger number sets. But as the number of large primes multiplied together is considered, it clearly becomes quite large eventually.

M.T. Cranium

With a bit of work I discovered that my method for testing multiples of 3 is even faster than I thought. Check this out ...

In the sequence of numbers, just eliminate all 3, 6, 9 and 0.

Reasons for removing 3,6,9 should be fairly obvious (e.g., 6 in position 5th from end indicates that number is 60,000 plus the number you create by changing it to zero, if it was divisible by 3 then the new number is.

Same logic for 3 and 9.

For zero, the logic is that your new number from left end (start) to that point is now one tenth of the old number that was there.

Example 527840xyz changing to 52784xyz is now reduced from 10000A + xyz to
1000A + xyz (where A in this case is 52784) ... your new number is therefore reduced by 9000A which has to be divisible by 3, so the test value of 527840 will be preserved by the test value of 52784.

Okay, so if we can remove all 3, 6, 9 and zero from the very long numbers, that leaves only 1, 2, 4, 5, 7 and 8. If you wanted to do so, you could reduce all 4 and 7 to 1, and all 5 and 8 to 2. This is because you would be removing multiples of 3 x 10^n from these test numbers.

Finally, you can then cross out any groups of consecutive numbers that are multiples of 3. And you can keep doing that with the reduced value.

Look how fast this is. Let's take this very long number:

7890684784761529323909970590192054202316166782389071238906123

Feel like dividing that by 3? It would take a while. But watch this:

1. Remove all 3, 6, 9 and 0

78847847152275125422117828712812


2. Remove all consecutive numbers that are multiples of 3 (from inspection using ones that are easily spotted) ... such as 78, 84, 78 then 15, 27, 51, 54,21, 78, 87, 12 81 ... you can't use a number twice, as for example 784 cannot yield 78 and 84 to remove 784, you must remove either 78 or 84, I removed 78.


47222122

3. Do it again (72 and 21 go out)

4222

4. and one more time 10 = 1 (or removing 42, 2+2 = 4 reduces to 1).

that means this number is not a multiple of 3 (it must be 1 more than a multiple of 3).

Test it out for yourself with other numbers.



7890684784761529323909970590192054202316166782389071238906123 / 3 =
2630228261587176441303323530064018067438722260796357079635374 rem 1

Here's a shorter one to try

89456121717178843952361

(do it in your head and scroll down to see)







894561 reduces to 8451 which you can toss (84, 51)

2171717 reduces to 71717 which reduces to 11111 or 5 or 2 ...

88439 reduces to 884 or 221 or 5 or 2 ... now we're at 4 or 1 ...

52361 reduces to 521 which reduces to 5, or 2, which makes 3, so this number is
divisible by 3.

test

89456121717178843952361 / 3 =

29818707239059614650787

Here's another interesting factoid ... in base 7, the same rule applies, multiples of 3 will produce the same test and results (but 7, 8 and 9 won't appear in your work).

example ... 2943 in base 7 would be 11403.

2943 for test = 24 = divisible by 3

11403 for test = 114 = divisible by 3 (114 is 60 in base 7 so that also works).

TheOneWhoDraws

The response is a bit late but:

1) What you're doing is determining the digital roots of numbers.

2) The reason a number is divisible by 3 the digital root is divisible by 3 is because:

PRELIMINARY: This assumes you are familiar with the concept of modular arithmetic and congruence classes. If not, x = r (mod d) means x = dq+r, where r can be any number from 0 up to d-1 (but it can't be d, as if r=d, then r=0 as x = dq+d = d(q+1) + 0). So basically r is the remainder under division, by a number d.

(In base 10) N = abcd...z where the K digits (it's arbitrary, just because there are 26 letters in the alphabet and I'm representing the digits with a to z does not mean I'm taking K=26, it's only because it makes the representation nicer) are elements of Z (mod 10). I'm using capital letters throughout to differentiate from the digits

i) N = (10^K)a + (10^(K-1))b + ... + 10y + z

ii) Observe that 10 = 1 (mod 3)

iii) N = a + b +...+ y + z (mod 3) (as 10^K = 1^ K = 1 mod 3)

If N=0 (mod 3) then a+b+...+z = 0 (mod 3), so N is divisible by 3 if and only if the digits are divisible by 3.

3) For the divisibility test by 9, it's the same thing:

i) N = (10^K)a + (10^(K-1))b + ... + 10y + z

ii) Observe that 10 = 1 (mod 9)

iii) N = a + b +...+ y + z (mod 9) (as 10^K = 1^ K = 1 mod 9)

If N=0 (mod 9) then a+b+...+z = 0 (mod 9), so N is divisible by 9 if and only if the digital root is divisible by 9.

4) In other bases, it's similar. We'll denote the base by B.

i) n = (B^K)a + ((B-1)^(K-1))b + ... + By + z

ii) Observe that if B = 1 (mod X)

iii) Observe that by definition, B = 1 (mod X) means
B = XQ +1
B-1 = XQ (this step isn't even necessary, it's just if you're unfamiliar with modular arithmetic)
B-1 = 0 (mod X). [This also gives us conditions on what X is, as X = (B-1+R)*Q^((-1)), so you can rewrite all of this in terms of B-1 as well if you wish with some slight adjustments; this is more useful if the base is very large]

iv) N = a + b +...+ y + z (mod X) (as B^K = 1^ k = 1 mod X)

If N = 0 (mod X) then a+b+...+z = 0 (mod X), so N is divisible by X in base B if and only if the digital root is divisible by X.

5) In other (natural number) bases, this can also be generalised. B=XQ+R for 0<= r < q

N = ((XQ+R)^k)a + ((XQ+R)^(B-1))b + ... + (XQ+R)y + z

N = (XQ+R)* [ ((XQ+R)^(k-1))a +((XQ+R)^(k-2))b + ... + y ] + z

You can use the binomial theorem on the powers of XQ+R to simplify this expression. However, we can make some pretty trivial observations in the case where R=0 (B=0 mod X) (#), R=1 (B =1 mod X) (##), or R = B-1 = -1 ( B = X-1 = -1 mod X) (###)

# Clearly
N = (XQ)* [ ((XQ)^(k-1))a +((XQ)^(k-2))b + ... + y ] + z
N = (0)* [ ((0)^(k-1))a +((0)^(k-2))b + ... + y ] + z (mod X)
N = z (mod X)
So X divides N in this case if and only if z (the final digit) = 0 (mod X)

Example: B=10 = 2(5) + 0.
N = z (mod 2).
If z=0, 2, 4, 6, 8, we have z=0 (mod 2) and N divisible by 2.
If not, then z= 1,3,5,7,9 = 1 (mod 2)

## Clearly
N = (XQ+1)* [ ((XQ+1)^(k-1))a +((XQ+1)^(k-2))b + ... + y ] + z
N = (1)* [ ((1)^(k-1))a +((1)^(k-2))b + ... + y ] + z (mod X)
N = a + b + ... + z (mod X)
So X divides N in this case if and only if the digital root is = 0 (mod X), and the remainder mod X will be the sum of the digits.

Example: B= 10 = 3(3) + 1. (also 9+1)
N = a+b+c+...+z (mod 3).
N=some number with the digits 9, 8 ,7, 6, 0 (doesn't matter where, in the number they are, and zero, nine, three and six can be repeated as many times as you want in this number since they're the same mod 3)
N=9+8+7+6 = 0+ 2 + 1 + 0 = 0 + (0) + 0 = 0 mod 3.

### Trickier, only just.
N = (XQ-1)* [ ((XQ-1)^(k-1))a +((XQ-1)^(k-2))b + ... + y ] + z
N = ((-1)^(k))a +((-1)^(k-1))b + ... + (-1)y + z (mod X)

Note the parity here matters. You can group every second term together this way, because it'll change from an even power to an odd power every term, and hence it'll switch from even to odd:
N = ((-1)^k) (a + c + e +...+) + ((-1)^(k-1))*(b+d+f+...+) + z (mod X)

So if there are an even number of digits:
N = a + c + e + ... + (second last digit) - b - d - f -... - (third last digit) + z (mod X)
[i.e. N = a -b + c - d + e ... + z (mod X)]
So N is divisible by X if and only if (a -b + c - d + e ... + z) = 0 (mod X)

Example: B = 10 = 11(1) - 1.
N=2222 has even number of digits
2 -2 + 2 -2 = 0 (mod 11) so divisible by 11

So if there are an odd number of digits:
N = -a - c - e - ... - (second last digit) + b + d + f -... + (third last digit) + z (mod X)
[i.e. N = -a +b - c + d - e ... + z (mod X)]
So N is divisible by X if and only if ( -a +b - c + d - e ... + z ) = 0 (mod X)

Example: B = 10 = 11 - 1
N = 121 has an odd number of digits
1 -2 +1 = 0 (mod 11) so divisible by 11.

EDIT: You can use similar rules/manipulation to construct(!) many different division rules, in different bases by considering the digital sum and the digital root. I hope you will find this to be a sufficient explanation for what exactly is happening, and precisely why.

The reasoning in this post should be sufficient to explain the following rules in base ten:

n divisible by 2 iff the final digit z is even
n divisible by 3 iff the digital root is divisible by three.
n divisible by 5 iff the final digit z ends in 5 or 0 (by observing 5 = -5 = 1*5 = (-1)*5 mod 10, and 10 = 0 mod 5, so the final digit is the only not affect and thus z= 0 or 5)
n divisible by 6 iff even and digital root divisible by 3 (by observing 6=2*3)
n divisible by 9 iff Digital root is divisible by 9.
n divisible by 10 iff final digit z=0
n divisible by 11 iff (depends which case).

You can add more by similar construction. Some further challenges you might like from this: Can you determine what the rule is for 4, 7, and 8 base 10?

EDIT: I thought I would directly comment on your base 7 observation since while I've clarified it above, I've not done so explicitly. 7 = 1 mod 3, hence why it satisfies the rule. If you take base 4, 7, 10, 13, 16, etc this rule will all hold for 3. If you take base 5, 8, 11, 14 it will fail since, mod 3, they're in the equivalence class of 2 (you may get some exceptions, however, since 2 = -1 mod 3, so they'll all satisfy the divisibility rule for 11 base 10).. If you take base 3, 6, 9, etc you're going to get the divisibility rule for 10 mod 10 since they're in the congruence class of zero (mod 3).