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 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 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.)
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 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 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 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 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.
- 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...
> 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!
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
Similarly, since 10001 = 73 × 137, abcdabcd always is divisible by 73 and 137.Oh and if you are copy pasting into notebook, then x %7 == 0 probably is a reasonable substitute...
Sort of silly, but it passes the time.
But a python notebook could definitely beat me in a race.
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$
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...
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
Impressive and novel, but not that easy to remember.