10 ms·
Divisible by 7 (2016)
- gus_massa 5y agoIt 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.
- blacksqr 5y agoThe linked site is a wiki, so you can create your own page and write it yourself!
- JadeNB 5y agoBased 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 https://news.ycombinator.com/item?id=27222819) to write it yourself is even better!
- SavantIdiot 5y agoI'd call OP "daring" for using Tk in a Python/Rust/Go/JS world. Impressive and novel, but not that easy to remember.
- holistio 5y agoClever and all, but I still actually divide faster than using this mechanism.
- slver 5y agoYou 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...
- gpvos 5y agoI'm fairly sure holistio means doing a long division using pen and paper, or even off the top of their head.
- KMnO4 5y agoHere’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 https://youtu.be/BfNlzdFa_a4
- anthony_romeo 5y agoJohn 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-divisibility-by-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-any-prime/ https://www.johndcook.com/blog/2021/02/17/divisibility-by-an...
- shultays 5y ago> 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
- meiji163 5y agoHere'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.
- Andy_G11 5y agoIs this only for numbers where the number of digits is a multiple of 6?
- Robin_Message 5y agoLeft pad with zeros
- Traster 5y agoI'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...
- lurquer 5y agoI 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.
- jldugger 5y agoI mean, who isn't loading their Anki decks with random mental math party tricks?
- meiji163 5y agoIt's just the fact that 1, 10, 100, 1000, ... = 1, 3, 2, -1, -3, -2, ... (repeating) mod 7
- quercusa 5y agoConvert 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.
- petschge 5y agoWait: Can you always test for divisibility by $n$ in base $n+1$ like that?
- J-Kuhn 5y agoYes. 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$
- klyrs 5y agoThe trick for 11 generalizes for testing for divisibility by n+1 in base n, too
- ouid 5y agoyes, n^k-1 is always divisible by n-1.
- wolfi1 5y agofor divisibility rules I would recommend "What is Mathematics" by Courant/Robbins
- juancn 5y agoIt doesn't render right on Chrome, such a weird site.
- sigzero 5y agoWorks fine in Chrome for me.
- annoyingnoob 5y agoThere 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.
- a1369209993 5y agoWhat 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?
- ouid 5y agolong division defines such a process