[HN Gopher] Divisible by 7 (2016)
___________________________________________________________________
Divisible by 7 (2016)
Author : blacksqr
Score : 68 points
Date : 2021-05-20 15:31 UTC (7 hours ago)
(HTM) web link (wiki.tcl-lang.org)
(TXT) w3m dump (wiki.tcl-lang.org)
| quercusa wrote:
| 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.
| petschge wrote:
| Wait: Can you always test for divisibility by $n$ in base $n+1$
| like that?
| J-Kuhn wrote:
| 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$
| klyrs wrote:
| The trick for 11 generalizes for testing for divisibility by
| n+1 in base n, too
| SavantIdiot wrote:
| I'd call OP "daring" for using Tk in a Python/Rust/Go/JS world.
|
| Impressive and novel, but not that easy to remember.
| anthony_romeo wrote:
| 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...
| shultays wrote:
| > 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
| wolfi1 wrote:
| for divisibility rules I would recommend "What is Mathematics" by
| Courant/Robbins
| gus_massa wrote:
| 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.
| blacksqr wrote:
| The linked site is a wiki, so you can create your own page and
| write it yourself!
| JadeNB wrote:
| 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!
| annoyingnoob wrote:
| 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.
| juancn wrote:
| It doesn't render right on Chrome, such a weird site.
| sigzero wrote:
| Works fine in Chrome for me.
| holistio wrote:
| Clever and all, but I still actually divide faster than using
| this mechanism.
| slver wrote:
| 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...
| KMnO4 wrote:
| 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 x _x_ x), 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
| gpvos wrote:
| I'm fairly sure holistio means doing a long division using
| pen and paper, or even off the top of their head.
| meiji163 wrote:
| 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.
| Andy_G11 wrote:
| Is this only for numbers where the number of digits is a
| multiple of 6?
| Robin_Message wrote:
| Left pad with zeros
| Traster wrote:
| 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...
| jldugger wrote:
| I mean, who _isn 't_ loading their Anki decks with random
| mental math party tricks?
| lurquer wrote:
| 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.
___________________________________________________________________
(page generated 2021-05-20 23:01 UTC)