
Divisibility by 7  - wglb
http://www.johndcook.com/blog/2010/10/27/divisibility-by-7/
======
eru
The rule in the article can be written as a regular expression.

And in general for every number m and base b you can build a finite automata
that gives you x mod m for numbers x expressed as a string of digits in base
b. The accepting automaton that accepts in case of x mod 7 = 0 for base 10 is
just a special case and gives you the regular expression mentioned above.

I am working on the regular expression for 7. In the meantime, look at this
regular expression for divisibility by 3
([http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-
Expr...](http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-
to-determine-if-a-base-10-number-is-divisible-by-3)). The author shows his
work.

~~~
waterhouse
If you're interested in deterministic finite automata, you might enjoy the
game Manufactoria:

<http://www.kongregate.com/games/PleasingFungus/manufactoria>

In the game, you deal with robots that come with a tape of binary digits (red
and blue dots), and you can build a maze using conveyer belts, branch points
(which read a dot from the front of the robot's tape), and things that write
dots to the end of the tape. You have tasks to fulfill; they start with easy
things like "Accept robots with no red dots", then "Accept robots with the
same number of red and blue dots", then "Reverse the input string" (that one
is unpleasantly hard), and so on.

In particular, there are some user-submitted levels, and one asks, "Accept if
the input number is congruent to 3 mod 7." (Input string is interpreted as a
binary number, read left-to-right normally, with blue = 1 and red = 0.) I have
a pretty nice solution to that one.

~~~
eru
Thanks. I tried it. The biggest challenge seems to be to make your layout
planar.

------
JeanPierre
I like the graph-way of dividing by 7. It's not intuitive and it's not easy to
remember, but at least it looks cool.

<http://imgur.com/wCE6z.png>

Start at 0. Read the number left to right, and for each digit D, go D black
edges. Whenever moving from digit to another, go a red edge.

~~~
radq
How does this work?

~~~
kwantam
It's a deterministic finite automaton (state machine) for dividing by seven.
In effect, it's the graph expansion of a regular expression.

[http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-
Expr...](http://blog.vkistudios.com/index.cfm/2008/12/30/Regular-Expression-
to-determine-if-a-base-10-number-is-divisible-by-3)

~~~
eru
By the way, at <http://slexy.org/view/s2QFWeNxZo> is a (horrible) regular
expression you can pop into "grep -xe" to test decimal numbers for
divisibility by 7. (Found with a Haskell programm I wrote via conversion from
the DFA.)

------
albertsun
432 = (7 * 60)+12

So 12 isn't divisible by 7.

8631 = (7 * 1000)+(7 * 200)+(7 * 30)+(7 * 3)

So 8631 is divisible by 7.

Just keep guessing numbers that get you close and lopping off chunks.

~~~
wwortiz
Otherwise known as long division :)

------
waterhouse
Here's what I generally do: Add or subtract multiples of 7 so that the final
digit will be 0, drop the final 0 (i.e. divide by 10), and repeat. To
illustrate:

37289 -> subtract 49 -> 37240 -> divide by 10 -> 3724 -> subtract 14 -> 3710
-> 371 -> subtract 21 -> 350 -> this is 35 * 10, and 35 is a multiple of 7.

The method described in the article is equivalent to my method, with the
stipulation that one always subtracts, and that there is a mechanical process
for picking the number to subtract (i.e. you multiply the number by 21).

37289 -> drop 9 from the end and subtract 18, which is equivalent to
subtracting 189 and dividing by 10 -> 37289 - 189 / 10 -> 37100 / 10 -> 3710
-> drop 0 from end and subtract 0 -> 371 -> drop 1 from end, subtract 2,
equivalent to subtracting 21 and dividing by 10 -> 371 - 21 / 10 -> 350 / 10
-> 35.

Advantages of my method:

a) This works with divisibility by any number at all (except for the factors
of 2 and 5, which can be dealt with easily). For example, divisibility by 13:

594875 -> subtract 65 -> 594810 -> divide by 10 -> 59481 -> add 39 -> 59520 ->
5952 -> subtract 52 -> 5900 -> 59 -> not multiple of 13.

b) You don't need to remember any magic number to do it--in this case, you
take the last digit, multiply it by the magic number -2, and add it to the
remainder of the number. (For divisibility by a general m (coprime to 10), a
magic number is any x such that x * 10 ≡ 1 (mod m). We see that _adding_ 5
times the last digit would also work for divisibility by 7.)

