Divisible by 7 (2016) | Hacker News Reader

Divisible by 7 (2016)

wiki.tcl-lang.org

82 pointsblacksqr30 comments

John D. Cook (who has one of my favorite blogs on the web) recently had a few helpful posts about divisibility rules:

- Divisibility by 7, 11, 13: https://www.johndcook.com/blog/2020/11/10/test-for-divisibil...

- Divisibility by any prime using determinants: https://www.johndcook.com/blog/2021/02/17/divisibility-by-an...

> Divisibility by even primes and primes ending in 5 is left as an exercise for the reader. haha, took me a second i must admit

It would be nice to write another article that explains why it works. Add labels like 0, 1, 2, ..., 6 to the nodes and explain that black arrows are +1 and white arrows are x3.

The linked site is a wiki, so you can create your own page and write it yourself!

Based on

> How does it work? Here's a hint: the white arrows correspond to 10x mod 7.

(which of course is the same as 3x mod 7), it seems that the author intentionally wants to leave it as a slight puzzle. But blacksqr's suggestion (https://news.ycombinator.com/item?id=27222819) to write it yourself is even better!

Here's a way I do it in my head: For every block of six digits "fedcba" calculate (a-d)+3(b-e)+2(c-f). The number is divisible by 7 if the sum is divisible by 7. Fun thing is you know any number with digits "abcabc" is divisible by 7.

Is this only for numbers where the number of digits is a multiple of 6?

Left pad with zeros

I'm kind of more intersted in why you know this. There's lots of weird esoteric stuff that I know that I need as part of my job, but what are you doing that requires you to know this that isn't "copy paste this number into a python notebook"?

Oh and if you are copy pasting into notebook, then x %7 == 0 probably is a reasonable substitute...

I can’t speak for the poster, but I learned that trick (and many others) to play a game while stuck in traffic. Namely, derive the prime factorization of the license plate number in front of you before you lose sight of it. (Usually a 5 digit number in my area.)

Sort of silly, but it passes the time.

I mean, who isn't loading their Anki decks with random mental math party tricks?

It's just the fact that 1, 10, 100, 1000, ... = 1, 3, 2, -1, -3, -2, ... (repeating) mod 7

I test numbers for divisibility by 7 in my head almost every time I do a daily KenKen puzzle. There's usually a four or five-digit number in there whose factors I don't know off the top of my head, so I'll give it a quick check for sevens just to get my bearings.

But a python notebook could definitely beat me in a race.

We have

  abcabc = 1001 × abc = 7 × 11 × 13 × abc

so abcabc also is divisible by 11 and 13.

That also means that, to check divisibility of abcdef by 7, 11, or 13, compute |def-abc| and check whether that is divisible by 7, 11, or 13 since

  abcdef = abcabc + (def - abc) = defdef + 1000 × (abc-def)

Similarly, since 10001 = 73 × 137, abcdabcd always is divisible by 73 and 137.

There was a time many years ago when Microsoft CD Keys were all divisible by 7. You could use any key that was divisible by 7. Need a key to unlock the software on that CD, no problem just make one up that divides by 7.

Convert a base-10 number to octal. If the octal digits are divisible by 7, it's divisible by 7. IOW, 7 is octal's 9.

Wait: Can you always test for divisibility by $n$ in base $n+1$ like that?

Yes.

A number in base $n$ is just $a*n^2+b*n^1+c$.

Because $n mod n-1 = 1$, you can replace every $n$ with $1$.

So $a*n^2+b*n^1+c mod n-1$ becomes $a+b+c mod n-1$

The trick for 11 generalizes for testing for divisibility by n+1 in base n, too

yes, n^k-1 is always divisible by n-1.

What I get out this is that "decimal numbers divisible by 7" is a regular language (can be recognized by a deterministic finite automaton). Is there a general procedure to construct such a graph for a arbitrary (base and) divisor?

long division defines such a process

for divisibility rules I would recommend "What is Mathematics" by Courant/Robbins

Clever and all, but I still actually divide faster than using this mechanism.

You divide faster thanks to your language interpreters and compilers implementing thousands of algorithms like this which convert between arithmetic operations so you can have that speed. For example sometimes when you divide by specific numbers in C it gets compiled to equivalent multiplication and addition.

Your comment reminds me of this other thread, where people were bragging they could implement curl in a few lines of Python code, by first including a CURL-like module...

I'm fairly sure holistio means doing a long division using pen and paper, or even off the top of their head.

Here’s a cool video that shows how compilers optimize exponentiation[1].

It seems like a really simple problem on the surface (x^3? Just do xxx), but lots of smart people have thought hard about the best way to do it for any arbitrary exponent.

For example, x^15 only needs 5 multiplication instructions.

[1]: https://youtu.be/BfNlzdFa_a4

It doesn't render right on Chrome, such a weird site.

Works fine in Chrome for me.

I'd call OP "daring" for using Tk in a Python/Rust/Go/JS world.

Impressive and novel, but not that easy to remember.

Reply on news.ycombinator.com