News for hackers. Stuff that matters.
Re:Divisible by 7 (2016) by anthony_romeo on Thursday May 20, 2021 @01:25PM (#27224142)
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...

Re:Divisible by 7 (2016) by shultays on Thursday May 20, 2021 @02:24PM (#27225072)
> 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
Re:Divisible by 7 (2016) by gus_massa on Thursday May 20, 2021 @11:44AM (#27222653)
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.
Re:Divisible by 7 (2016) by JadeNB on Thursday May 20, 2021 @12:31PM (#27223336)
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!

Re:Divisible by 7 (2016) by blacksqr on Thursday May 20, 2021 @11:55AM (#27222819)
The linked site is a wiki, so you can create your own page and write it yourself!
Re:Divisible by 7 (2016) by meiji163 on Thursday May 20, 2021 @03:01PM (#27225587)
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.
Re:Divisible by 7 (2016) by Someone on Thursday May 20, 2021 @07:34PM (#27228783)
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.
Re:Divisible by 7 (2016) by Traster on Thursday May 20, 2021 @03:47PM (#27226173)
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...

Re:Divisible by 7 (2016) by lurquer on Thursday May 20, 2021 @04:30PM (#27226790)
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.

Re:Divisible by 7 (2016) by tashi on Thursday May 20, 2021 @07:44PM (#27228869)
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.

Re:Divisible by 7 (2016) by meiji163 on Thursday May 20, 2021 @07:26PM (#27228728)
It's just the fact that 1, 10, 100, 1000, ... = 1, 3, 2, -1, -3, -2, ... (repeating) mod 7
Re:Divisible by 7 (2016) by jldugger on Thursday May 20, 2021 @05:02PM (#27227208)
I mean, who isn't loading their Anki decks with random mental math party tricks?
Re:Divisible by 7 (2016) by Andy_G11 on Thursday May 20, 2021 @03:26PM (#27225869)
Is this only for numbers where the number of digits is a multiple of 6?
Re:Divisible by 7 (2016) by Robin_Message on Thursday May 20, 2021 @03:39PM (#27226079)
Left pad with zeros
Re:Divisible by 7 (2016) by annoyingnoob on Thursday May 20, 2021 @06:34PM (#27228288)
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.
Re:Divisible by 7 (2016) by quercusa on Thursday May 20, 2021 @03:03PM (#27225612)
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.
Re:Divisible by 7 (2016) by petschge on Thursday May 20, 2021 @03:39PM (#27226071)
Wait: Can you always test for divisibility by $n$ in base $n+1$ like that?
Re:Divisible by 7 (2016) by J-Kuhn on Thursday May 20, 2021 @03:44PM (#27226133)
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$

Re:Divisible by 7 (2016) by klyrs on Thursday May 20, 2021 @05:44PM (#27227752)
The trick for 11 generalizes for testing for divisibility by n+1 in base n, too
Re:Divisible by 7 (2016) by ouid on Thursday May 20, 2021 @07:32PM (#27228768)
yes, n^k-1 is always divisible by n-1.
Re:Divisible by 7 (2016) by a1369209993 on Thursday May 20, 2021 @07:25PM (#27228720)
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?
Re:Divisible by 7 (2016) by ouid on Thursday May 20, 2021 @07:29PM (#27228746)
long division defines such a process
Re:Divisible by 7 (2016) by wolfi1 on Thursday May 20, 2021 @03:32PM (#27225966)
for divisibility rules I would recommend "What is Mathematics" by Courant/Robbins
Re:Divisible by 7 (2016) by holistio on Thursday May 20, 2021 @01:19PM (#27224050)
Clever and all, but I still actually divide faster than using this mechanism.
Re:Divisible by 7 (2016) by slver on Thursday May 20, 2021 @02:20PM (#27225017)
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...

Re:Divisible by 7 (2016) by gpvos on Thursday May 20, 2021 @02:37PM (#27225250)
I'm fairly sure holistio means doing a long division using pen and paper, or even off the top of their head.
Re:Divisible by 7 (2016) by KMnO4 on Thursday May 20, 2021 @02:44PM (#27225355)
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

Re:Divisible by 7 (2016) by juancn on Thursday May 20, 2021 @04:51PM (#27227054)
It doesn't render right on Chrome, such a weird site.
Re:Divisible by 7 (2016) by sigzero on Thursday May 20, 2021 @05:07PM (#27227267)
Works fine in Chrome for me.
Re:Divisible by 7 (2016) by SavantIdiot on Thursday May 20, 2021 @01:03PM (#27223828)
I'd call OP "daring" for using Tk in a Python/Rust/Go/JS world.

Impressive and novel, but not that easy to remember.