Just replace the regex for the prime with a prime sieve, and pick your integers from the results. My own terrible single threaded sieve written in basic Python checks the numbers up to 100,000 in 35 seconds on my own machine. It appears to be O(n^2), but I'm certain there are faster ways to do it.
@@LaughingOrange thoughts: - checking numbers individually for primality by testing prime factors up to sqrt(n) and saving previous primes for later tests might be faster; the sieve gives you a list of primes in O(n^2), this would give you the same list of primes in O(n*sqrt(n)). maybe. might be wrong on that asymptotic analysis. - it also might be slower because now you're doing integer division instead of repeated addition; the sieve is a very simple algorithm and computers can do simple things very very fast - you are, however, doing way way way better in terms of space; instead of linear space usage, you're now using n/log(n) for the list of primes below n.
@@simon-pierrelussier2775publish an online article and refer to that. Even better with an everything-site where .../.html contains divisibility tests for that number and if the page does not yet exist, it's generated once and stored for later.
My favourite divisibility test for 7 is removing multiples of 1001 (=7*11*13). For the number 2716, you can subtract 2002 and get 714, which is obviously divisible by 7. Works great to get big numbers small by subtracting 10010, 100100 and so on.
I don't usually comment on videos, but I had to share this story on this video. I went to grade school with a math whiz who worked out a divisibility test for seven, on his own, in 5th grade (I'm sure it was something along the lines of those in this video, but I'm equally sure he worked it out independently; I wish I could remember what it was). He was as proud as I ever saw him when he showed it to the teacher. The teacher's response was "that's neat, but it's kind of like doing cartwheels to get into your chair when you could just walk; why don't you just do the problems the way I showed you." It wasn't even me and it still hurts to think about.
Well it is a neat trick, but it's sort of an antiquated thing, like unless you have an eidetic memory it's not worth memorizing bc calculators are always immediately available, and finding if something is divisible isn't an especially common a problem in the first place.
And this is why kids end up hating math. Teachers don't let them actually do math, and get excited about it. When a kid does actually do some math on his own the response is "that's neat" at best. Then back to following some formula that someone else came up with a long time ago. I know people need to know what's already out there, but you've gotta encourage innovation at the same time
If I'm unable to sleep, then I think of a sufficiently large number, but not too large, to check if it's prime. I take an approximate square root in my head, and then I do the check of divisibility for each prime number up until the biggest one less than the original number's square root. Because of this, I had to come up with divisibility rules in my head, and I always used this "take away the last digit, multiply it by a correct number, then subtract or add it to the rest" method. This way, I checked that 8329 is indeed a prime number, thus, it's my favorite one! Coming up with the multipliers was a long mental process, though. I'm glad you made this video, Matt!
I would do the same thing while rollerblading. I determined that 1,023 was not prime that way. I would also determine multiples of large two- and three-digit numbers. It really helped pass the miles . . .
1023 shouldn't take long, but I also ignore a test of 2, 3, and 5 sometimes, which makes the realisation that 3 was a divisor all along really frustrating :D I'm glad I'm not the only one doing mental arithmetic to pass the time
Ha, what a bunch of nerds... anyways when I'm bored/passing time I try to approximate weird probabilities/distributions. Although it's often much harder to actually verify.
Not just me using that as a way of getting to sleep then! I look for ways of either getting rid of the first digit(s) or making the last digit(s) zero. So for 2716 adding 14 (a multiple of 7) gives me 2730 but I can just drop the zero and move on to 273 - add 7 and you get 28 and I'm done since I know my 7 times table. Different tricks work for different numbers but you can just knock out any 7 in this case for example or subtract 7 from any higher digit - so 9961 you can immediately reduce to 2261, then knock 21 off each end to get 14. For anything over around 5000 chances are I'll be asleep on the first night and have to continue next time.
The highest prime test to have been assigned is 23027 (The Taekiro tests). As of the video being released, 23029 and higher are all free real estate! (Coincidentally cut off is between twin primes)
@@ltloxa1159 my fav is divisibility by n-1 in base-n. In base 10 that would be div by 9. So in binary it can work as div by 3, 7, 15, 31, 63 etc, just by grouping digits into higher 2^N base systems.
I think I prefer my own divsibility by n method... 1. Write the number down. 2. Stare at it for ten seconds. 3. Get annoyed that I can't remember any of the divisibility rules I've written down. 4. Give up. 5. Cave in and get a calculator for the actual result. Works like a charm every time. 😂
"I called it the vsause method." We live in a bizarre world where, if Matt comes up with something that actually works, he can't call it the Parker method, because that would make people think there was something wrong with it!
I think fairly early on, it’s easier to use the divisibility rule called “long division”. The only multiplying you need to do is working out the N times table up to 9N, and then it works for all values of N the same way. It even tells you *how many* times your number is divisible by N! (That’s just an exclamation mark, not N factorial)
หลายเดือนก่อน +15
IMO if the divisibility test still needs O(n) effort, it needs to be really intuitive, otherwise you are memorising random magic and have to believe that it worked for barely any time gain.
My teacher taught me "Drop everything but the last two digits, then if either digit is 4 or higher, subtract 4 from that digit (repeat for 8 or 9). Then check your times table."
@@SkippiiKai Depends on how much of the times table you have memorized. No need to subtract if you know 68 is divisible by 4 off the top of your head, but most kids only learn up to 12 x 12 or so, and 4 x 17 is a bit off to the side.
@@siosilvaryes, but 60 is divisible and 8 is divisible therefore 68 is di isible by 4. Or, 68/2=34 and 34/2=17. When we can divide by 2 twice, we have divided by 4. Practically, I do not use divisible rules but the calculator. 0 decimals indicates divisibility.
The explanation for how all this works is so much more easy and beautiful! It all comes down to modulo classes. Take Michael's approach. Split any number into two parts so that the number equals 10a+b. If that is divisible by 7, then 3a+b is as well, which if multiplied with 3 is still divisible by 7: 9a+3b. Subtract that from 10a+b and you get a-2b which gives the same rest as a+5b. And that's his formula. Using those calculations you can get super nice divisibility checks. E.g. for 7: Take the first digit. Multiply with 3. Add the next digit. Multiply with 3, add the next digit... Until you added the last digit. E.g. 112: 1*3 = 3, +1 = 4, *3 = 12, +2 =14 which is divisible by 7, so 112 is as well.
Yes! I stopped the video before he did the proof, and worked it out myself. Matt's method was extremely simple to prove: 100a + b = (98 + 2)a + b = 98a +2a + b = 7*(14a) + 2a + b ≡ 2a + b (mod 7) I tried the same technique for the other two methods, but could not do it. I finally did something similar to what you did.
Using modular arithmetic, these divisibility rules are easy to prove. For instance in the method where you multiply the unit by 5 and add to the other digits, you first write the whole number as 10a + b. If this is divisible by 7, then this is 10a + b (mod 7) = 0. 10 (mod 7) = 3, so 3a + b (mod 7) = 0. Multiply by 5, and since 3*5 = 15 (mod 7) = 1, you get a + 5b (mod 7) = 0, which is the exact rule we want (5 times unit digit, plus the other digits).
I am a little surprise the 1001-trick wasn't mentioned. You capture three flies in one bang and it is fast for larger numbers since we don't do operations for every single digit, but instead just every third digit. Since 7•11•13=1001 you can actually check divisibility by both 7,11 and 13 in one nice swoop by utilizing this. Which is extra cool since they are three consecutive primes! Here is how you do it. Example 1: I wonder if 11250057 is divisible by either 7,11 or 13. 1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 11 250 057 2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here -11+250-57 or simply 250-68 = 182. 3. Now all you have to do is to check whether 182 is divisible by either 7,11 or 13. We notice 182=7•26=7•2•13. 4. Cool 182 is divisible by both 7 and 13. Hence 11250057 is divisible by both 7 and 13 but not by 11. Another example 2424737531233. 1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 2 424 737 531 233 2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here 2-424+737-531+233 = (2+737+233)-(424+531)=972-955=17 3. Now all you have to do is to check whether 17 is divisible by either 7,11 or 13. We notice 17 is prime. 4. Cool 2424737531233 is neither divisible by 7, 11 nor 13.
I got three minutes into re-watching your video on the Egyptian papyrus on fractions, and suddenly you show up in a notification telling me you have MORE to tell me on division? THIS CANNOT BE A COINCIDENCE 🤯
Interesting fact: some of these tests are only *"divisibility-preserving"* (iff the number had a remainder other than 0, the number that comes out will have a remainder other than 0, but potentially a different one), while others are *"remainder-preserving"* (the remainder is unchanged by the operation). The tests that remove the singles digit (and do an implicit multiplication by 10) are only *divisibility-preserving* (with the exception of divisibility tests for 11, 9, 101, 99, 1001, 999, ... and their thirds). The tests that remove chunks from the large end (for example the divisibility tests for 7 based on 98 and 1001) are *remainder-preserving.* You could probably turn a divisibility-preserving operation into a remainder-preserving one if you counted how many times you applied it, took the final remainder and multiplied it by "a certain number" that many times. Where I think (but am not 100% sure) that the "certain number" is 10 mod N for divisibility tests by N. The problem is that for divisibility tests for numbers between 10 and 20 the "certain number" is negative, which will flip-flop the sign of the remainder. And for divisibility tests above 20, you'd multiply the remainder by 10 as many times as you divide the original number by 10.
17:46 I do appreciate that Matt picked an example where no matter what number Nicole picked or how many mistakes Matt made, he would still be right 99.9% of the time. Truly the power of backstage maths.
My personal favorite divisibility test for 7 is the test in binary, where you split it up into chunks of three bits and add them up. For example: 100101001001111011 = 152187 splits into 100|101|001|001|111|011 4 5 1 1 7 3 which, added up gets 100 + 101 + 001 + 001 + 111 + 011 = 10101 = 21 (base 10) then 101 + 10 = 111 = 7 The reason I like it so much (besides the fact that it's easy for computers) is that it's functionally identical to the divisibility by 3 or 9 rule, but for binary. I was thinking about the 3 or 9 rule that we learn in elementary school when cutting cucumbers in my kitchen and was wondering about how it extended past those two numbers. I realized that my teachers never told us about how it also applies to 99, thus also 33 and 11 so long as you group the digits into pairs before adding them up. Likewise for 999, 333, 111, and so on for any 10^n-1 and its factors. It was about this point that I cut my finger and had to leave my cucumbers to get a bandaid.
For large decimal numbers, you can reduce them down to at most 6 digits by taking 6 digit chunks and summing them (padding one end of the original number with 0s to get enough digits if needed), which preserves divisibility by 7. It also preserves divisibility by all the other factors of 999999, though among other prime power factors, only 13 needs the full 6 digits - 27 and 37 each work with 3 digit chunks and 11 only needs 2.
@@KevinMcFlying They included a zero at the left side to be able to split the number up into chunks of three without changing the value. 10101 = 010101 Splits into 010 | 101 Add them up 010 +
Watching this made me realize that breaking down why the divibility rules work is eye opening. It's such a cool feeling when you can understand why the math is happening the way it is rather than just following a rule. I feel like that was part of the goal for common core, just implemented poorly. I feel lucky to have had amazing math teachers growing up that wanted us students to understand math rather than just memorizing rules. At the time as a child I couldnt understand, but now looking back at what I learned, I can see the beauty underneath
Fun fact, in seximal (base six), the units-based test will work for any prime greater than 3 out of the box, since all primes greater than 3 end in either 1 or 5 in base six (the 5 version works the same as the 9 version in decimal). Powers of primes other than 2 and 3 (six's factors) will also end in 1 or 5
@@Moldovallan1618 Other way around; senary is the official name, sometimes it gets called heximal, but jan Misali intentionally uses seximal because they dislike senary as a word and think heximal is too easily confused for hexadecimal.
For small divisors, just find a nearby number known to be divisible, then check if the difference is divisible. It often makes the problem something you can do in your head.
This depends on what you mean by “small.” Using the example of 2716 from the video, I think it’s pretty easy to take 2800 (7*4*100) and see that the difference is 84 (7*12). Which additionally tells you that the dividend is 388 (4*100 - 12). Depending on how quickly your brain can make those connections, it might be faster than long division.
Funnily enough I find basically just doing the division so much faster than almost any divisibility trick. Obviously there are exceptions for 2 or 3 or the really easy numbers but at any point where you have to do a calculation or add/subtract different parts of the number i just do it straight up 7889/7 -7000 889-700 189-140 49 is divisible by 7. If I slowed down I would see it’s 1127x7 but if I just want to know whether it’s divisible or not I can just skip the division part and do most of the method for short division in my head The video example: 2716 -2100 616 -560 56 is divisible by 7
I remember getting a homework problem as an undergrad to create divisibility tests for various numbers based on modular arithmetic. This leads to some different tests than the ones in the video and is also neat imo. Could be a followup vid.
wow i feel proud i was looking at your thumbnail and was like 'hey that reminds me of an old ding video' and i was instantly validated :D thank you mr count binface counting agent parker
The "you can just subtract out batches" approach has led me to a divisibility test that I think I like in practice: Subtract out 5*10^n for the largest n that makes that less than the number you're testing, then add 10^(n-1). So for 2716, you'd remove 5 500s and add 5 10s; 2716-> 216 -> 266. You've removed 490 5 times, which is a multiple of 7. Then remove 50 5 times and add 5 1s; 266 -> 16 -> 21. You've removed 49 5 times. That's a multiple of 7 so we're done. It's nice because you are just working with multiples of 10, which I find easier to manipulate in my head, even if it is based on the same basic math as the Veritasium approach.
*does a convoluted test for multiples of 1009 when no one asked except him and calculators exist* 19:46 "MATHS!" "Now that's applied useful mathematics."
For any integer, n, divide the number by 17 (use long division). If the remainder is zero, then the number is divisible by 17. I call this "Pat's Rule."
Back when the dozenal video came out on Numberphile (at this point, almost a dozen years ago...), I started working out divisibility rules for base 12. For most of the single digit numbers, checking is fairly straightforward. For 2, 3, 4, and 6, it's just a case of looking at the last digit. 144 is divisible by 8, so that just requires the last 2 digits. 11 (el) can be found by summing the digits (for the same reason that 3 and 9 work in base 10). That left 5, 10 (dec), and 7, which I found amusing because 5 and 10 are two of the easiest in base 10. Eventually, I found through trial and error that you could test divisibility by 5 by summing the ones digit, plus twice the 12s digit, plus 4 times the 144s digit, and so on - basically evaluating the number as if it were in base 2 instead of base 12. If the result was divisible by 5, so was the original! The same method works for 10 as well, and a similar method worked for 7 (except you multiply by increasing powers of 5). After working through this, I found a general rule that works in any base: To check if a (base b) is divisible by n (base b), evaluate a as if it were written in base c, where c is the remainder of b/n. If the result is divisible by n, so is a.
@@ljfaag Tests for 2^n + 1 or 2^n - 1 are fairly straightforward in binary. For example, the test for 7 is to split the number into 3-bit chunks (because 2^3 = 8) and add those together. If the result is a multiple of 7, so was the original number. Conversely, for, say 17 (2^4 + 1), break the number into 4-bit chunks, then alternate adding and subtracting those chunks. If the result is divisible by 17, so was the original number. I have no idea if any of these are any more efficient than just calculating the modulus and seeing if it's zero, though maybe they could be faster on custom hardware
That made me think and I'm pretty 2520 is the smallest base in which you can check the divisibility of the numbers 1-9 by looking at the last number, not that it would matter much in base 2520 anyways. Also, this might be the first time someone recognizes you in random TH-cam comments, but I love your maze algorithm videos :)
this video is exactly the kind of math i'm super interested in. I loved D!NG and Numberphile and remember watching both of those videos about divisibility rules, i'm stoked to get a comprehensive guide to one approach of solving the problem!
I just only just now realized the similarity of "Matthew" and "Maths" because of the intro. So it's really, "Stand -up Math-ew"? I must be the last person to notice this.
Much better title! This one tells me that the video is about generalizing divisibility rules, whereas I didn't really know what I would be getting before.
I have the test for 8513. Take the 10,000s, multiply by 1487, and add to the rest. Multiply the units by 2554 and add. Thanks for all the great videos Matt.
So what I’m going to take away from this is, when I hear a big number, I can just sagely remark in passing “divisible by one” and nod as if this was a singularly unique talent that I have cultivated.
@6:40 This was the biggest experience of simultaneous "what that can't possibly be right that's magic" and "that is very simply and obviously true" I've had in a long while.
(making this comment right after the first 3 methods have been introduced) I find it's easiest to check divisibility by 7 by just diving by 7, but "backwards" from normal. Since the last digit of the multiples of 7 are unique from 0-9, just subtract the corresponding multiple that matches the last digit (if the last digit is zero, ignore it and compare with the rightmost non-zero digit), and repeat until the answer becomes clear. For the example of 2716: 2716-56=2660 2660-560=2100=7x300 This gives the result of the division from the 1's place up, so 7x8+7x80+7x300=7x388.
Divisibility Rules! What does Divisibility rule? Was Divisibility elected? "Well, I didn't vote for you." "Help, I'm being repressed!" That would have been funny a few years ago; now I just made myself sad again.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the covid hump with Biden actually doing anything of value.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the pandemic hump with Biden actually doing anything of value.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the covid hump with the current administration actually doing anything of value.
The week after i first watched the james grime video, i also knocked together some terrible python code to find divisibility rules for every number up to 10000. To make the rules for composites i had it combine and simplify the divisibility rules for its prime factors into one function. Love the video as always, good stuff
Woo something is named after me! 17027 is a prime and has the 'Parrik' tests: Take the 100,000,000s, multiply by 429, and add to the rest. Multiply the units by 5108 and subtract.
I really hoped Matt Parker would have shown how to construct these divisibility rules, so I came up with my own method. Find prime P and natural number N such that P*N = a *10^b + c P=313 N=16 a=5 b=3 c=8 313*16=5 *10^3 + 8 313*16=5008 Now we can test for 223795=313*13*11*5 Split 223795 after the b:th number, 3rd in this case. 223795/10^3=223.795 decimal point separates the components A, B Multiply the A=223 by c and subtract from the rest B=795 multiplied by a B*a-A*c= 795*5-223*8=2191 Repeat if needed till you get to small enough number. 2191/10^3=2.191 191*5-2*8=939 which is easy to see that's 3*313 Some bad combinations don't reduce the starting number but they are at least always divisible by P. Those cases could be called Parker divisibility rules.
Another way to prove Michael's is that, at any step, the difference between applying each method is 7×units, so if one is a multiple, then so is the other
I like Matt's divisibility-by-7 rule the best as it preserves the remainder. So that, for example, if the final number is one off from being divisible by 7, then the original number is also one off from being divisible by 7.
This applies for every odd number (except multiples of five): Find the first multiple of your factor with a one in the ones' digit. Take that multiple and drop the ones' digit. multiply the new number by the ones' digit of the number you're checking. This works because multiplying the ones digit will cancel out, which is why you drop the last digits.
I really like this explanation for the divisibility rules for 7 over using modular arithmetic. The modular arithmetic works but this is super intuitive!
18:35 „..68, gotta multiply that by 28.. Ach.. great“ *cut to some multiplication. I don’t know why i think that’s so funny but I can’t stop watching it xD
Great, now I got my own rule. I hope you all use it regularly as it is a very handy one: 6841 is a prime and has the 'DarkElder' tests: Take the 1,000,000s, multiply by 1214, and add to the rest. Multiply the units by 684 and subtract. Sounds pretty straight forward indeed. Thanks, Matt! 😆
I think this was one of the best maths videos on TH-cam, thoroughly enjoyed it! I've always wondered - of course, not so much as to look it up - how those divisiblity rules are created. Now I wonder, are there any other generalizable methods besides summing/subtracting to a power of 10 🤔
A general rule I like to remember is that if the divisor's rightmost digit is co-prime to the base (1, 3, 7, and 9 in base 10), then each multiple from 0-9 of that divisor has a unique digit in the 1's place; this means that you can do some pretty simple "backwards" long division. Let's say we want to see if 63893 is divisible by 7 (I have no clue if it is yet): 63893-63=63830 63830-630=63200 63200-4200=59000 (which is clearly not divisible by 7) May not be the easiest mental math method, but can reasonably be done quickly with pencil and paper; just scratch out the multiples of the divisor from 1-9 to the side and subtract whichever one matches the current rightmost non-zero digit.
Isn’t Collatz conjecture just shorthand for the divisibility tests of every prime number? See 16:17. So applying it will always reduce the number over time, factors out all prime factors except 1, and loops at the end because it’s a divisibility test. The fundamental theorem of arithmetic states a unique factorization exists for every number. This ensures there are divisibility tests to check for all of them.
this is a nice way of explaining it without involving explicit modular arithmetics! but i also like working in modular arithmetics since it allows you to take plenty of shortcuts for these. for example, we can view the +5/-2 rule (which are trivially equivalent in modular arithmetics) as 1/10 (=1/3) in the modulo 7 group. so essentially, we just divide the whole number by 10, just like matt said in this video.
On the topic of fast prime tests, you should look into (or do a video on) the Miller-Rabin primality test. It's technically probabilistic for each individual witness test, but it is **extremely** fast (as in like basically instant for all 64-bit numbers), and it's fairly easy to implement and understand too. And heck, you _can_ make it be robust and polynomial time if you assume the generalized Reimann hypothesis or use the hand-selected witnesses for your test range.
As of writing this, I have the video pause at 5:11, the instant after you finished showing all 3 methods. I think I figured out the trick with the Michael version. In the Michael version, what you are actually calculating is "how many times do I have to add 49 to this in order to get a 0 and the ones place, which I can then remove". (49·6)+6 = 50·6, and in fact (49·x)+x = 50·x. The James version is the same thing, but in reverse. Since the only thing that matters is the modulo, the remainder, going in reverse doesn't matter. You get the same result although you might have an occasional negative value since you are subtracting. From this I think I can infer how you would go about creating more of these rules. Now the question I have is whether these additional rules, and the pattern of creating them, actually make the computation of divisibility any faster, in terms of computational complexity. Does this discovery do anything that weakens RSA cryptography?
In decimal, I find a multiple of the divisor where the last digit matches the one in the dividend. Then I subtract and divide by 10 as many times as necessary. So for 2716 2716-56 = 2660 ==> 266 266-56 = 210 ==> 21 21-21 = 0 ✓ It's "easier" in binary! I'll comment under this one for those interested.
In binary, I divide both by 2 until one or both is odd. If the divisor is still even, it is not divisible. Then loop until the dividend is smaller than the divisor at any step: * Divide the dividend by 2 until it is odd * Subtract the divisor If you are left with 0, it is divisible. This "binary" way doesn't require you to find multiples, so for 2716, since 7 is odd, we can skip the first part: 2716 ==> 1358 ==> 679 679-7 = 672 ==> 336 ==> ... ==> 21 21-7 ==> 14 ==> 7 7-7 = 0 ✓
I laughed when I saw you adding from right to left. I am terrible at math, but when I was a chemist in a lab, my boss showed me how to add from left to right. It’s faster and more accurate, and you can do it in your head without any “carry the ones”.
Matt's "but I didn't stop there", reminds me of a scene from a British sitcom called My Hero, where a doctor says "Apparently one dose is enough to bring a giraffe to its knees.... so I put in 4".
I was once in a unique situation: at a competition where I knew I had ten minutes to answer a question about arithmetic mod 7. So before I started, I wrote down the multiples of 3 mod 7 for digits 0-9 so that I could start with the first digit and multiply by 3 and add the next digit all while taking mod 7, effectively evaluating the base-10 expansion of the number (10 mod 7 = 3). The interesting thing though is that this is generalizable-by simply starting with the first digit and continuously multiplying by 10 and adding the next digit all while taking the modulo of the number for which you want to test divisibility, you can compute any number modulo any other number without having to divide large numbers and test for divisibility by seeing if the result is 0 or not. It wouldn't be too far or a stretch to call this "the universal divisibility test".
5:10 matt's is the most intuitive to me, since it's just adding all the remainders of the hundreds (100 = 14*7 + 2, so 2 for every hundred) to everything below 100, which is a lot like the well known rule for divisibility by 3 the "michael" and "james" methods i have not yet figured out, but i can tell they have to be equivalent because 7 - 2 = 5, so the amount added always will differ by a factor of 7 between them so i just have to figure out why 10a + b is divisible by 7 if a + 5b is divisible by 7 (assuming a & b are integers, of course) *edit:* got it, if we take 5*(10a + b) = 50a + 5b, the remainders for all the 50s in 50a will just be a, because 50 = 7*7 + 1 so we're checking the divisibility of x through the divisibility of 5x and skipping a step, and since 5 and 7 are coprime this doesn't alter the divisibility by 7 at all meanwhile we could take the same tack with the "james" method, because -20 = -3*7 + 1, and 2 is still coprime with 7, so -2x = -20a + -2b (equivalent to a + -2b in mod-7) will be divisible by 7 if x is divisible by 7
0:23 Didn't see that video, but was told a rule for 7 by my grandfather, which is the one all of those people say. I had to be told by my grandfather, because they always told me there wasn't one (and it seemingly there's more than one), but they also kept reducing the divisibility tests to teach to schoolchildren every few years (I believe at least some of my younger siblings had textbooks that said that there was no test for multiples of 11).
really thought you would talk about the division graphs that james mentioned on an even more recent Numberphile video! they are very visual, fitting your video style very well
I've never seen the title of a video change in real time before: "I cracked the divisibility code." --> "New Divisibility Rule (30,000 of them)" Literally changed to the second title as Matt said '30,000' and I thought it was a new feature
I love divisibility rules, and I have known the divisibility rule for 7 for quite a while, the one that James used of subtracting two times the units digit from the rest of the number. For some reason it felt like to me as if it's some bizarre number theory result or something, and I didn't look it up as I wanted to maybe prove it myself. Didn't get to doing that, mainly because I was demotivated, and then I see this video, where Matt very casually says why it works and it's so simple it kind of makes me want to cry.
I like to imagine Terrible Python is a version of Python, and Matt is very good at programming it.
It's slightly more efficient than Monty Python.
so, Parker Python?
Python is already terrible, though
@@DanielHarveyDyer A nice bit of recursion there, seeing as Python is also named for Monty Python. Sadly, an infinite loop.
@@WildMatsu import bait
Someone's about to make this code a 10000000000% more efficient
Just replace the regex for the prime with a prime sieve, and pick your integers from the results. My own terrible single threaded sieve written in basic Python checks the numbers up to 100,000 in 35 seconds on my own machine. It appears to be O(n^2), but I'm certain there are faster ways to do it.
@@LaughingOrange thoughts:
- checking numbers individually for primality by testing prime factors up to sqrt(n) and saving previous primes for later tests might be faster; the sieve gives you a list of primes in O(n^2), this would give you the same list of primes in O(n*sqrt(n)). maybe. might be wrong on that asymptotic analysis.
- it also might be slower because now you're doing integer division instead of repeated addition; the sieve is a very simple algorithm and computers can do simple things very very fast
- you are, however, doing way way way better in terms of space; instead of linear space usage, you're now using n/log(n) for the list of primes below n.
Common Lisp already has a primep built in, so this would be a lot faster, and handle HUGE numbers.
@@royalninja2823sieve is O(n log(n)) or O(n / log(n))
@@LaughingOrange downloading a list of 50 mil primes and checking against that would definitely be a speedup :D
That Wikipedia article is about to get a lot bigger.
I’ll definitely add “my” test to the Wikipedia page!
@@Christian_MartelSurely WP:N
Well, if you can cite a reliable source !
@@johnjameson6751 Goddamnit, I'll have to have a paper published to be allowed to edit wikipedia...again!
@@simon-pierrelussier2775publish an online article and refer to that.
Even better with an everything-site where .../.html contains divisibility tests for that number and if the page does not yet exist, it's generated once and stored for later.
My favourite divisibility test for 7 is removing multiples of 1001 (=7*11*13). For the number 2716, you can subtract 2002 and get 714, which is obviously divisible by 7.
Works great to get big numbers small by subtracting 10010, 100100 and so on.
This is also my favourite, especially because it works for 11 and 13 at the same time :)
I wish I knew that one when I was actually participating in math competitions, and not just doing math at home, here I can just check online :/
You can phrase this test differently: Divide your number into blocks of three digits and then add and sub these blocks alternatingly.
That gives me linear algebra vibes
@@amigalemming can you give an example of using this test? Sounds cool but I can't make sense of it
As a programmer, my favourite divisibility test is:
return x%n == 0
!(x%n)
For powers of 2 i like x & ((1
Hi I'm javascript. -18%9 = -0 and -16%9 = -7. I'm so good at math.
@pwnchip, nice
@@eu7059 Only in languages with weak type systems, where you can freely cast integers to bools.
I don't usually comment on videos, but I had to share this story on this video. I went to grade school with a math whiz who worked out a divisibility test for seven, on his own, in 5th grade (I'm sure it was something along the lines of those in this video, but I'm equally sure he worked it out independently; I wish I could remember what it was). He was as proud as I ever saw him when he showed it to the teacher. The teacher's response was "that's neat, but it's kind of like doing cartwheels to get into your chair when you could just walk; why don't you just do the problems the way I showed you." It wasn't even me and it still hurts to think about.
I had a 5th grade teacher just like that. He thought outsmarting ten year olds made him pretty slick.
Well it is a neat trick, but it's sort of an antiquated thing, like unless you have an eidetic memory it's not worth memorizing bc calculators are always immediately available, and finding if something is divisible isn't an especially common a problem in the first place.
And this is why kids end up hating math. Teachers don't let them actually do math, and get excited about it. When a kid does actually do some math on his own the response is "that's neat" at best. Then back to following some formula that someone else came up with a long time ago.
I know people need to know what's already out there, but you've gotta encourage innovation at the same time
I remember being in 4th grade or so and I figured out how to make consistent divisibility rules for all prime numbers. I don't remember how.
Sounds like a teacher who didn't like math and didn't understand that kid's creation.
Matt: "We are putting the prime numbers on ebay."
Also Matt: *holds up the number 9*
9 is a Parker prime
9 is in fact 3x3, it's a parker square
He's doing integers by parts
No, it was a 6, but he was holding it upside down.
9 is the smallest fake prime in base 10.
My favorite method to see if a number is divisible by 7 is to use a calculator and see if it returns a whole number
edgy
But how do you know of it was a whole number or it just rounded to a whole numbee?
If I'm unable to sleep, then I think of a sufficiently large number, but not too large, to check if it's prime. I take an approximate square root in my head, and then I do the check of divisibility for each prime number up until the biggest one less than the original number's square root.
Because of this, I had to come up with divisibility rules in my head, and I always used this "take away the last digit, multiply it by a correct number, then subtract or add it to the rest" method. This way, I checked that 8329 is indeed a prime number, thus, it's my favorite one!
Coming up with the multipliers was a long mental process, though. I'm glad you made this video, Matt!
I would do the same thing while rollerblading. I determined that 1,023 was not prime that way. I would also determine multiples of large two- and three-digit numbers. It really helped pass the miles . . .
1023 shouldn't take long, but I also ignore a test of 2, 3, and 5 sometimes, which makes the realisation that 3 was a divisor all along really frustrating :D I'm glad I'm not the only one doing mental arithmetic to pass the time
Ha, what a bunch of nerds... anyways when I'm bored/passing time I try to approximate weird probabilities/distributions. Although it's often much harder to actually verify.
I tried this: Picked 8723, tested divisors until finding 11 as a divisor, and then promptly fell asleep for a good nine hours. Thanks! 😄
Not just me using that as a way of getting to sleep then! I look for ways of either getting rid of the first digit(s) or making the last digit(s) zero. So for 2716 adding 14 (a multiple of 7) gives me 2730 but I can just drop the zero and move on to 273 - add 7 and you get 28 and I'm done since I know my 7 times table. Different tricks work for different numbers but you can just knock out any 7 in this case for example or subtract 7 from any higher digit - so 9961 you can immediately reduce to 2261, then knock 21 off each end to get 14.
For anything over around 5000 chances are I'll be asleep on the first night and have to continue next time.
"Divisibility Rules" is the motivational phrase that keeps the composites going.
Wow, this is deep. I'm so angry at this joke but it was so good.
@ 3:08 If you actually continue with 35:
25 + 3 = 28 =>
40 + 2 = 42 =>
10 + 4 = 14 =>
20 + 1 = 21 =>
5 + 2 = 7.
7 is divisible by 7! And 7*5 = 35 where this started.
7 is not divisible by 7! you'd get 1/6!
7! is divisible by 7 as well :v
Not to be that guy, but.... 7 isn't divisible by 7!
Came to the comments looking for this. I love how it jumps up and down.
If you land at 49 at any point, you just get stuck because 4 + (9*5) = 49 again
The highest prime test to have been assigned is 23027 (The Taekiro tests). As of the video being released, 23029 and higher are all free real estate! (Coincidentally cut off is between twin primes)
This is so base 10 focused. To test if its devisable by a number x, first convert to base x, and if it ends with a zero, its dividable by that..
That’s basically just doing the divison 😂
On a more serious note, there are some very interesting patterns when you look at divisibility rules for different bases.
Are you serious now?
@@waz1y woosh
@@ltloxa1159 my fav is divisibility by n-1 in base-n. In base 10 that would be div by 9. So in binary it can work as div by 3, 7, 15, 31, 63 etc, just by grouping digits into higher 2^N base systems.
I think I prefer my own divsibility by n method...
1. Write the number down.
2. Stare at it for ten seconds.
3. Get annoyed that I can't remember any of the divisibility rules I've written down.
4. Give up.
5. Cave in and get a calculator for the actual result.
Works like a charm every time. 😂
My division by N method is just sequential subtraction.
Benefits: Easy to draw, Dont have to remember multiplication tables.
In quantum math, the probability is always that it is not divisible, unless it's div by 2 or 5.
I thought step 5 was going to be just do the division.
"I called it the vsause method." We live in a bizarre world where, if Matt comes up with something that actually works, he can't call it the Parker method, because that would make people think there was something wrong with it!
I think fairly early on, it’s easier to use the divisibility rule called “long division”. The only multiplying you need to do is working out the N times table up to 9N, and then it works for all values of N the same way. It even tells you *how many* times your number is divisible by N! (That’s just an exclamation mark, not N factorial)
IMO if the divisibility test still needs O(n) effort, it needs to be really intuitive, otherwise you are memorising random magic and have to believe that it worked for barely any time gain.
You mean O(logn), all of the tests described in the video, as well as long division itself, are proportional to the length of n, not n itself.
@@phiefer3 Oh yeah, sorry, I thought of n as the number of digits.
Makes sense, with long division you're just removing multiples starting at the highest digits. Also works with 2 and 5 :)
I'm so lost with all of this but I can do long division.
Terrible Python Code is the real star of this show
I want a Terrible Python Code t-shirt.
I remember asking my teacher in 4 the grade what the test for divisibility by 4 was. He looked at me like i had a squid hat on.
My teacher taught me "Drop everything but the last two digits, then if either digit is 4 or higher, subtract 4 from that digit (repeat for 8 or 9). Then check your times table."
@@torokkuroi6928that seems unnecessary complicated.
@@SkippiiKai Depends on how much of the times table you have memorized. No need to subtract if you know 68 is divisible by 4 off the top of your head, but most kids only learn up to 12 x 12 or so, and 4 x 17 is a bit off to the side.
@@siosilvaryes, but 60 is divisible and 8 is divisible therefore 68 is di isible by 4.
Or, 68/2=34 and 34/2=17. When we can divide by 2 twice, we have divided by 4.
Practically, I do not use divisible rules but the calculator. 0 decimals indicates divisibility.
@@torokkuroi6928 What I teach my students is "drop everything but the last two digits and divide them by 2. If the result is even it's divisible by 4"
The explanation for how all this works is so much more easy and beautiful! It all comes down to modulo classes. Take Michael's approach. Split any number into two parts so that the number equals 10a+b. If that is divisible by 7, then 3a+b is as well, which if multiplied with 3 is still divisible by 7: 9a+3b. Subtract that from 10a+b and you get a-2b which gives the same rest as a+5b. And that's his formula. Using those calculations you can get super nice divisibility checks. E.g. for 7: Take the first digit. Multiply with 3. Add the next digit. Multiply with 3, add the next digit... Until you added the last digit.
E.g. 112: 1*3 = 3, +1 = 4, *3 = 12, +2 =14 which is divisible by 7, so 112 is as well.
And if you take -3 instead of 3 you get the divisibility rule for 13.
Yes! I stopped the video before he did the proof, and worked it out myself.
Matt's method was extremely simple to prove:
100a + b = (98 + 2)a + b = 98a +2a + b = 7*(14a) + 2a + b ≡ 2a + b (mod 7)
I tried the same technique for the other two methods, but could not do it. I finally did something similar to what you did.
Using modular arithmetic, these divisibility rules are easy to prove. For instance in the method where you multiply the unit by 5 and add to the other digits, you first write the whole number as 10a + b. If this is divisible by 7, then this is 10a + b (mod 7) = 0. 10 (mod 7) = 3, so 3a + b (mod 7) = 0. Multiply by 5, and since 3*5 = 15 (mod 7) = 1, you get a + 5b (mod 7) = 0, which is the exact rule we want (5 times unit digit, plus the other digits).
I am a little surprise the 1001-trick wasn't mentioned. You capture three flies in one bang and it is fast for larger numbers since we don't do operations for every single digit, but instead just every third digit. Since 7•11•13=1001 you can actually check divisibility by both 7,11 and 13 in one nice swoop by utilizing this. Which is extra cool since they are three consecutive primes!
Here is how you do it. Example 1: I wonder if 11250057 is divisible by either 7,11 or 13.
1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 11 250 057
2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here -11+250-57 or simply 250-68 = 182.
3. Now all you have to do is to check whether 182 is divisible by either 7,11 or 13. We notice 182=7•26=7•2•13.
4. Cool 182 is divisible by both 7 and 13. Hence 11250057 is divisible by both 7 and 13 but not by 11.
Another example 2424737531233.
1. Group the digit in groups of 3 (hey! That's how we normally write them anyway). So 2 424 737 531 233
2. Then make every other group negative (it's wise to choose so we get a positive sum but not necessary). So here 2-424+737-531+233 = (2+737+233)-(424+531)=972-955=17
3. Now all you have to do is to check whether 17 is divisible by either 7,11 or 13. We notice 17 is prime.
4. Cool 2424737531233 is neither divisible by 7, 11 nor 13.
I got three minutes into re-watching your video on the Egyptian papyrus on fractions, and suddenly you show up in a notification telling me you have MORE to tell me on division? THIS CANNOT BE A COINCIDENCE 🤯
Interesting fact: some of these tests are only *"divisibility-preserving"* (iff the number had a remainder other than 0, the number that comes out will have a remainder other than 0, but potentially a different one), while others are *"remainder-preserving"* (the remainder is unchanged by the operation).
The tests that remove the singles digit (and do an implicit multiplication by 10) are only *divisibility-preserving* (with the exception of divisibility tests for 11, 9, 101, 99, 1001, 999, ... and their thirds). The tests that remove chunks from the large end (for example the divisibility tests for 7 based on 98 and 1001) are *remainder-preserving.*
You could probably turn a divisibility-preserving operation into a remainder-preserving one if you counted how many times you applied it, took the final remainder and multiplied it by "a certain number" that many times.
Where I think (but am not 100% sure) that the "certain number" is 10 mod N for divisibility tests by N.
The problem is that for divisibility tests for numbers between 10 and 20 the "certain number" is negative, which will flip-flop the sign of the remainder. And for divisibility tests above 20, you'd multiply the remainder by 10 as many times as you divide the original number by 10.
17:46 I do appreciate that Matt picked an example where no matter what number Nicole picked or how many mistakes Matt made, he would still be right 99.9% of the time. Truly the power of backstage maths.
My personal favorite divisibility test for 7 is the test in binary, where you split it up into chunks of three bits and add them up.
For example:
100101001001111011 = 152187
splits into
100|101|001|001|111|011
4 5 1 1 7 3
which, added up gets
100 +
101 +
001 +
001 +
111 +
011 =
10101 = 21 (base 10)
then
101 +
10 =
111 = 7
The reason I like it so much (besides the fact that it's easy for computers) is that it's functionally identical to the divisibility by 3 or 9 rule, but for binary. I was thinking about the 3 or 9 rule that we learn in elementary school when cutting cucumbers in my kitchen and was wondering about how it extended past those two numbers. I realized that my teachers never told us about how it also applies to 99, thus also 33 and 11 so long as you group the digits into pairs before adding them up. Likewise for 999, 333, 111, and so on for any 10^n-1 and its factors. It was about this point that I cut my finger and had to leave my cucumbers to get a bandaid.
oh no! wonderful story though
My favorite divisibility-by-7 test is in septimal, but quadrodecimal is quite okay too.
You get 10101, but then you add 101 and 10 as if you'd gotten 10110? What's going on?
For large decimal numbers, you can reduce them down to at most 6 digits by taking 6 digit chunks and summing them (padding one end of the original number with 0s to get enough digits if needed), which preserves divisibility by 7. It also preserves divisibility by all the other factors of 999999, though among other prime power factors, only 13 needs the full 6 digits - 27 and 37 each work with 3 digit chunks and 11 only needs 2.
@@KevinMcFlying
They included a zero at the left side to be able to split the number up into chunks of three without changing the value.
10101 =
010101
Splits into
010 | 101
Add them up
010 +
Watching this made me realize that breaking down why the divibility rules work is eye opening. It's such a cool feeling when you can understand why the math is happening the way it is rather than just following a rule.
I feel like that was part of the goal for common core, just implemented poorly. I feel lucky to have had amazing math teachers growing up that wanted us students to understand math rather than just memorizing rules. At the time as a child I couldnt understand, but now looking back at what I learned, I can see the beauty underneath
I'm just glad to hear that Michael is safe and sound
Fun fact, in seximal (base six), the units-based test will work for any prime greater than 3 out of the box, since all primes greater than 3 end in either 1 or 5 in base six (the 5 version works the same as the 9 version in decimal). Powers of primes other than 2 and 3 (six's factors) will also end in 1 or 5
It would actually be heximal bc hexadecimal exists
@@big_numbersno, it’s seximal or senary. although heximal was used by jan Misali iirc
@@Moldovallan1618 Other way around; senary is the official name, sometimes it gets called heximal, but jan Misali intentionally uses seximal because they dislike senary as a word and think heximal is too easily confused for hexadecimal.
23:32 that's the most unhinged thing I've ever heard. I'm gonna have to lie down for a bit
This is somehow the best patron benefit I have ever seen. I am definitely going to support your patron.
For small divisors, just find a nearby number known to be divisible, then check if the difference is divisible. It often makes the problem something you can do in your head.
This depends on what you mean by “small.” Using the example of 2716 from the video, I think it’s pretty easy to take 2800 (7*4*100) and see that the difference is 84 (7*12). Which additionally tells you that the dividend is 388 (4*100 - 12). Depending on how quickly your brain can make those connections, it might be faster than long division.
Funnily enough I find basically just doing the division so much faster than almost any divisibility trick. Obviously there are exceptions for 2 or 3 or the really easy numbers but at any point where you have to do a calculation or add/subtract different parts of the number i just do it straight up
7889/7
-7000
889-700
189-140
49 is divisible by 7. If I slowed down I would see it’s 1127x7 but if I just want to know whether it’s divisible or not I can just skip the division part and do most of the method for short division in my head
The video example:
2716
-2100
616
-560
56 is divisible by 7
3:26 -2 = 5 mod 7 so that's why that works too
19:40 so that's why I see 1312 graffitis everywhere
I am assuming this is referencing something completely unrelated to the video.
My curiosity is piqued. I would be most grateful if you would sate it.
1 = a, 2 = b, 3 = c and the rest is US politics
@@2001PiepsNo need for American exceptionalism, ACAB works just fine over here in Europe as well.
@@2001Pieps Officer Matt Thorton, among many others.
@@Antanana_Rivo Originated in the UK, in fact
I use the engineer's method of divisibility testing. Pull out the calculator and look for a decimal.
But, what if the answer is 4.0
There's a decimal right there
10000000000001 is arguably divisible by 10
@@skyjoe55As an engineer, I responsibly declare: it is divisible by 10. The main thing is to be within the margin of error
True engineers use a slide rule.
VSauce's test, with small numbers makes two loops: 49 -> 49 and 7 -> 35 -> 28 -> 42 -> 14 -> 21 -> 7. 56 turns into 35 and 63 turns into 21.
I remember getting a homework problem as an undergrad to create divisibility tests for various numbers based on modular arithmetic. This leads to some different tests than the ones in the video and is also neat imo. Could be a followup vid.
wow i feel proud i was looking at your thumbnail and was like 'hey that reminds me of an old ding video' and i was instantly validated :D
thank you mr count binface counting agent parker
Too bad there are no "spelling" rules for the title card at 1:00.
took me longer than i care to admit to spot the errror
@@servvonot sure that's an error exactly. When the word gets divided and shifts, the 'I' appears
The "you can just subtract out batches" approach has led me to a divisibility test that I think I like in practice: Subtract out 5*10^n for the largest n that makes that less than the number you're testing, then add 10^(n-1). So for 2716, you'd remove 5 500s and add 5 10s; 2716-> 216 -> 266. You've removed 490 5 times, which is a multiple of 7. Then remove 50 5 times and add 5 1s; 266 -> 16 -> 21. You've removed 49 5 times. That's a multiple of 7 so we're done. It's nice because you are just working with multiples of 10, which I find easier to manipulate in my head, even if it is based on the same basic math as the Veritasium approach.
*does a convoluted test for multiples of 1009 when no one asked except him and calculators exist*
19:46
"MATHS!"
"Now that's applied useful mathematics."
For any integer, n, divide the number by 17 (use long division). If the remainder is zero, then the number is divisible by 17. I call this "Pat's Rule."
Back when the dozenal video came out on Numberphile (at this point, almost a dozen years ago...), I started working out divisibility rules for base 12. For most of the single digit numbers, checking is fairly straightforward. For 2, 3, 4, and 6, it's just a case of looking at the last digit. 144 is divisible by 8, so that just requires the last 2 digits. 11 (el) can be found by summing the digits (for the same reason that 3 and 9 work in base 10). That left 5, 10 (dec), and 7, which I found amusing because 5 and 10 are two of the easiest in base 10.
Eventually, I found through trial and error that you could test divisibility by 5 by summing the ones digit, plus twice the 12s digit, plus 4 times the 144s digit, and so on - basically evaluating the number as if it were in base 2 instead of base 12. If the result was divisible by 5, so was the original!
The same method works for 10 as well, and a similar method worked for 7 (except you multiply by increasing powers of 5). After working through this, I found a general rule that works in any base:
To check if a (base b) is divisible by n (base b), evaluate a as if it were written in base c, where c is the remainder of b/n. If the result is divisible by n, so is a.
That makes me wonder what tests in base 2 or 16 look like and if they could be useful for computers
@@ljfaag Tests for 2^n + 1 or 2^n - 1 are fairly straightforward in binary. For example, the test for 7 is to split the number into 3-bit chunks (because 2^3 = 8) and add those together. If the result is a multiple of 7, so was the original number.
Conversely, for, say 17 (2^4 + 1), break the number into 4-bit chunks, then alternate adding and subtracting those chunks. If the result is divisible by 17, so was the original number.
I have no idea if any of these are any more efficient than just calculating the modulus and seeing if it's zero, though maybe they could be faster on custom hardware
That made me think and I'm pretty 2520 is the smallest base in which you can check the divisibility of the numbers 1-9 by looking at the last number, not that it would matter much in base 2520 anyways.
Also, this might be the first time someone recognizes you in random TH-cam comments, but I love your maze algorithm videos :)
@@Nawakooo0 2520 = lcm(1, 2, 3, ..., 9) so makes sense.
this video is exactly the kind of math i'm super interested in. I loved D!NG and Numberphile and remember watching both of those videos about divisibility rules, i'm stoked to get a comprehensive guide to one approach of solving the problem!
I just only just now realized the similarity of "Matthew" and "Maths" because of the intro. So it's really, "Stand -up Math-ew"? I must be the last person to notice this.
Just only just now
omg me to
Much better title! This one tells me that the video is about generalizing divisibility rules, whereas I didn't really know what I would be getting before.
Divisibility does rule!
divide and rule
I have the test for 8513.
Take the 10,000s, multiply by 1487, and add to the rest.
Multiply the units by 2554 and add.
Thanks for all the great videos Matt.
So what I’m going to take away from this is, when I hear a big number, I can just sagely remark in passing “divisible by one” and nod as if this was a singularly unique talent that I have cultivated.
That's one way to promote your patreon page XD great work Matt, such a fun video
Divisibility does rule
*divisibilty
I didn't realize that I wasn't subscribed! Thanks for the reminder even though TH-cam's algorithm already knew to send your videos my way.
4:36 Surely, it should be called the Parker method. Gotta follow the theme.
That would only be if something about it doesn't quite work...
Cool video! This helped me really understand how these divisibility rules can be created. Liked!
Some other people who are not Matt Parker or Steve Mould also known as Bec Hill!
Who graciously loaned the dice used in this video!
loaner of the Dice Jar of 458 Dice
@6:40 This was the biggest experience of simultaneous "what that can't possibly be right that's magic" and "that is very simply and obviously true" I've had in a long while.
(making this comment right after the first 3 methods have been introduced)
I find it's easiest to check divisibility by 7 by just diving by 7, but "backwards" from normal. Since the last digit of the multiples of 7 are unique from 0-9, just subtract the corresponding multiple that matches the last digit (if the last digit is zero, ignore it and compare with the rightmost non-zero digit), and repeat until the answer becomes clear.
For the example of 2716:
2716-56=2660
2660-560=2100=7x300
This gives the result of the division from the 1's place up, so 7x8+7x80+7x300=7x388.
Cannot believe I wasn't subscribed. Great as usaul! And thanks for the book!
Divisibility Rules! What does Divisibility rule? Was Divisibility elected? "Well, I didn't vote for you." "Help, I'm being repressed!"
That would have been funny a few years ago; now I just made myself sad again.
You're going to feel very foolish when your life begins to improve with the new gang.
@@bloodleader5 My life went into the toilet during his first term; it had been steadily improving since he left.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the covid hump with Biden actually doing anything of value.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the pandemic hump with Biden actually doing anything of value.
@@petersage5157 And yet the majority of Americans agree that everything has been insufferable for the last several years, and all statistics show that we are worse off than we were in 2019. You're confusing the comedown from the covid hump with the current administration actually doing anything of value.
The week after i first watched the james grime video, i also knocked together some terrible python code to find divisibility rules for every number up to 10000. To make the rules for composites i had it combine and simplify the divisibility rules for its prime factors into one function. Love the video as always, good stuff
> gets 1312
> "Oh, that's interesting."
:D
Why divide when you can unite?
Woo something is named after me!
17027 is a prime and has the 'Parrik' tests:
Take the 100,000,000s, multiply by 429, and add to the rest.
Multiply the units by 5108 and subtract.
i like divisibility rules
I agree, divisibility does rule
Divisibility rules rock
I’d definitely watch a livestream of Matt checking if really big numbers are divisible by 7. Its very satisfying
I really hoped Matt Parker would have shown how to construct these divisibility rules, so I came up with my own method. Find prime P and natural number N such that P*N = a *10^b + c
P=313 N=16 a=5 b=3 c=8
313*16=5 *10^3 + 8
313*16=5008
Now we can test for 223795=313*13*11*5
Split 223795 after the b:th number, 3rd in this case.
223795/10^3=223.795 decimal point separates the components A, B
Multiply the A=223 by c and subtract from the rest B=795 multiplied by a
B*a-A*c=
795*5-223*8=2191
Repeat if needed till you get to small enough number.
2191/10^3=2.191
191*5-2*8=939
which is easy to see that's 3*313
Some bad combinations don't reduce the starting number but they are at least always divisible by P. Those cases could be called Parker divisibility rules.
Another way to prove Michael's is that, at any step, the difference between applying each method is 7×units, so if one is a multiple, then so is the other
I like Matt's divisibility-by-7 rule the best as it preserves the remainder. So that, for example, if the final number is one off from being divisible by 7, then the original number is also one off from being divisible by 7.
You can preserve the remainder with the Michael/Grime tests for 7 by iterating them 6n times.
This applies for every odd number (except multiples of five):
Find the first multiple of your factor with a one in the ones' digit. Take that multiple and drop the ones' digit. multiply the new number by the ones' digit of the number you're checking. This works because multiplying the ones digit will cancel out, which is why you drop the last digits.
I really like this explanation for the divisibility rules for 7 over using modular arithmetic. The modular arithmetic works but this is super intuitive!
Your videos are sooooo cool. I literally smile watching the maths unfold. Really appreciate the content!
All of these sound like long division with extra steps
Ah! This is so cool, no more wobbling whiteboard held in one hand. The top camera view of the entire page on the desktop is so cool!
Thanks Matt.
For whatever reason I really liked what you did with the intro :)
You easily see Michael's version as follows:
10a+b is div. by 7 iff a+5b=5(10a+b)-49b is div. by 7. (for 2716, a=271 and b=6)
18:35 „..68, gotta multiply that by 28.. Ach.. great“ *cut to some multiplication. I don’t know why i think that’s so funny but I can’t stop watching it xD
eBay? Shouldn't the Prime numbers be on Amazon?
Ba dum tsss! 😂
"16384: Ignore everything from the 100,000,000,000,000s up."
Ah yes, this makes my life so much easier
Great, now I got my own rule. I hope you all use it regularly as it is a very handy one:
6841 is a prime and has the 'DarkElder' tests:
Take the 1,000,000s, multiply by 1214, and add to the rest.
Multiply the units by 684 and subtract.
Sounds pretty straight forward indeed. Thanks, Matt! 😆
I think this was one of the best maths videos on TH-cam, thoroughly enjoyed it! I've always wondered - of course, not so much as to look it up - how those divisiblity rules are created.
Now I wonder, are there any other generalizable methods besides summing/subtracting to a power of 10 🤔
A general rule I like to remember is that if the divisor's rightmost digit is co-prime to the base (1, 3, 7, and 9 in base 10), then each multiple from 0-9 of that divisor has a unique digit in the 1's place; this means that you can do some pretty simple "backwards" long division.
Let's say we want to see if 63893 is divisible by 7 (I have no clue if it is yet):
63893-63=63830
63830-630=63200
63200-4200=59000 (which is clearly not divisible by 7)
May not be the easiest mental math method, but can reasonably be done quickly with pencil and paper; just scratch out the multiples of the divisor from 1-9 to the side and subtract whichever one matches the current rightmost non-zero digit.
19:55 "now that's applied, useful mathematics" 😆
Isn’t Collatz conjecture just shorthand for the divisibility tests of every prime number? See 16:17. So applying it will always reduce the number over time, factors out all prime factors except 1, and loops at the end because it’s a divisibility test. The fundamental theorem of arithmetic states a unique factorization exists for every number. This ensures there are divisibility tests to check for all of them.
this is a nice way of explaining it without involving explicit modular arithmetics! but i also like working in modular arithmetics since it allows you to take plenty of shortcuts for these. for example, we can view the +5/-2 rule (which are trivially equivalent in modular arithmetics) as 1/10 (=1/3) in the modulo 7 group. so essentially, we just divide the whole number by 10, just like matt said in this video.
This is so easy to understand one you talk in decimal. Thanks!
On the topic of fast prime tests, you should look into (or do a video on) the Miller-Rabin primality test. It's technically probabilistic for each individual witness test, but it is **extremely** fast (as in like basically instant for all 64-bit numbers), and it's fairly easy to implement and understand too. And heck, you _can_ make it be robust and polynomial time if you assume the generalized Reimann hypothesis or use the hand-selected witnesses for your test range.
proud to be the patron for the divisibility test for 12497
As of writing this, I have the video pause at 5:11, the instant after you finished showing all 3 methods.
I think I figured out the trick with the Michael version. In the Michael version, what you are actually calculating is "how many times do I have to add 49 to this in order to get a 0 and the ones place, which I can then remove". (49·6)+6 = 50·6, and in fact (49·x)+x = 50·x.
The James version is the same thing, but in reverse. Since the only thing that matters is the modulo, the remainder, going in reverse doesn't matter. You get the same result although you might have an occasional negative value since you are subtracting.
From this I think I can infer how you would go about creating more of these rules. Now the question I have is whether these additional rules, and the pattern of creating them, actually make the computation of divisibility any faster, in terms of computational complexity. Does this discovery do anything that weakens RSA cryptography?
Hey Matt, Vsauce here 9:56 is how Michael does everything
In decimal, I find a multiple of the divisor where the last digit matches the one in the dividend. Then I subtract and divide by 10 as many times as necessary.
So for 2716
2716-56 = 2660 ==> 266
266-56 = 210 ==> 21
21-21 = 0 ✓
It's "easier" in binary! I'll comment under this one for those interested.
In binary, I divide both by 2 until one or both is odd. If the divisor is still even, it is not divisible.
Then loop until the dividend is smaller than the divisor at any step:
* Divide the dividend by 2 until it is odd
* Subtract the divisor
If you are left with 0, it is divisible.
This "binary" way doesn't require you to find multiples, so for 2716, since 7 is odd, we can skip the first part:
2716 ==> 1358 ==> 679
679-7 = 672 ==> 336 ==> ... ==> 21
21-7 ==> 14 ==> 7
7-7 = 0 ✓
Hello Matt, thank you for keeping maths fresh. Also - good man for declaring the ownership of the dice, just as promised
Finally! A video that talks about all the divisibility tests; as I knew about the fact that there’s a pattern between similar divisibility tests.
I just want to say thank you Matt. That shelf behind you drives me absolutely bonkers being crooked in frame.
I laughed when I saw you adding from right to left. I am terrible at math, but when I was a chemist in a lab, my boss showed me how to add from left to right. It’s faster and more accurate, and you can do it in your head without any “carry the ones”.
Matt's "but I didn't stop there", reminds me of a scene from a British sitcom called My Hero, where a doctor says "Apparently one dose is enough to bring a giraffe to its knees.... so I put in 4".
I was once in a unique situation: at a competition where I knew I had ten minutes to answer a question about arithmetic mod 7. So before I started, I wrote down the multiples of 3 mod 7 for digits 0-9 so that I could start with the first digit and multiply by 3 and add the next digit all while taking mod 7, effectively evaluating the base-10 expansion of the number (10 mod 7 = 3). The interesting thing though is that this is generalizable-by simply starting with the first digit and continuously multiplying by 10 and adding the next digit all while taking the modulo of the number for which you want to test divisibility, you can compute any number modulo any other number without having to divide large numbers and test for divisibility by seeing if the result is 0 or not. It wouldn't be too far or a stretch to call this "the universal divisibility test".
5:10 matt's is the most intuitive to me, since it's just adding all the remainders of the hundreds (100 = 14*7 + 2, so 2 for every hundred) to everything below 100, which is a lot like the well known rule for divisibility by 3
the "michael" and "james" methods i have not yet figured out, but i can tell they have to be equivalent because 7 - 2 = 5, so the amount added always will differ by a factor of 7 between them
so i just have to figure out why 10a + b is divisible by 7 if a + 5b is divisible by 7 (assuming a & b are integers, of course)
*edit:* got it, if we take 5*(10a + b) = 50a + 5b, the remainders for all the 50s in 50a will just be a, because 50 = 7*7 + 1
so we're checking the divisibility of x through the divisibility of 5x and skipping a step, and since 5 and 7 are coprime this doesn't alter the divisibility by 7 at all
meanwhile we could take the same tack with the "james" method, because -20 = -3*7 + 1, and 2 is still coprime with 7, so -2x = -20a + -2b (equivalent to a + -2b in mod-7) will be divisible by 7 if x is divisible by 7
0:23 Didn't see that video, but was told a rule for 7 by my grandfather, which is the one all of those people say. I had to be told by my grandfather, because they always told me there wasn't one (and it seemingly there's more than one), but they also kept reducing the divisibility tests to teach to schoolchildren every few years (I believe at least some of my younger siblings had textbooks that said that there was no test for multiples of 11).
really thought you would talk about the division graphs that james mentioned on an even more recent Numberphile video! they are very visual, fitting your video style very well
I've never seen the title of a video change in real time before:
"I cracked the divisibility code." --> "New Divisibility Rule (30,000 of them)"
Literally changed to the second title as Matt said '30,000' and I thought it was a new feature
I love divisibility rules, and I have known the divisibility rule for 7 for quite a while, the one that James used of subtracting two times the units digit from the rest of the number. For some reason it felt like to me as if it's some bizarre number theory result or something, and I didn't look it up as I wanted to maybe prove it myself. Didn't get to doing that, mainly because I was demotivated, and then I see this video, where Matt very casually says why it works and it's so simple it kind of makes me want to cry.