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)
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 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.
@@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 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)
2 місяці тому+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.
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.
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.
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.
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.
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).
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 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 🤯
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.
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.
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.
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
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.
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 +
*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."
As usual, very entertaining and instructive video. 👍👍👍 Myself, I like to use a variation on a classic: Euclid book 7, proposition 2, the one about greater common divisor. It goes like this: 2716 - 2100 = 3x 7 x 10^2 616 - 560 = 8 x 7 x 10 56 - 56 = 8 x 7 0 (no reminder so 7 measures (divides) 2716 More then 2000 years old and still working :-)
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."
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! 😆
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 UA-cam comments, but I love your maze algorithm videos :)
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.
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.
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.
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.
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.
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
@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.
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 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.
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.
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
This is a nice explainer. At the start of the video, I paused and proved the modulus 7 congruence of 10a+b and a+5b and a-2b. This method turned out to be straightforward once I observed that 7a and 7b are both congruent to 0 modulo 7. It also required division by 3, so 3 must be coprime with 7. Which, yeah, no problem there. Generalizing this method could be tricky for a non-prime modulus. Other bases would be easy with this method. Instead of starting from 10a+b, just start from base*a+b, or raise the base to a greater power if you want to remove multiple digits at once.
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 rule for div. by 7 I was taught in elementary school (and it works for similar reasons you discussed) is the 1,3,2,-1,-3,-2 rule, i.e., multiply digits from right to left by 1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,... and then add them up.
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.
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.
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, A good prime generation method for "small" prime numbers is running the Sieve of Erathostenes up to 65535 (i.e. 2^15-1) and then using the listed primes to check all numbers up to 2^32. The initial list of primes up to 65536 used to run in 0.24s in a Penthium 3 under Linux with the code compiled in GCC. Typing it took less than 5 minutes if you would often repeat it for classes XD
Fun little story from my own experience: In 5th grade, I noticed that we learned a divisibility rule for all of the first ten numbers EXCEPT 7, so I set out to find one. Don’t remember how I got there, but I found one that I’ve never seen anywhere else, probably because it’s so complicated. It involves multiplying the FIRST digit by a multiplier and adding that to the rest of the number. However, the correct multiplier depends on how many digits there are: 6n+1 digits: x1 6n+2 digits: x3 6n+3 digits: x2 6n+4 digits: x6 6n+5 digits: x4 6n digits: x5 The sequence of multipliers depending on the place value follows a repeating pattern (going up) of 1,3,2,6,4,5… I always found it fascinating that this pattern resembles the order of the decimal expansion of 1/7: 0.142857 repeating. I finally discovered the explanation behind this link in 10th grade, but I’ve forgotten it by now.
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”.
When I am bad at remembering those rules. I think I will just add (or substract, just what is more convenient) a number divisable by seven that gives me a 0 at the end and then divide by 10. 2716 + 14 = 2730 , 273 + 7 = 28. Done. (for the non-daily-doing-math people this should be easy to remember). Thanks Matt. Good One.
Matt - I have been doing this type of thing for working out factors of large numbers - or proving they are prime - as a mental arithmetic exercise. I realised that to get rid of the last digit (1,3,5,7) you either have to add 1 or 3 times the factor or subtract 1 or 3 times the factor to eliminate the last digit.
My favorite way of doing a test for 53 is easy. Take the right most digit - the ones - and multiply by 6/7. After that, add the 10's digit to it and multiply by 6/7. Add and multiply until all the digits are added in. When you have a non-mixed fraction just get right of the denominator, which must be a power of 7. The resulting integer will divisible by 53 only if the starting one was. It's a lot simpler than your method. For a test of 23, use -3/2 but start from the most significant digit.
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
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 think you're underselling the practicality of this, since modern encryption systems rely on multiplying large primes together. I suppose it depends on the efficiency of the code, but automating the process of generating divisibility rules for large prime numbers would seem to be pretty helpful.
I'm used to proceeding using two digits at once. The principle is simple, check the remainder to 100. 100 is 98+2 so you multiply then 100s by 2 and add the units. E.g. 371 is 3*100+71 you do 2*3 = 6 + 71 = 77 => divisible by 7. Likewise, 39746 is solved as 2*397=794 + 46 = 840 => 7*120 (or you can recurse as 2*8+40 = 56) => divisible by 7. The same principle works with all other divisors below 100. 11 requires to multiply by 1, 13 by -4, 17 by -2, 19 by 5, 23 by 8, 29 by 13, 31 by 7, 37 by -11 etc. You can do the same with more digits at once. For example 1001 is divisible by 7 (7*11*13) so you can subtract the 1000s from the lowest parts (precisely you multiply the 1000s by -1). In my previous example, 39746 would simply result in 746-39 = 707 => 7*101, done! It's just generally harder to remind all remainders above 100. The approach seems logical to me and doesn't require to remember any particular trick.
This "times 5 plus the rest" kinda reminds me of the 3x+1 problem. If you continue the method after 35, you get 28, 42, 14, 21 and 7. And if you do this method one more time, 7*5+0, you loop back to 35 again.
I don't think I will be seen, but I think there is a better method to think about divisibility. For example, divisibility by 7: Let's say we have number A with n digits: A = a1 + a2 × 10 + a3 × 100... We look up the closest multiple of 10 (not by 7), to a multiple of seven. In this example it is 5 × 10 = 50 (49 + 1). Now, let's multiply two sides of the equation by 5. Since 5 is not divisible by 7, it doesn't affect our test. 5A = 5 × a1 + 50 × a2 + 500 × a3 Our number 5A has two sides: 1) 49 × a2 + 490 × a3 + 4900 × a4... 2) 5a1 + a2 + 10a3 + 100a4... 1) is clearly divisible by 7. So if 5×a1 + A' (the rest of the number) is divisible by 7, then the number itself must be divisible by 7.
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.
One of my strange customs I had years ago was trying to to prime factorizations (of 4-digit numbers) in my head (when trying to fall asleep, as a replacement for counting sheep). This needed both the divisibility, but also then the other factor to continue. What I used was a process like this (here for the example 2716, and the 7): → Last digit is 6. What multiple of 7 ends with 6? 56. → Subtract 56 (or rather, cut off the last digit, and subtract 5). → We are left with 266. Oh, nice, again a 6. → Subtract 56 again (or rather, cut off the last digit, and subtract 5). → We are left with 21. → So now we know it's divisible by 7. → But if we go backwards, we also get the digits of the other factor: 3 (21 = 7×3), 8 (56 = 7×8 ) and 8. → So 2716 = 7 × 388. (I feel that this is somewhat easier than doing the long division I learned in school (at least in my head without paper).) Now continue with 388. (Of course, I'd normally start checking divisibility (and factoring out) the easier 2, 3, 5 and 11 before I go to 7, just used this example here as it was in the video. This also means I basically only have to remember the reverse multiplication table for odd numbers.) We end up with 2716 = 2² × 7 × 97.
I came up with a really good divisibility test that works most of the time large primes. I think it's revolutionary! To check if any number Q is divisible by a prime P>1000, take the last digit of Q and blink that many times, making voodoo noises. Then Q is not divisible by P. Works more than 99.9% of the time!
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".
15 years ago me and a schoolmate were introduced to the divisibility rule for 7. We became fascinated and eventually worked out a generic method that produced a rule for any number. We only worked on paper in our spare time and applied out to the 50s for fun. Good times.
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
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?
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.
"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.
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.
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)
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 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.
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.
@ 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
"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.
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.
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"
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.
Terrible Python Code is the real star of this show
I want a Terrible Python Code t-shirt.
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.
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).
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 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 🤯
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.
I'm just glad to hear that Michael is safe and sound
23:32 that's the most unhinged thing I've ever heard. I'm gonna have to lie down for a bit
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.
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.
3:26 -2 = 5 mod 7 so that's why that works too
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.
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
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.
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 +
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
@@travcollierIt was done on *purpse
*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."
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
As usual, very entertaining and instructive video. 👍👍👍
Myself, I like to use a variation on a classic: Euclid book 7, proposition 2, the one about greater common divisor.
It goes like this:
2716
- 2100 = 3x 7 x 10^2
616
- 560 = 8 x 7 x 10
56
- 56 = 8 x 7
0 (no reminder so 7 measures (divides) 2716
More then 2000 years old and still working :-)
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."
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! 😆
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 UA-cam comments, but I love your maze algorithm videos :)
@@Nawakooo0 2520 = lcm(1, 2, 3, ..., 9) so makes sense.
This is somehow the best patron benefit I have ever seen. I am definitely going to support your patron.
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.
> gets 1312
> "Oh, that's interesting."
:D
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
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.
Divisibility does rule!
divide and rule
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
*divisibilty
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.
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.
Why divide when you can unite?
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
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
Cool video! This helped me really understand how these divisibility rules can be created. Liked!
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...
@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.
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 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.
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.
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
This is a nice explainer. At the start of the video, I paused and proved the modulus 7 congruence of 10a+b and a+5b and a-2b.
This method turned out to be straightforward once I observed that 7a and 7b are both congruent to 0 modulo 7. It also required division by 3, so 3 must be coprime with 7. Which, yeah, no problem there.
Generalizing this method could be tricky for a non-prime modulus.
Other bases would be easy with this method. Instead of starting from 10a+b, just start from base*a+b, or raise the base to a greater power if you want to remove multiple digits at once.
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 rule for div. by 7 I was taught in elementary school (and it works for similar reasons you discussed) is the 1,3,2,-1,-3,-2 rule, i.e., multiply digits from right to left by 1,3,2,-1,-3,-2,1,3,2,-1,-3,-2,... and then add them up.
i like divisibility rules
I agree, divisibility does rule
Divisibility rules rock
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.
All of these sound like long division with extra steps
I’d definitely watch a livestream of Matt checking if really big numbers are divisible by 7. Its very satisfying
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.
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?
19:55 "now that's applied, useful mathematics" 😆
Hey Matt,
A good prime generation method for "small" prime numbers is running the Sieve of Erathostenes up to 65535 (i.e. 2^15-1) and then using the listed primes to check all numbers up to 2^32.
The initial list of primes up to 65536 used to run in 0.24s in a Penthium 3 under Linux with the code compiled in GCC.
Typing it took less than 5 minutes if you would often repeat it for classes XD
Fun little story from my own experience: In 5th grade, I noticed that we learned a divisibility rule for all of the first ten numbers EXCEPT 7, so I set out to find one.
Don’t remember how I got there, but I found one that I’ve never seen anywhere else, probably because it’s so complicated.
It involves multiplying the FIRST digit by a multiplier and adding that to the rest of the number. However, the correct multiplier depends on how many digits there are:
6n+1 digits: x1
6n+2 digits: x3
6n+3 digits: x2
6n+4 digits: x6
6n+5 digits: x4
6n digits: x5
The sequence of multipliers depending on the place value follows a repeating pattern (going up) of 1,3,2,6,4,5…
I always found it fascinating that this pattern resembles the order of the decimal expansion of 1/7: 0.142857 repeating. I finally discovered the explanation behind this link in 10th grade, but I’ve forgotten it by now.
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)
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”.
eBay? Shouldn't the Prime numbers be on Amazon?
Ba dum tsss! 😂
When I am bad at remembering those rules. I think I will just add (or substract, just what is more convenient) a number divisable by seven that gives me a 0 at the end and then divide by 10. 2716 + 14 = 2730 , 273 + 7 = 28. Done. (for the non-daily-doing-math people this should be easy to remember). Thanks Matt. Good One.
Matt - I have been doing this type of thing for working out factors of large numbers - or proving they are prime - as a mental arithmetic exercise. I realised that to get rid of the last digit (1,3,5,7) you either have to add 1 or 3 times the factor or subtract 1 or 3 times the factor to eliminate the last digit.
My favorite way of doing a test for 53 is easy. Take the right most digit - the ones - and multiply by 6/7.
After that, add the 10's digit to it and multiply by 6/7.
Add and multiply until all the digits are added in.
When you have a non-mixed fraction just get right of the denominator, which must be a power of 7.
The resulting integer will divisible by 53 only if the starting one was.
It's a lot simpler than your method.
For a test of 23, use -3/2 but start from the most significant digit.
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
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 think you're underselling the practicality of this, since modern encryption systems rely on multiplying large primes together. I suppose it depends on the efficiency of the code, but automating the process of generating divisibility rules for large prime numbers would seem to be pretty helpful.
Hey Matt, Vsauce here 9:56 is how Michael does everything
"16384: Ignore everything from the 100,000,000,000,000s up."
Ah yes, this makes my life so much easier
I'm used to proceeding using two digits at once. The principle is simple, check the remainder to 100. 100 is 98+2 so you multiply then 100s by 2 and add the units. E.g. 371 is 3*100+71 you do 2*3 = 6 + 71 = 77 => divisible by 7. Likewise, 39746 is solved as 2*397=794 + 46 = 840 => 7*120 (or you can recurse as 2*8+40 = 56) => divisible by 7. The same principle works with all other divisors below 100. 11 requires to multiply by 1, 13 by -4, 17 by -2, 19 by 5, 23 by 8, 29 by 13, 31 by 7, 37 by -11 etc. You can do the same with more digits at once. For example 1001 is divisible by 7 (7*11*13) so you can subtract the 1000s from the lowest parts (precisely you multiply the 1000s by -1). In my previous example, 39746 would simply result in 746-39 = 707 => 7*101, done! It's just generally harder to remind all remainders above 100. The approach seems logical to me and doesn't require to remember any particular trick.
Your videos are sooooo cool. I literally smile watching the maths unfold. Really appreciate the content!
This "times 5 plus the rest" kinda reminds me of the 3x+1 problem.
If you continue the method after 35, you get 28, 42, 14, 21 and 7. And if you do this method one more time, 7*5+0, you loop back to 35 again.
I don't think I will be seen, but I think there is a better method to think about divisibility. For example, divisibility by 7:
Let's say we have number A with n digits:
A = a1 + a2 × 10 + a3 × 100...
We look up the closest multiple of 10 (not by 7), to a multiple of seven. In this example it is 5 × 10 = 50 (49 + 1).
Now, let's multiply two sides of the equation by 5. Since 5 is not divisible by 7, it doesn't affect our test.
5A = 5 × a1 + 50 × a2 + 500 × a3
Our number 5A has two sides:
1) 49 × a2 + 490 × a3 + 4900 × a4...
2) 5a1 + a2 + 10a3 + 100a4...
1) is clearly divisible by 7.
So if 5×a1 + A' (the rest of the number) is divisible by 7, then the number itself must be divisible by 7.
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.
proud to be the patron for the divisibility test for 12497
Having a divisibility rule named after you might be the first small step on a journey that will end having a square named after you.
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.
That's one way to promote your patreon page XD great work Matt, such a fun video
Getting a divisibility test named after you is honestly the most tempting crowdfunding incentive I have ever encountered
One of my strange customs I had years ago was trying to to prime factorizations (of 4-digit numbers) in my head (when trying to fall asleep, as a replacement for counting sheep).
This needed both the divisibility, but also then the other factor to continue.
What I used was a process like this (here for the example 2716, and the 7):
→ Last digit is 6. What multiple of 7 ends with 6? 56.
→ Subtract 56 (or rather, cut off the last digit, and subtract 5).
→ We are left with 266. Oh, nice, again a 6.
→ Subtract 56 again (or rather, cut off the last digit, and subtract 5).
→ We are left with 21.
→ So now we know it's divisible by 7.
→ But if we go backwards, we also get the digits of the other factor: 3 (21 = 7×3), 8 (56 = 7×8 ) and 8.
→ So 2716 = 7 × 388.
(I feel that this is somewhat easier than doing the long division I learned in school (at least in my head without paper).)
Now continue with 388. (Of course, I'd normally start checking divisibility (and factoring out) the easier 2, 3, 5 and 11 before I go to 7, just used this example here as it was in the video. This also means I basically only have to remember the reverse multiplication table for odd numbers.)
We end up with 2716 = 2² × 7 × 97.
I came up with a really good divisibility test that works most of the time large primes. I think it's revolutionary! To check if any number Q is divisible by a prime P>1000, take the last digit of Q and blink that many times, making voodoo noises. Then Q is not divisible by P.
Works more than 99.9% of the time!
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".
15 years ago me and a schoolmate were introduced to the divisibility rule for 7. We became fascinated and eventually worked out a generic method that produced a rule for any number. We only worked on paper in our spare time and applied out to the 50s for fun. Good times.