c) It is quite elementary. It's based on the facts that 1) adding a multiple
of 7 (or whatever your number is) won't change the divisibility, and 2)
dividing by 10 won't change the divisibility.

~~~
anigbrowl
It seems like you're doing it backwards?

37289 - 35000 = 2289 - 2100 = 189 - 140 = 49 / 7 = 0. It's just quick and
dirty long division, but easy to do quickly. I'm perplexed about what
advantage you see in starting at the small end?

~~~
waterhouse
I think you're asking why I think my method is better than the long division
you mention. I've used that method too, in the past. Hmm... On paper, they
seem pretty similar, but I think it is easier to answer the question "What
multiple of 7 can we add or subtract from the final digit n to get 0?" (a
memory lookup if you know single-digit multiplication and pay attention to
final digits) than "What's the biggest multiple of 7 we can subtract from the
leading digits mn?" (requires a couple of tries and comparisons).

If the first two digits happen to be "21" or "42", etc., a multiple of 7 by
themselves, then I will probably notice and subtract that out. But that's
fairly rare (1/7 assuming uniform distribution).

Overall, I find working from the small end more rewarding. Note that I _never_
have to add or subtract anything larger than 7 x 5, and, 7/10 of the time, I
don't have to add/subtract anything that isn't 7, 14, or 21. (I sometimes
choose to add/subtract larger numbers to avoid carrying a hundreds digit.)

And note that I do this with 13 and 17 and so on as well. Then long division
becomes even harder, whereas it's no harder to determine which multiple to
add/subtract (as you just need to look at the last digits; 13 and 23 are like
3, and 17 is like 7), and maybe just a bit harder to calculate this multiple
(e.g. last digit = 5 -> add 23 x 5 = 115; last digit = 9 -> subtract 23 x 3 =
69).

~~~
anigbrowl
I guess it depends on how each person's brain works. Long division seems to
just unzip itself without any real effort on my part.

------
Towle_
Also interesting is division by 7 resulting in a decimal.

1/7= .142857 repeating

2/7= .285714 rep

3/7= .428571 rep

4/7= .571428 rep

5/7= .714285 rep

6/7= .857142 rep

It's the same string of six digits, the only difference is which digit you
start at.

~~~
mmphosis
<http://www.markorodin.com/content/view/7/26/>

~~~
waterhouse
My reaction to the above link is "lolwut". The page talks about the fact that
the digital sums ("horizontal addition") of the powers of 2 form a repeating
sequence (1,2,4,8,7,5), and proceeds to call this "the MATHEMATICAL
FINGERPRINT OF GOD".

I can sympathize with people who look at the whole beautiful structure of
mathematics and see the touch of God, but the premise of that page seems to be
that this particular phenomenon--by itself--is huge and revolutionary and
supernatural. In fact, a student of modular arithmetic would see it as fairly
trivial. Two observations suffice to explain it:

1\. The digital sum of a decimal integer is just that integer mod 9. (This
gives us, as a special case, the divisibility rule for 9: N is divisible by 9
iff its digits add to a multiple of 9.) To illustrate with five digits, the
number N = abcde (base 10) is equal to:

    
    
      N = a * 10^4 + b * 10^3 + c * 10^2 + d * 10^1 + e
    

and since 10 ≡ 1 (mod 9), this reduces to

    
    
      N ≡ a * 1^4 + b * 1^3 + c * 1^2 + d * 1^1 + e (mod 9)
        ≡ a + b + c + d + e (mod 9).
    

If a+b+c+d+e < 10, then clearly that is the digital sum, and it's also N mod
9. If a+b+c+d+e ≥ 10, then we take the digital sum of _that_ , which will
again be the same as taking it mod 9. For a quick concrete example, the number
758 -> 7+5+8 = 20 -> 2+0 = 2, and 758 = 2 + 9 * 84, so it is 2 mod 9. Or we
could say that 758 = 7 * 100 + 5 * 10 + 8 = 7 * 1 + 5 * 1 + 8 = 7+5+8, which
is clearly the same number we got while taking the digital sum.

2\. The powers of 2 mod 9 are periodic. (In general, the powers of N mod M are
periodic, for any integers N and M.) Specifically, they are: 1, 2, 4, 8, 16 ≡
7 (mod 9), 14 ≡ 5 (mod 9), 10 ≡ 1 (mod 9), and we are back at 1. This is
exactly the "1,2,4,8,7,5" sequence that page talks about.

