the unluckiest divisibility rules
Вставка
- Опубліковано 7 кві 2024
- 🌟Support the channel🌟
Patreon: / michaelpennmath
Channel Membership: / @michaelpennmath
Merch: teespring.com/stores/michael-...
My amazon shop: www.amazon.com/shop/michaelpenn
🟢 Discord: / discord
🌟my other channels🌟
mathmajor: / @mathmajor
pennpav podcast: / @thepennpavpodcast7878
🌟My Links🌟
Personal Website: www.michael-penn.net
Instagram: / melp2718
Twitter: / michaelpennmath
Randolph College Math: www.randolphcollege.edu/mathem...
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
🌟How I make Thumbnails🌟
Canva: partner.canva.com/c/3036853/6...
Color Pallet: coolors.co/?ref=61d217df7d705...
🌟Suggest a problem🌟
forms.gle/ea7Pw7HcKePGB4my5
Rule 1: the multiples of 10^(3n) should have been 10^(3n-1), which ends up to be 10^3 and 10^0 for the last two sets of three digits. No change either way as the signs are still alternating.
Edit:
Yeah, should have been 10^[3(n-1)].
Ah! I was wondering about this precise point. Thanks for the clarification.
We could also argue that the result of multiplying the original number by 10^3 will be as multiple of 13 as the original; and then this 10^3*original is what's shown in the blackboard.
Don't you mean it should've been 10^(3n-3) ?
@@gerryiles3925yeah, it should’ve been 10^(3n-3), even I was getting that
@@xnick_uyyeah, that’s really neat, but he should’ve mentioned it lol
One thing to note the first rule with the alternating 3 blocks also works for 7 and 11, so you can reduce it to one number and then do all 3 checks from the base 3 digit number
it should since 1001 = 7*11*13
The fact that 7*11*13 equals 1001 made me fall in love with base ten. It's so cool and makes it really quick and easy to check if a number has divisors
You will love base 13! - 1 then 🤓
1001 is one of my favourite numbers...
Because in school, some teachers would give us numbers like 'abcabc' that involved factorization.
Once I realized 1001 = 7 * 11 * 13, I exploited it to build my own rule of divisibility by 13.
4,219,358 ----> 215,358 ----> 143 which is a multiple of 13.
It didn't work as elegantly as this for all numbers... But hey, it was my rule. And it works for 7 and 11 too.
I like using iterated subtraction for divisbility, it has a nice logic behind it. Gets unwieldly for large divisors, but that's to be expected.
The first rule is essentially the same as that for 11 but in base 1000.
It works for any divisor of 1001. Also it preserves the remainder module 1001 (and it's divisors).
That is different to the other rules, wich only project remainder 0 to 0.
I've seen a general divisibility rule: take the prime you want to check divisibility with, find its first multiple that ends with 9, add one, remove the zero at the end, this number is called the osculator (if my memory isn't playing tricks on me), take the number you are checking divisibility of, remove the last digit and multiply it with the osculator, add it to the remaining digits of the original number, repeat as needed until the result is manageable, if result is 0 mod the prime, then divisibility is given. Ex.: 98 div by 7? 7x7=49-> osc=5, 9+5x8=49 ->yes.
Nice! In particular, in the case of 13, we have 3×13=39, 39+1=40, so the osculator is 4, which gives Michael's rule number 2.
The "divvy-number!" (Prof. Tony Padilla, on a very similar Numberphile video)
I think it would be fun to explore divisibility rules in different number base system, and see correlations.
It is really fun to do
Here's an easy divisibility rule for any prime other than 2 or 5: Take the integer, split it into blocks of length p-1, and add the results (which comes from Fermat's little theorem). It's a little impractical for primes bigger than 3, though.
From 20 = -1 (mod 7) you get the rule that a number is divisible by 7 iff the result from removing the last digit, multiplying it by 2 and subtracting it from what remains is divisible by 7.
E.g. 2023 => 202-2*3 = 196 => 19-2*6 = 7, so 2023 is divisible by 7.
This reminds me that I once heard John Horton Conway say "91 is the smallest number that looks prime but isn't." (It's 7x13 and this JHC joke is why I remember that.)
My favourite lecturer at Cambridge!
@@MichaelRothwell1 I worked at Bell Labs when he was at Princeton. He came to the Labs all the time to work with Neil Sloane
@@TomDuff"Brady, let me show you a few sequences..."
-Sloane, not too long ago
At about 2:00, Michael discusses that rule number one "generally" nets you a large number. That is probably true, but it can also easily net you a small number such as 13, as do the following numbers, which I constructed such that alternating sums add to 13 and which are therefore divisible by 13: 158171 and 172315156. Making blocks adding to 0 is obviously trivial and works too, since by the proof shows any number of the form abcabc is divisible by 13. Which also means any number of the form cdecdeabcabc is divisible by 13, etc. Obviously, I could also assemble a number with the larger number on either side of the inverted blocks of the smaller number to have a much larger number which adds to 13. Than there is 100100 which obviously satisfies both the divisibility by 11 and the divisibility by 13. In fact, any 3 digit number divisible by 11 builds a 6 digit number divisible by 13 when you repeat it. So do the same digits repeated twice into a 12 digit number, when the sum was 0 for the blocks of 3. So far I "cheated" by always using 2 blocks of 3 when discussing divisibility by 13 and 11, which makes it easy. How easy is it to construct a 9 or 15 digit number which is divisible by 11 and 13? Are there "classes" of such numbers in the same way that the abcabc numbers work? 123246123 works but I am not sure about a pattern there.
At last, an analysis of my favourite number since childhood.
9:01 you need a6a5a4 * 10³, not 10^6 and same for a3a2a1, it needs to be multiplied by 1, not 10³, though the divisibilty trick works pretty much the same way? Nice video!
The digit sum congruence for base b works for the divisors of b - 1. That's where the digital root = multiple of 9 => number divisible by 9 comes from. If you treat a multiprecision integer in RAM on a 64-bit CPU as a base 2^64 number you get a quick check for divisibility by 3, 5 and 17 (and many others). It's much faster to sum a vector of 64-bit words than to do a modulus operation (you can likely take a SIMD approach if you don't mind a bit of assembly programming).
I do it from left to right, subtract the leftmost digit 3x from the next digit, and do a mod 13 on the result. Iterate until you get something for which you know whether it is divisible:
4219358 -> (-10)19358 = 319358 -> (-8)9358 = 59358 -> (-6)358 = 7358 -> (-18)58 = 858 -> (-19)8 = 78 -> (-13) = 0 so it is divisible.
That also works for divisibility by 11, 12, 14 etc. if you replace the x3 with x1, x2, x4, etc.
Rule 4: the result from removing the last two digits, multiplying by 3 and adding it to what remains is divisible by 13
Hello please give this problem a try:
Cynthia loves Pokemon and she wants to catch them all. In a road, there are a total of 50 Pokemon. Cynthia wants to catch as many
of them as possible. However, she can not catch any two Pokemon that are
enemies with each other. After exploring around for a while, she makes
the following two observations.
1. Every Pokemon in the road is enemy with exactly two other Pokemon.
2. Due to her inability to catch Pokemon that are enemies with one another,
the maximum number of Pokemon that she can catch is equal to n.
What value of n?
Thank you, I am always happy I watched your videos
For divisibility by 13: take the leftmost digit, multiply by 3, subtract the next digit, multiply the result by 3, add the next digit, multiply the result by 3, subtract the next digit, multiply the result by 3 ... alternating adding and subtracting digits in turn, until you run out of digits. The final result will be divisible by 13 if the original number is.
For me personally, I like a fun little exercise before sleep to tire my mind. I come up with a number (usually reading the clock's 4 digits) and determine if it is prime or not. Of course, I leave anything divisible by 2, 3 or 5 and only care about the rest. To test of a number is prime, I take the approximate square root of that number in my head. This number is the upper limit until which you need to check divisibility by prime numbers.
However, all of this being mental arithmetic, I need to check divisibility by lots of prime numbers, so I have to come up with their divisibility rules. I always check for the rule: add or substract x times the last digit to the remaining number. I find x by trial and error. I found one night that 87*2=174, so I would need to check if 174+8 or 174-8 is divisible by 7. This will decide whether I would need to subtract or add the last digit times a number, respectively. 182=26*7, and from that to get 174, we need to subtract 8. This means that any number is divisible by 87 if you subtract 26 times the last digit from the remaining number.
So in short, an interesting divisibility rule is the divisibility by 87, where you would need to subtract 26 times the last digit from the remaining number.
For a number with three digits or fewer, you can take 4 times the hundreds digit, add 3 times the tens digit, and subtract the ones digit.
Proof: this is equivalent to taking 104 times the hundreds digit, adding 13 times the tens digit, and subtracting the original number; 104 and 14 are both multiples of 13.
I hate computers so much
The tests involving multiplying by 4 are too big to do on one hand, since 4×9 is too big to fit on one hand. There's a divisibility test by 7 which is multiply by 3, add the next digit, and reduce mod 7. That might overflow a hand if you reduce mod 7 by lifting three adjacent fingers that are down, but usually it doesn't.
When I get a number down to three digits, I can tell by inspection whether it's divisible by 13. 143 is obviously 11×13, and 213 can't be divisible by 13 because there's a 13 in it, and the rest is 2.
I've used another one for 13... I'd say it's a bit easier than Rule 3. Just multiply the last digit by 9 and subtract from the remaining digits, and you get a congruent number mod 13.
This is essentially similar to rule 2, starting from 90 = -1 (mod 13) instead of 40 = 1 (mod 13), but it will work for both 7 and 13 since 91=7*13.
A few rules:
7: Last 2 digits, add to (rest * 2)
11: Last 2 digits, add to rest
17: Last 2 digits, subtract from (rest * 2)
19: Last 2 digits, add to (rest * 5)
23: Last 2 digits, add to (rest * 8) tho this one seems kinda complicated
A little simpler for 23: Last 2 digits, (rest / 3 + last2) * 3
29: Last digit, (rest / 3 + last)*3
31: Last digit, (rest / 3 - last)*3
Fun fact: 1001 = 7.11.13, so the first divisibility rule also provides a test for divisibility by 7 (and somewhat less usefully, 11)
Mad divisibility test, #1: 101 is prime, so there's an alternating 2-digit test for divisibility by 101: e.g., 67771 = 71-77+6 = 0, and low and behold, 67771 = 671 x 101
1001 is not prime, giving a few (perhaps) more useful divisibility tests
10001 is not prime, either. 10001 = 73 x 137, so we have an alternating 4-digit sum test for divisibility by 73 and 137
For what values of n is 1...n zeros....1 prime?
lo and behold
So, when is 10^n + 1 prime?
If n is odd it is divisible by 11 (alternating sum divisibility rule).
If n is not a power of 2, so that n=m*2^k, where m>1 is odd, then 10^n + 1 = x^m + 1 where x=10^(2^k). But this is divisible by (x+1) = 10^(2^k) + 1. E.g. for 10^6 + 1, m=3, k=1 and it is divisible by 101. For 10^20 + 1, m=5, k=2 then (x+1) = 10^4 + 1 = 10001 divides our number.
The only possible primes are if n is a power of 2. This is a necessary but not a sufficient condition.
@@michaelguenther7105 Excellent response! Thanks for taking the trouble to write it
You can solve the equation y''+3xy'+2x^2y=0. It has an exact solution.
16:20
Expression for rule 1 at 9:14 is incorrect and because of this expression at 10:12 has minus sign for the last term.
Our number is a_3n*10^(3n-1)+a_(3n-1)*10^(3n-2)+a_(3n-2)*10^(3n-3)+⋯+a_6*10^5+a_5*10^4+a_4*10^3+a_3*10^2+a_2*10^1+a_1*10^0
We can combine this sum in the following way: (a_3n*10^2+a_(3n-1)*10^1+a_(3n-2) )*10^(3n-3)+⋯+(a_6*10^2+a_5*10^1+a_4 )*10^3+(a_3*10^2+a_2*10^1+a_1 )*10^0
Every statement inside parenthesis is actually a 3-digit number: (a_3n a_(3n-1) a_(3n-2) ) ̅*10^(3n-3)+⋯+(a_6 a_5 a_4 ) ̅*10^3+(a_3 a_2 a_1 ) ̅*10^0
And now we apply our congruence rule 10^3n≡(-1)^n: (a_3n a_(3n-1) a_(3n-2) ) ̅*(-1)^(n-1)+⋯+(a_6 a_5 a_4 ) ̅*(-1)^1+(a_3 a_2 a_1 ) ̅*(-1)^0
Clearly, (-1)^1 is simply -1 and (-1)^0 is 1.
I prefer my version more 😂
To test the divisibility by any number, reduce your number by a known multiple of this number.
4219358
306358
6058
52
26
So you don't need complicated multiplications, additions or subtractions.
Bravo! I've used this technique many times!