Cool how to: Determine "divisible by three" without doing addition, subtraction, multiplication or division
An Innocent Icelander
It's possible to determine whether a number is divisible by three
without doing any addition, subtraction, multiplication or division.
Well, sort of- you do have to do some counting which is effectively
"adding 1." But it sounds less impressive that way.
Here's how:
Step 1: Scan through the number from left to right (or right to left,
it doesn't matter). Every time you encounter the digits 1, 4 or 7,
count up from 1 to 3, starting over when you get to 3. For example,
if the number were 1471744, you would count 1,2,3,1,2,3,1. Make note
of how many "leftover" 1/4/7 digits there were. In the above example,
it would be 1. There will be at most two leftover 1's, 4's or 7's
(since any more would have made another set of three).
Step 2: Scan through again, this time for the digits 2,5, and 8.
Again, make note of how many leftovers of those digits there were.
Step 3: Evaluate. Mark (mentally or on paper) a "1" for every 1, 4 or
7 left over and a "2" for every 2, 5 or 8. If the result is
"empty" (i.e. no leftover digits of either set), the result is 12 or
the result is 1122, then the number was divisible by three.
Why it works:
The "traditional" way of determining divisibility by three for Base 10
integers is to take the sum of each digit, and if the sum is divisible
by three then so is the original number. This should be pretty
familiar to anyone who reads this newsgroup, and there are dozens of
proofs available on the internet, so for the purposes of this
discussion we'll consider it to be (effectively) an axiom.
Most people stop right there, but let's take it a little further. If
it can be PROVEN that the digits of a Base 10 integer add up to a sum
divisible by three, then there is no reason to do the actual
addition. Using that as a guiding principle, the familiar rule might
be restated as "if it can be shown that the sum of the digits of a
Base 10 integer is divisible by three, then the number itself is also
divisible by three."
This is actually pretty easy. First, remember that we don't care WHAT
the sum of the digits is. We only care that we can prove the sum is
divisible by three.
Any combination of three 1's, 4's or 7's is divisible by three.
That's because 1=(0*3+1), 4=(1*3+1) and 7=(2*3+1). The sum of any of
those three digits can be rewritten as the sum of the "coefficients"
of 3 times three, plus the sum of the "remainders" like so: (c1 + c2 +
c3) * 3 + (1 + 1 + 1). The first part is obviously divisible by
three. The second adds up to three, which is again obviously
divisible by three. So therefore the sum of the three digits itself
is divisible by three.
The same logic applies to triplets of digits 2, 5 and 8, with the only
difference being the "remainders" are 2, not 1.
So all triplets of 1,4,7 or 2,5,8 can be rewritten as SOME coefficient
times 3. We just don't care what that coefficient is. That's because
the sum of all triplets of 1/4/7 and 2/5/8 in a number with n such
triplets is the sum of all those (c1 + c2 + c3 ... + cn)*3, which
again is obviously divisible by 3. So there's no real reason to know
or care what each coefficient is, just that the sum of all of them
(times 3) is divisible by 3.
We didn't mention digits 0, 3, 6 and 9 in the method above simply
because the same logic applies. Any of those digits can be rewritten
as a product of 3. (i.e 0=0*3, 3=1*3, 6=2*3 and 9=3*3.) The sum of
all of those digits in a number with "n" 0's, 3's 6's and 9's is the
same as the sum of the "coefficients" of 3, times 3. (c1 + c2 +
c3 ... + cn)*3, which is again obviously divisible by three.
The ONLY things remaining are the 1's, 4's, 7's and 2's, 5's 8's that
didn't get into a triplet of three of those sets of digits. We again
ignore the "3's component" of each and only concern ourselves with the
remainders. There will be at most 2 from each set, making the only
possible combinations:
*nothing* or, better stated: 0*3, which is divisible by 3
1: not divisible by 3
2: not divisible by 3
1+2: divisible by 3
1+2+2: not divisible by 3
1+1+2: not divisible by 3
1+1+2+2: divisible by 3
For very long numbers, this method will be much faster than the
traditional method. For a 300-digit number, the traditional method
would require 299 addition operations. This method requires nothing
more than the ability to count to three repeatedly. An alternative
would be to ignore all the 0's, 3's, 6's and 9's, and only add up the
other digits, which is also faster.
For a bar trick, I recommend asking someone to write down as many
random digits as they like on a sheet of paper, and bet them that you
will be able to determine divisibility by three without doing any
addition, subtraction, multiplication or division. When they've
written the number down, tell them to mark an A above all 1's, 4's and
7's, and a B below all 2's, 5's and 8's. Then have them put commas
between sets of three As above and sets of three Bs below. Instead of
evaluating a 12, 112, etc. you'll be evaluating an AB, AAB, etc. which
looks much less like arithmetic.
Cheers!
P.S. This method works equally well for numbers in any Base 3 or
higher. The only difference is that the three different sets of
digits (digits who are divisible by 3, digits whose "remainder" is 1,
and digits whose "remainder" is 2) will have more or fewer members.
For example, in hexadecimal, digits 0, 3, 6, 9, C, and F are divisible
by 3. Digits 1, 4, 7, A and D have remainders of 1. Digits 2, 5, 8,
B and E have remainders of 2. In all bases, the possible end results
to evaluate are the same (i.e. nothing, 1, 2, 12, 112, 122, or 1122).
Doing that same bar trick in hexadecimal is a sure-fire way to get
some geek cred!
William Elliot
> It's possible to determine whether a number is divisible by three
> without doing any addition, subtraction, multiplication or division.
> Well, sort of- you do have to do some counting which is effectively
> "adding 1." But it sounds less impressive that way.
>
> Here's how:
>
Here's how in one scan.
Start with zero. Skip each digit that's a 0, 3, 6 or 9,
add one for each digit that's a 1, 4 or 7 and substract
one for each digit that's a 2, 5 or 8.
The number is divisible by three iff the result is divisible by three.
The Qurqirish Dragon
wrote:
Actually, it will only work if the base is one more than a multiple of
3 (such as 10, or 16). If you are in another base, say binary, this
will not work, as the remainders when dividing by 3 are then dependent
on the position as well as the digit. For example, in binary, a "1"
has a remainder of 1 in the positions corresponding to even powers of
2, while it has a value of "2" in positions for odd powers of 2.
The reason for this is the same as why the traditional method works
for 3 and 9 in decimal: a 1 in any position is congruent to one more
than a multiple of any factor of (the base - 1).
me13013
> It's possible to determine whether a number is divisible by three
> without doing any addition, subtraction, multiplication or division.
That sounds like a pretty good challenge. What operations should be
allow? How about pattern matching, erasure and sorting?
A) Erase any 0, 3, 6, or 9
B) Sort the digits (low-to-high)
C) Erase any 111,222,444,555,777,888
D) Erase any 12,15,18,45,48,78
E) Repeat steps C and D as long as either can be applied
F) If there are no digits left, the original was a multiple of 3
G) Otherwise, the original was not a multiple of 3
This is NOT completely successful. Where did I blunder?
Bob H
Tim Little
> It's possible to determine whether a number is divisible by three
> without doing any addition, subtraction, multiplication or division.
> Well, sort of- you do have to do some counting which is effectively
> "adding 1." But it sounds less impressive that way.
Any mathematical operation can be done without doing any addition,
subtraction, multiplication or division. You don't even need to do
counting!
http://en.wikipedia.org/wiki/Turing_machine
Of course sometimes the procedures you would need to go through to
avoid counting are rather more involved than if you can assume the
ability to count.
> Step 1: Scan through the number from left to right (or right to left,
> it doesn't matter). Every time you encounter the digits 1, 4 or 7,
> count up from 1 to 3, starting over when you get to 3.
Or you could instead use the letters M, B and O, starting with M.
You ignore digits of 0, 3, 6, and 9. For digits of 2, 5, or 8 you
follow the appropriate transition from B->O->M->B. For digits of 1,
4, or 7 you go in the reverse direction. If the final result is "M"
then the number is a (M)ultiple of three, otherwise it is just (O)over
or (B)elow a multiple of three.
Now you don't even have to count! As an extra special bonus, you can
show it to airport security officials, who will be so impressed when
you explain that you used a BOMB that they will take you aside to ask
all sorts of questions.
- Tim
g.r...@iit.cnr.it
Clearly in step D one should include also 24, 27, and 57.
We can also simplify things and avoid sorting:
Initialization:
0,3,6,9 => null, 4,7 => 1, 5,8 => 2
Repeat until applicable:
111, 222, 12, 21 => null
The number is a multiple of 3 iff the final string is null.
giovanni
--
http://anagram.it : anagrams, alphametics, arithmogriphs,...
me13013
> We can also simplify things and avoid sorting:
> Initialization:
> 0,3,6,9 => null, 4,7 => 1, 5,8 => 2
But you've added an operation, substitution. And since since the
original poster said we can't use addition, you can't add
operations. ;)
me13013
>
>
>
>
>
> > Someone claiming to be An Innocent Icelander wrote:
>
> > > It's possible to determine whether a number is divisible by three
> > > without doing any addition, subtraction, multiplication or division.
>
> > That sounds like a pretty good challenge. What operations should be
> > allow? How about pattern matching, erasure and sorting?
>
> > A) Erase any 0, 3, 6, or 9
> > B) Sort the digits (low-to-high)
> > C) Erase any 111,222,444,555,777,888
> > D) Erase any 12,15,18,45,48,78
> > E) Repeat steps C and D as long as either can be applied
> > F) If there are no digits left, the original was a multiple of 3
> > G) Otherwise, the original was not a multiple of 3
>
> > This is NOT completely successful. Where did I blunder?
>
I forgot to mention that including 24, 27, and 57 in step D is still
incomplete.
Bob H
An Innocent Icelander
Good observation - I woke up in a cold sweat this morning realizing
that I was wrong about the base! (And I hate to be wrong!)
An Innocent Icelander
Bob -
That's a good approach. If you rewrite 1,4,7 as 1 and 2,5,8 as 2
prior to sorting, it works just fine. That would make the solution:
A) Erase any 0, 3, 6 or 9
B) Substitute 1 for any 1, 4 or 7 and Substitute 2 for any 2, 5 or 8
C) Sort the digits
D) Erase any 111 or 222
E) If you are left with an empty string, 12 or 1122 the original was a
multiple of 3
F) Otherwise, the original was not a multiple of 3