An extremely inefficient divisibility criteria for sleepless people
2 AM. I should be sleeping, but my brain is working. Too many videogames and UX design are keeping me awake I think. But this has always been like this. I always loved to discover new things and trying inventing something new, and combined with insomnia this creates a lethal mix.
“can you recall to mind all divisibility criteria?”
Shut up brain. It’s 2 A.M. Well no I can’t remember all of them. Just the rule of 3. “if the sum of all digits gets to a number divisible by 3, then the number is divisible by 3”.
But what about other numbers? is there any way to get a criterion?
The principle of 9
If we look carefully at 9, we notice that every time it changes a ten (9,18,27,36…) it loses one number on the units. That number is exactly 1, which is the difference between 10 and 9.
This is obvious and works for every other number: if we get 7, it tends to lose 3. (7,14,21…). It’s like the tens are memorizing the 3. Every time you get a ten, a 3 is lost on the right.
That 3 is remembering me something: the rule for 7.
Multiply by 3 the first most significant digit….
And randomly I asked myself: “what happens if I tweak this principle to other numbers?”
Well after some tries I found out something very strange.
The Doremi’s conjecture (pardon me)
What happens if I multiply the tens (remember that 7 lost 3 for every ten gained) for the number lost in multiplying, and then add the remaining unit?
An example:
is 112 divisible by 7?
Let’s consider D as 10-K, where K stands for the divisor we test. the D for 7 is obviously 10–7 = 3.
Let’s multiply the tens of 112 by 3 and add the remaining unit.
11*3 + 2 = 35.
Well, that is interesting. It is divisible by 7. Let’s try another number with the same technique.
is 171 divisible by 9?
10-K = 10–9 = 1.
17*+1 = 18. Again divisible.
What about numbers bigger than 10?
is 121 divisible by 11?
10-K = 10–11 = -112*-1 + 1 = -11.
Works. Yes, we tested divisible numbers, but if they aren’t they’ll generate non-divisible numbers.
is 78 divisible by 8?
10-K = 10–8 = 2
7*2+8= 22. Not divisible by 8. as expected.
Works perfectly.
a K value equal or bigger than 20
Here is why I define it as extremely inefficient: multiplying for numbers of this size generates a number that is bigger than the precedent one. Not very useful indeed.
Is 400 divisible by 30?
10-K = 10–30 = -20
40*-20 + 0 = -800. Well that’s bad.
I’ll try to find out if there is any other tweak to the principle, maybe there is a solution. Now it’s 5 AM. I can go to sleep, night night.
The algorithm in a nutshell
We have now defined an algorithm, given a number N and a divisor K :
- calculate D = 10-K
- multiply the tens of N by D
- add the units
- if the number obtained is not enough (to say it’s divisible), go to step 2.
The proof
As I stated before, I suck at maths and I don’t really know why and how this works. I just figured out randomly. But this is the fascinating part: I could invent something without even knowing how. Thanks, brain.
An inspiring quote
Even if you totally suck at something, do not surrender and try to learn something new. A lot of inventions were made accidentally, and you can’t even consider them “new” if they were already known. This is just a bad algorithm no one will ever use, but it’s important for me and you: Everyone can find out something curious by trying.