So, the above page talks about an elementary result of modular arithmetic as
though it, by itself, were some logic-defying mystery. Seems pretty dishonest
to me. Maybe it's a joke site. I saw a donation link, so maybe these guys are
successful trolls.

I'm a bit curious as to the motives of the parent commenter. You seem to be a
long-time member of HN (account is more than 2 years old). Was it a joke, or
did you suspect something fishy but didn't know what it was and posted it here
hoping someone would explain it for you, or did you actually take the author
at his word, or what?

------
ahn
You can generate rules like these for arbitrary integers/primes(much easier
than trying to remember them in my opinion). Take 41.

Example: 1476 is divisible by 41? 147 - 4 * 6 = 123. 12 - 4 * 3 = 0. Yes.

Example: 3321 is divisible by 41? 332 - 4 * 1 = 328. 32 - 4 * 8 = 0. Yes

What's the rule? Take the last digit off, multiply by 4 and subtract.

How to find the rules is left as an exercise.

------
8ig8
I usually just use a calculator.

Sorry, that's gonna sound rude, but the comments got me thinking.

In all seriousness, are we ever that far from a calculator? I'm sure just
about every cell phone has one built in. I understand the importance of a
fundamental understanding of mathematics, but at some point do we shift the
approach?

Novelty vs. practicality.

~~~
astine
Even sitting at a computer, if I can do a calculation in my head, it's usually
faster than attempting to do it with a calculator and it usually allows me to
keep the mental flow of whatever it is that I'm doing at the moment.

~~~
8ig8
Agreed. I placed my comment after reading waterhouse's comment
(<http://news.ycombinator.com/item?id=1852464>) which on first read seemed
like a lot of effort.

------
aufreak3
(warning: funny one)

Express the number in base 7. If the last digit is 0, then the number is
divisible by 7. I win!

~~~
aufreak3
More seriously, if you consider that the series 10^0, 10^1, 10^2, 10^3, etc.
in modulo 7 runs as 1, 3, 2, -1, -3, -2, (loop with period 6), the remainder
upon dividing a decimal number FEDCBA by 7 = the remainder on dividing (A-D) +
3(B-E) + 2(C-F) by 7.

Ex: 23456 mod 7 = 3+9+8 mod 7 = 6

------
brianbreslin
Clever but most people won't remember these tricks. I for one would appreciate
a refresher on the other divisibility rules/tricks.

~~~
spicyj
I do math contests competitively, so I remember these things. Here are some
rules:

Divisibility by 2: Last digit is divisible by 2 (0, 2, 4, 6, or 8).

Divisibility by 3: Sum of digits is divisible by 3. (You can repeatedly sum
the digits until the sum is small enough to manage easily.)

Divisibility by 4: Last two digits are divisible by 4 (00, 04, 08, 12, ...).
If you don't know your multiples of four, you can divide the two digits by 2
and then see if it's even.

Divisibility by 5: Last digit is divisible by 5 (0 or 5).

Divisibility by 6: Divisible by 2 and by 3. (Works similarly for all composite
numbers, of course. Like 10, 14, 15, etc. Make sure the factors you're
checking are relatively prime (share no common factors), or it won't work. For
example, divisibility by 2 and 6 does _not_ imply divisibility by 12.)

Divisibility by 8: Last three digits are divisible by 8 (000, 008, 016, ...).
Probably faster to divide the last three by 2 at least once then check
divisibility by 4.

Divisibility by 9: Sum of digits is divisible by 9. (You can repeatedly sum
the digits until the sum is small enough to manage easily.)

Divisibility by 11: Alternating sum of digits is divisible by 11. (Almost
always turns out to be -11, 0, or 11. Example: 66374. 6 - 6 + 3 - 7 + 4 = 0,
so 66374 is divisible by 11.)

~~~
omaranto
Seeing this list of silly things one might find useful in high school math
contests made me nostalgic for those days...

~~~
xyzzyz
Silly? Some people do math for a living.

~~~
omaranto
I do math for a living. Needing to now whether a small integer is divisible by
7 rarely comes up. And when it dos we tend to let dumb machines handle the
easy stuff, leaving humans free to think.

------
shabda
You may want to post your jobs at

<http://www.hackernewsjobs.com/>

(Since last time people requested that I not cross post things from here, I am
not going to do that, but you can email me (in profile) to do so, or post
directly.)

------
fxj
slightly different alorithm:

<http://www.cut-the-knot.org/blue/div7-11-13.shtml>

------
ChristianMarks
-n = -10a-b ~ -3a -b ~ -6a -2b ~ a - 2b mod 7

