You need a full jury to conclude a number is a prime, whereas even just one dissenter will show the number is composite. This implies that primes are guilty and composites are innocent. This makes sense, because we usually assume numbers are composite until proven prime.
You forgot to mention how ugly prime numbers are. We all know that 13 and 17 cannot even compare with the beauty and structure such as 36 and 100. The worst are those large primes like 101 or 83. WHY CAN'T THEY GROW UP LIKE EVERYONE ELSE? THEY LACK SOPHISTICATION AND ARE A SHAME TO THIS WORLD. AND DON'T CLAIM IT'S BECAUSE OF THE WAY THEY ARE TREATED. IT'S THE NATURE OF THEIR EXISTENCE THAT IS THE PROBLEM. WHY ARE THEY CALLED PRIME WHEN THEY ARE USELESS, SINFUL REINCARNATIONS OF THE DEVIL HIMSELF.
@@ivarangquist9184 True mathematical beauty lies in the primes. Any composite order you cherish seems boring and daft in comparison to the primes' unruly yet reliable nature.
I first learned about this when I took a class taught by Prof. Rabin, who called it the "randomized primality test" because he was too humble to tell us it was named after him, which made it a bit hard to find references to what he was talking about in our textbook or online
@@will1603 i mean it was a class taught in my school's CS department while i was working towards a CS degree there. maybe math students or something would've also been welcome (i don't remember, it was a long time ago), but it wasn't like totally something completely, um, randomized
11:53 "Over 8 times as far" must of course be referring to a 'Parker 8', which we can therefore infer is some value less than 6.6103. We learn so much from Matt!
At one point (7:02) he also said that 18 is just below a quarter of 90 - and I was like "WTF, 90/18=5, Matt surely knows that", but, just like with what you wrote, in this case it must have been a Parker quarter. Okay, hold up. I've just watched it again to find the timestamp and he said "quarter" because 25% is the worst-case scenario for the ratio of liars.
Previous statements I made were incorrect, due to hasty coding. I am very confident in the following results: For 2 < n < 100, n is odd, the top 5 naughtiest numbers are the following: 38, with 4 offences 8, with 3 offences 18, with 3 offences 34, with 3 offences 47, with 3 offences For 2 < n < 1000, n is odd, the top 5 naughtiest numbers are the following: 64, with 16 offences 68, with 15 offences 118, with 14 offences 307, with 14 offences 274, with 13 offences For 2 < n < 10000, n is odd, the top 5 naughtiest numbers are the following: 512, with 68 offences 64, with 66 offences 256, with 59 offences 1451, with 58 offences 254, with 57 offences There seems some justification that powers of two are particularly naughty.
The results are symmetrical, so the witness "a" always gives the same results as witness (n-a), so the 18 liars for 91 are actually: 1,9,10,12,16,17,22,29,38,(91-38),(91-29),(91-22),(91-17),(91-16),(91-12),(91-10),(91-9),(91-1) You can also use witnesses a>n without problems, but the result for a, a+n, a+2n, a+3n ... etc. will be the same.
@@Falanwe Yeah I know, I forgot to mention that. I just added them in the list because they were shown in the video for the 91 case. You should also never use n, 2n, 3n, ... etc as witness, they will always show composite even for primes. So basically (2 to n-2), (n+2 to 2n-2), (2n+2 to 3n-2), ... etc. are ok, but the results for each range are identical, but it is useful to use a>n if you have a huge a that works for a lot of n. For example the 2 witnesses a=336781006125 or a=9639812373923155 will work for n
The funny thing is, that meme became popular when a RUclips video of the clip went viral. That clip was uploaded by the user Tibees, who ended up becoming a math RUclipsr. It's full circle.
If anyone is interested, this is how you'd implement it in c# public static int Pow2(int x, int y, int z) { int number = 1; for(int i = 0; i < y; i++) { number = number * x % z; } return number; }
This is basically a generalization of the Fermat primality test, where you just test if a^(n-1) = 1 (mod n); if it isn't, then it's definitely composite, but if it is, then it's only probably prime. Except, for the Fermat test, there are "Carmichael numbers" for which every witness is a liar; the first three are 561, 1105, and 1729. So the real innovation of the Miller-Rabin test is being able to prove that at most 25% of its witnesses are liars, enabling an effective probabilistic test.
I'm a little bit curious whether 1662803 has any particular properties that makes it more likely to be honest, or if it's just a pure numerical coincidence that it happens to cover up the holes of the other three numbers over that range.
Wow. I'm studying computer science. I just found this exact thing in a footnote of one of my scripts (discrete mathematics). We were looking at groups, modular arithmetic and primes to understand RSA public-key encryption . This is just checking weather 1 is the greatest common divisor of a and n. If you check all possible dividers you will know wether it's prime. Well that and some awesome aspects of mathematics that keep computation feasible. We used it because a gcd of 1 is necessary for it to have an inverse in the groups we were using, breaking group axioms, so we'd either have to exclude them or just use a prime which had non of them (except for 0 which is equal to n). Damn this feels amazing understanding the math behind this.
This reminds me of bloom filters and their cousins, the xor and fuse filters. They are constructed from a set of numbers (hashes, usuallly) but they use far fewer bits than the set and can tell you if a number isn't in the set faster than you could search the set. You can control how often they lie about it being in the set by the size of the filter in relation to the size of the set. Since these filters are just big integers, there should be naturally occurring filters for every possible set somewhere in the natural numbers.
@@Embermeetstimber Maybe, but if you think about it too much, you will be relieved when an infinite troupe of monkeys shows up at your door wanting to talk to you about the script for Hamlet they've worked out.
If the set of witnesses are the first n primes, what is the largest number that can be conclusively confirmed or rejected as prime, as a function of n? The examples Matt showed makes me think it might be exponential or double exponential.
matt, that calculator has a FACT button on it. ttype the number, hit equals, then shift+(the degrees button) and it prints out the prime decomposition of the number
I programmed my TI-84 CE to factor any number under 2.52 million in November 2020. :) Why that number? Cos the device runs out of memory beyond 2.5 million. I even came up with an estimated calculation time (3 minutes for factoring the largest numbers). Have you ever programmed your calculator Matthew in TI Basic?
@@ZedaZ80 Yes, the calculator in the video was a Casio. I used to own a Casio a long time ago, but sadly most textbooks here in the US require Texas Instruments. :( At least I can program it.
"Minimizing the mistakes, not eradicating but cutting back" (1:50) is henceforth known as the Parker Method. The Parker Method gave us the Parker Square.
@@volodymyrgandzhuk361 Ah, lay off. Ever since the Parker Square plenty of almost correct things have been labelled as Parker solutions and Matt's in on the joke. He is a stand-up comic you know
16:45 Matt being super happy about 747 appearing, looking up at the camera all enthusiastic, and then realizing nobody in the room shares his level of number geekhood. This is me about 5 times every day. 🤣
May I just interject a comment, please? I just adore Numberphile Matt and this channel. It is always fascinating beyond words, and exceptionally educational. Bravo, Numberphile! Superb content!
8:29 This kind of thing is how you know it's Parker. In truth, only the first modular comparison is allowed to yield a remainder of +1 for a primality verdict. If the first test is not +-1 and a later test is +1, a is a witness to n.
With the way you explained the algorithm, the strongest liars would be 1 and (n-1). They lie for ALL non-primes. Which is exactly why the correct algorithm excludes them from the list of possible candidates
@@Anonymous-df8it Well, 1 will always stay 1, no matter to which power you raise it. And (n-1) mod n is the same as -1, so it will be either 1 or -1 (mod n) when you raise it to any positive power. Those are exactly the "probably prime" results the algorithm is looking for, so using those will result in a false positive every time.
@@Anonymous-df8it I have not tried to find that out yet, but some others in the comments have listed their results. Though the last time I checked only up to 100.000. You probably need a lot of calculations to go higher since you have to check n-3 numbers every time. So the algorithms time increases quadratically...
so I did the math and from all the odd numbers from 7 to 25326001 I found that: 2 give false testimony to 255 numbers 3 give false testimony to 314 numbers 5 give false testimony to 280 numbers
Interestingly I can’t seem to find anything breaking down what the “strongest liars” are. My intuitive guess is the smaller the number the better the chance it lies so 2 might be the strongest, but I’m curious to see an answer to that question Matt had at the end.
@@keithbromley6070 star witnesses are only reliable if you query the whole group - it could be that 2 only covers 3's weaknesses but lies all the other times. Just a possibility, no idea if it's true but saying you can be a star witness and a frequent liar!
Though not quite the same, one probabilistic primality test I like is the Fermat primality test - it's kind of like a worse version of the Miller-Rabin primality test. It builds on Fermat's Little Theorem and states that if a^(p - 1) ≡ 1 (mod p) with 1 < a < p - 1, then p is probably prime. And if the congruence doesn't hold for a given a, then p is composite. However, there is a class of numbers where ALL coprimes of a between 1 and p - 1 are congruent to 1 (mod p) even though p is composite. These are known as Carmichael Numbers, and the smallest is 561 = 3 * 11 * 17. Indeed, the test only fails if a is set to one of its factors (which you can trivially divide p by to confirm it's compositeness).
The witness is providing an alibi for the number m. If m has an alibi (i.e., mod =1), he's not the thief (not prime). Not having an alibi doesn't make m the thief, call another witness to the stand.
His upset sigh when he was told right away that 747 is indeed not prime… It’s a relatable feeling. Today I was counting primes from 1000 out of boredom, until I got to above 2000 and said “why not”. Sad that 2023 isn’t prime, but 2027 is, so we still have a few more years to go.
Judge : 4 was found guilty and is sentenced to become a part of Collartz Conjecture loop. Lawyer : But almost all of the witnesses says 4 isn't guilty! Judge : But 1662803, 23, 13, and 2 said that he is guilty!
What i like most about Brady's style of interviewing is, that it is on such a personal level. Also for example when he says "Brilliant, they are great people"
Are these star numbers found by checking every number up to the limit and seeing that they do not lie for any or is there a proof that gives this limit without having to check? I'm assuming the former but would be cool to know.
The way the test is described in the video, it fails for Fermat primes like 257. When you subtract 1 and take out the 2s from what's left, the d value just becomes 1, so very few witnesses will yield a remainder of +-1 even though the test number is prime. It also fails for primes lying above multiples of large powers of 2, such as 193, where d becomes 3. For instance, with a witness of 3, of course its cube (27) is not +-1 (mod 193), so the supplemental task starting at 8:08 is necessary rather than optional.
Question: when using the “star witness” approach, which is more, start testing with the lower numbers first, the higher numbers first, or is there no difference?
Off the top of my head, I wouldn't be surprised to see the strongest liar change as you test higher and higher numbers. For example: testing liars for all numbers up to 1001, you can't have 1001 having witnessed yet. But it could, by the time you've tested up to a million, be the strongest liar.
At 13:05, the number is mispronounced. The first digit is a trillion, not a quadrillion, because Matt skipped billions and went straight from trillions to millions.
So extrapolating from the groups, just take the first k primes to get to 2^f(k) for some function f? Or has this be disproven? How does this algorithm compare to other ways to test for primes in efficiency?
I tried writing is myself and I am stuck on 673. 673 is 2^5*21+1 FIRST WITNESS: 2 2 ^ 21 mod 673 is 84 -> not a prime. But 673 is a prime number ... Did I miss something?
Same thing with the prime number 149 (picked randomly). If we test with a=2 or even a=23, they say it's not a prime because we don't get 1 or -1 mod 149. I suspect the rule given in the video is a Parker rule.
I don't get it as well. 37 = 2 ^ 2 x 9 + 1 2 ^ 9 mod 37 = 512 mod 37 = 31 => not prime but 37 is prime... Edit: Ok, the part at 8:00 is important 2 ^ (9 * 2^0) mod 37 = 512 mod 37 = 31 => not prime 2 ^ (9 * 2^1) mod 37 = 262 144 mod 37 = 36 => prime
Also, for smaller numbers (like, 91), you can call over 1/4 of all witnesses (like, a half); and, if all of them say it’s prime, it’s definitely prime. Of course, it won’t work for bigger numbers (like, a trillion); so, for those, you’d better call up the star witnesses.
The 4^-k probability of falsely declaring a number prime is a very pessimistic one as the number being tested gets bigger and the number of witnesses increases. And if you're worried, then iterate for 25 or 50 different witnesses. It's a sufficiently fast algorithm that you can afford to do that even for RSA-sized primes - 800 decimal digits or so - if you don't mind waiting a few milliseconds. Also, you can tweak Miller-Rabin to sometimes get a prime factor out of a number in addition to proving its compositeness.
Apparently around 4 or 5 random tests is sufficient. 1/4 liars is an upper bound and when dealing with cryptographic sized numbers it's actually far less. So in practice my intuition to do like you say k of 50 or 100 is no needed at all. Although your choices must be random.
This looks very similar to Fermat's Little Theorem, I can't remember whether Numberphile's ever done a video on the topic but some other channels definitely have (I'd recommend Mathologer's)
Something that wasn’t said in the video is that there’s a number that’s trivially always a strong liar if the number isn’t prime: 1, because 1 to the power of anything is 1, which is congruent to 1 modulo anything. 1 is the kind of witness who just wants to get out of the courtroom ASAP, so it’ll accuse anyone on the stand and leave.
Well first of Mersenne numbers have their own primality test which only works for them and is much more efficient than this one. Also 2 is a liar for all Marsenne Numbers (and all Fermat Numbers), using this test with 2 will same Prime for all Marsenne Numbers, whether prime or composite
You need a full jury to conclude a number is a prime, whereas even just one dissenter will show the number is composite. This implies that primes are guilty and composites are innocent. This makes sense, because we usually assume numbers are composite until proven prime.
Elegant.
But the star witnesses you have to call in are the most notorious primes. It takes a hardened criminal to rat out their fellow criminals.
You forgot to mention how ugly prime numbers are. We all know that 13 and 17 cannot even compare with the beauty and structure such as 36 and 100. The worst are those large primes like 101 or 83. WHY CAN'T THEY GROW UP LIKE EVERYONE ELSE? THEY LACK SOPHISTICATION AND ARE A SHAME TO THIS WORLD. AND DON'T CLAIM IT'S BECAUSE OF THE WAY THEY ARE TREATED. IT'S THE NATURE OF THEIR EXISTENCE THAT IS THE PROBLEM. WHY ARE THEY CALLED PRIME WHEN THEY ARE USELESS, SINFUL REINCARNATIONS OF THE DEVIL HIMSELF.
@@ivarangquist9184
I see that the spirit of Pythagoras lives well & strong inside you, my child
@@ivarangquist9184 True mathematical beauty lies in the primes.
Any composite order you cherish seems boring and daft in comparison to the primes' unruly yet reliable nature.
"Well I happen to know, below 91 there are 90 numbers"
The things I learn from Numberphile are priceless.
*negative numbers and zero*: "Are we a joke to you?"
@@raphaelschmitz-dumont4426 The rationals: "Are we a joke to you?"
@@OrangeC7 The irrationals: "Are we a joke to you?"
@@timallgood4108 the complex:" hey look over there!"
@@Ludwig-MariaAKern-yz2vs unfortunately, the complex are neither below nor over 90, afaik.
I first learned about this when I took a class taught by Prof. Rabin, who called it the "randomized primality test" because he was too humble to tell us it was named after him, which made it a bit hard to find references to what he was talking about in our textbook or online
Thats cool
That is COOOOOOOOOLLLL
Taught by the one who made it XD
I love how in america you can just choose to take a class. One of the few things from America id like in theuk
@@will1603 i mean it was a class taught in my school's CS department while i was working towards a CS degree there. maybe math students or something would've also been welcome (i don't remember, it was a long time ago), but it wasn't like totally something completely, um, randomized
"Witness, is this number prime?"
"Yes!"
"Objection, your honour. We have evidence that this witness is a strong liar."
"Sustained."
A Parker witness, you might say.
@@qovro uh oh
he gave it a go, but wasn't quite right.
Oh no
SUS
There is a lot of character in this video, well done to both of you.
New to numberphile, eh? 😄
Yeah, really made me invested in the plot of this crime drama.
welcome to the wonderful world of matt parker
@@toolebukk he is punning around...
@@katowo6521 berbahasa indonesia
11:53 "Over 8 times as far" must of course be referring to a 'Parker 8', which we can therefore infer is some value less than 6.6103.
We learn so much from Matt!
At one point (7:02) he also said that 18 is just below a quarter of 90 - and I was like "WTF, 90/18=5, Matt surely knows that", but, just like with what you wrote, in this case it must have been a Parker quarter.
Okay, hold up. I've just watched it again to find the timestamp and he said "quarter" because 25% is the worst-case scenario for the ratio of liars.
Similar to the 'Parker Quadrillion' at 12:49 eh?
false.
13:03 Matt's about 3 orders of magnitude off; it's 1 trillion and 122 billion. That's a real Parker Quadrillion if I've ever seen one
Gotta have at least one per video
The billion is sus.
I'm pretty sure he puts them in intentionally, like his book
Could be the British Vs American definition.
@@markinnes4264 No-one uses the Long-count any more in mathematics
Previous statements I made were incorrect, due to hasty coding. I am very confident in the following results:
For 2 < n < 100, n is odd, the top 5 naughtiest numbers are the following:
38, with 4 offences
8, with 3 offences
18, with 3 offences
34, with 3 offences
47, with 3 offences
For 2 < n < 1000, n is odd, the top 5 naughtiest numbers are the following:
64, with 16 offences
68, with 15 offences
118, with 14 offences
307, with 14 offences
274, with 13 offences
For 2 < n < 10000, n is odd, the top 5 naughtiest numbers are the following:
512, with 68 offences
64, with 66 offences
256, with 59 offences
1451, with 58 offences
254, with 57 offences
There seems some justification that powers of two are particularly naughty.
Can't wait for the next video on N*ughty Numbers
I wonder if it's because they're a power of 2. Who was second and third for each test respectively?
81 seems naughty for all natural up to thousands.
I think it's interesting that these are powers of two. Thanks for this!
I wonder if this is an actual patten and if that's been proven already... 🤔
I love how the numbers changed from witnesses to detectives to cops to juries as the video progressed XD
Yeah, the story did seem somewhat judicially confused...
That's OK though, it makes for really interesting worldbuilding.
Spoiler alert : one of them is the killer.....
Detectives and cops can be witnesses, no? The only real jump was to jury.
Matt liked the numbers so much, that he kept promoting them.
Absolutely admire the strength of Parker to not make a “Prime Suspect” joke in the whole video haha
I love these little anthropomorphisations of numbers and the stories of their relations :)
I prefer onomatopoeic anthropomorphisations
Ooh I'd love it if they got together with ViHart and did a story series of different number types. The only question left is what should they call it?
Hmmm
I'm ALWAYS team anthro! In fact, I dislike strongly when anybody tries to stop me from anthroing for a bit of spice.
Love your pfp
The results are symmetrical, so the witness "a" always gives the same results as witness (n-a), so the 18 liars for 91 are actually:
1,9,10,12,16,17,22,29,38,(91-38),(91-29),(91-22),(91-17),(91-16),(91-12),(91-10),(91-9),(91-1)
You can also use witnesses a>n without problems, but the result for a, a+n, a+2n, a+3n ... etc. will be the same.
Coolio
Cool, so if I wanted to figure out all liars for any given number I'd only have to check halfway.
You should never call 1 and n-1 as witnesses: they will always tell you n is prime.
@@Falanwe Yeah I know, I forgot to mention that. I just added them in the list because they were shown in the video for the 91 case. You should also never use n, 2n, 3n, ... etc as witness, they will always show composite even for primes. So basically (2 to n-2), (n+2 to 2n-2), (2n+2 to 3n-2), ... etc. are ok, but the results for each range are identical, but it is useful to use a>n if you have a huge a that works for a lot of n.
For example the 2 witnesses a=336781006125 or a=9639812373923155 will work for n
@@Einyen Thanks for the information. You rock.
It's like they say: Don't do the crime if you can't prove you're prime.
Awesome one! 🤣🤣🤣
This comment is on fire 🔥
@@samuelvilz then get some water
I had a lecturer who would pronounce "prime" as "crime"
false.
* ponts at 747 *
"we're assuming this is odd"
One of the boldest assumptions a mathematician has ever said
The 747 airplane is kinda odd. It has a hump like a giant metal sky whale. It is my favorite mainstream aircraft though. :)
@@thatguyalex2835 The hump is why I love the old Antonov's.
It's a Parker conjecture.
@@SwervingLemon I like both models of planes. Are you talking about the AN-225?
I was waiting for this for about 500years!
😆 well look who it is!
Is the comment to the video too small to put proof in?
@@volodyadykun6490 Unfortunately, yes.
Time Lord!
Pierre! How’s it hangin? How’s the dirt nap? Did you dream of Bernhard Riemann?
Makes sense that the primes are the most apt witnesses for telling if another number is prime or not.
It takes one to know one
They see each other at the various prime meetings and functions.
??
When I heard "In the future, entertainment will be randomly generated." I didn't think numbers would be this entertaining.
Numbers can lie- I mean
WEED EATER
i mean, is entertainment not randomly generated anyway?
Wait youre the chess guy
The funny thing is, that meme became popular when a RUclips video of the clip went viral. That clip was uploaded by the user Tibees, who ended up becoming a math RUclipsr. It's full circle.
Same
Python's pow function takes an optional mod argument, making this test easy to program. For instance, pow(23, 373, 747) = 131.
Huh, did not know that!
How sensible for anyone programming any cryptographic stuff.
I think I'm going to have to start solving my project euler problems in python due to this lol
If anyone is interested, this is how you'd implement it in c#
public static int Pow2(int x, int y, int z)
{
int number = 1;
for(int i = 0; i < y; i++)
{
number = number * x % z;
}
return number;
}
@@1992jamo Try:
while (y > 0) {
if (y & 1) number = number * x % z;
x = x * x % z;
y >>= 1;
}
instead.
Matt Parker and James Grime, really the two stars you need on the 10th anniversary of Numberphile
Don't forget Cliff Stoll!
And Hannah Fry!
Neil (what was his surname again... the OEIS founder) and Ben Sparks are also people I like to see in these videos!
This is basically a generalization of the Fermat primality test, where you just test if a^(n-1) = 1 (mod n); if it isn't, then it's definitely composite, but if it is, then it's only probably prime. Except, for the Fermat test, there are "Carmichael numbers" for which every witness is a liar; the first three are 561, 1105, and 1729. So the real innovation of the Miller-Rabin test is being able to prove that at most 25% of its witnesses are liars, enabling an effective probabilistic test.
Fun that Ramanujan's Number is in there
I'm a little bit curious whether 1662803 has any particular properties that makes it more likely to be honest, or if it's just a pure numerical coincidence that it happens to cover up the holes of the other three numbers over that range.
Well 1662803 is prime and 1662804 is very composite.
Why am I not suprised that you'd be thinking about something like that :D But it's definetly interesting
Pretty sure "happens to cover up the holes of the other three numbers over that range"
@@DukeBG my guess as well
They were just raised not to be a liar.
Wow. I'm studying computer science. I just found this exact thing in a footnote of one of my scripts (discrete mathematics). We were looking at groups, modular arithmetic and primes to understand RSA public-key encryption
. This is just checking weather 1 is the greatest common divisor of a and n. If you check all possible dividers you will know wether it's prime. Well that and some awesome aspects of mathematics that keep computation feasible. We used it because a gcd of 1 is necessary for it to have an inverse in the groups we were using, breaking group axioms, so we'd either have to exclude them or just use a prime which had non of them (except for 0 which is equal to n). Damn this feels amazing understanding the math behind this.
"The numbers don't lie." - "Well actually they do!"
13:03 that’s a blunder if I’ve ever seen one, classic Matt Parker move.
11:50 Another blunder
This reminds me of bloom filters and their cousins, the xor and fuse filters. They are constructed from a set of numbers (hashes, usuallly) but they use far fewer bits than the set and can tell you if a number isn't in the set faster than you could search the set. You can control how often they lie about it being in the set by the size of the filter in relation to the size of the set. Since these filters are just big integers, there should be naturally occurring filters for every possible set somewhere in the natural numbers.
Sounds very Miller-Rabin-y.
@@Embermeetstimber Maybe, but if you think about it too much, you will be relieved when an infinite troupe of monkeys shows up at your door wanting to talk to you about the script for Hamlet they've worked out.
??
This is the maths video with the most plot twists I've ever seen
"747 has been charged with homicide and vehicular manslaughter and will be serving 747 years in prison"
This is great, I had learnt Miller Rabin test in my Cryptography class, but not so clearly with these Witness numbers.
If the set of witnesses are the first n primes, what is the largest number that can be conclusively confirmed or rejected as prime, as a function of n? The examples Matt showed makes me think it might be exponential or double exponential.
that sounds pretty interesting
I saw 91 and something in my brain immediately said “it’s 70 plus 21 so 7 times 13”
matt, that calculator has a FACT button on it. ttype the number, hit equals, then shift+(the degrees button) and it prints out the prime decomposition of the number
I programmed my TI-84 CE to factor any number under 2.52 million in November 2020. :) Why that number? Cos the device runs out of memory beyond 2.5 million. I even came up with an estimated calculation time (3 minutes for factoring the largest numbers).
Have you ever programmed your calculator Matthew in TI Basic?
@@thatguyalex2835 So you're saying it can do FACTs and Logic?
@@thatguyalex2835 friend, that's a Casio
@@U014B Nope. :) It can't. It is not a Casio.
@@ZedaZ80 Yes, the calculator in the video was a Casio. I used to own a Casio a long time ago, but sadly most textbooks here in the US require Texas Instruments. :( At least I can program it.
"2, forget about 3, 13, 23, and the team captain; 1,662,803."
That had me dying because I was not expecting the last number to be so f*cking large.
"Minimizing the mistakes, not eradicating but cutting back" (1:50) is henceforth known as the Parker Method. The Parker Method gave us the Parker Square.
Liar numbers should be called “perjurious numbers”! 😂
Because, if there's one things mathematicians like, it's giving catchy names to numbers.
18/90 is the new Parker approximation for 1/4
He said AT MOST 1/4 of the numbers are liars
@@volodymyrgandzhuk361 Ah, lay off. Ever since the Parker Square plenty of almost correct things have been labelled as Parker solutions and Matt's in on the joke. He is a stand-up comic you know
@@volodymyrgandzhuk361 So let's hope for him that there are no composite numbers n = p*q*r where each of the prime number q, and r divide (n-1)/2.
Professor: The test isn’t even that hard
The test:
Question 1: Guess the next number in the following sequence:
2, 13, 23, …?
687. That's my guess. Therefore I've done what you asked. Full marks, please!
“I happen to know that below 91 there are 90 numbers”. Excellent
This comment is definitely perfect
16:45 Matt being super happy about 747 appearing, looking up at the camera all enthusiastic, and then realizing nobody in the room shares his level of number geekhood. This is me about 5 times every day. 🤣
you meant 14:14 ?
never call 1 to the stand, it always gives 1
May I just interject a comment, please? I just adore Numberphile Matt and this channel. It is always fascinating beyond words, and exceptionally educational. Bravo, Numberphile! Superb content!
You two really had a lot of fun in this episode. Well done!
Your Quadrillion is missing 3 digits.
Ooh. Actually throwing in the "Dun Dun"
I feel like some aggressive content ID would try to claim the whole video over those .5 seconds
Hi Verlis didn’t expect to see you here lol
I know this is unrelated to your comment but can I say how cool your profile picture looks?
It looks really nice.
I think it's insufficient for a legal claim.
@@Qermaq
The bots aren’t smart enough to know that
@@executeorder6613 Yeah but the bots aren't asked to match stuff like this.
8:29 This kind of thing is how you know it's Parker. In truth, only the first modular comparison is allowed to yield a remainder of +1 for a primality verdict. If the first test is not +-1 and a later test is +1, a is a witness to n.
With the way you explained the algorithm, the strongest liars would be 1 and (n-1). They lie for ALL non-primes. Which is exactly why the correct algorithm excludes them from the list of possible candidates
Proof?
@@Anonymous-df8it Well, 1 will always stay 1, no matter to which power you raise it. And (n-1) mod n is the same as -1, so it will be either 1 or -1 (mod n) when you raise it to any positive power. Those are exactly the "probably prime" results the algorithm is looking for, so using those will result in a false positive every time.
@@holgerchristiansen4003 What would be the next strongest liars?
@@Anonymous-df8it I have not tried to find that out yet, but some others in the comments have listed their results. Though the last time I checked only up to 100.000. You probably need a lot of calculations to go higher since you have to check n-3 numbers every time. So the algorithms time increases quadratically...
@@holgerchristiansen4003 Why quadratically? Wouldn't that make it run exponentially with the number of digits?
13:06 the number jumps from trillions to millions, I want justice for my boys the billions digit
so I did the math and from all the odd numbers from 7 to 25326001 I found that:
2 give false testimony to 255 numbers
3 give false testimony to 314 numbers
5 give false testimony to 280 numbers
I loved this video and love matt parker. Great
One of the best numberphile videos I have seen!! Well done to both of you.
I gotta agree; it’s pretty cool to be able to infer primality or compositness without actually doing any division!
Interestingly I can’t seem to find anything breaking down what the “strongest liars” are. My intuitive guess is the smaller the number the better the chance it lies so 2 might be the strongest, but I’m curious to see an answer to that question Matt had at the end.
That makes sense.. it would seem 2 would lie half the time. This is just my guess, though.
2 is the best witness yet the strongest liar lol
Surely not 2? It was part of all the star witness groups! Perhaps the lowest non-prime? Dastardly number 4.
@@keithbromley6070 star witnesses are only reliable if you query the whole group - it could be that 2 only covers 3's weaknesses but lies all the other times. Just a possibility, no idea if it's true but saying you can be a star witness and a frequent liar!
@@AdamHill42 I guess I don’t understand it enough to be sure either way!
THANK YOU for finally covering Miller Rabin! I've always been fascinated with this particular primality test due to how incredibly simple it seems.
Having not looked into the numbers most prone to lying, my first instinct would be that it'd likely be related to the highly composite numbers.
That's a very Parker Prime Number test!
I love the 12 Angry Men reference.
Though not quite the same, one probabilistic primality test I like is the Fermat primality test - it's kind of like a worse version of the Miller-Rabin primality test. It builds on Fermat's Little Theorem and states that if a^(p - 1) ≡ 1 (mod p) with 1 < a < p - 1, then p is probably prime. And if the congruence doesn't hold for a given a, then p is composite.
However, there is a class of numbers where ALL coprimes of a between 1 and p - 1 are congruent to 1 (mod p) even though p is composite. These are known as Carmichael Numbers, and the smallest is 561 = 3 * 11 * 17. Indeed, the test only fails if a is set to one of its factors (which you can trivially divide p by to confirm it's compositeness).
A Numberphile Classic!
14:17 “There you are! - That's putting a little *_boe_* on this figure, isn't it?...”
The witness is providing an alibi for the number m. If m has an alibi (i.e., mod =1), he's not the thief (not prime). Not having an alibi doesn't make m the thief, call another witness to the stand.
*mod ≠ ±1
His upset sigh when he was told right away that 747 is indeed not prime… It’s a relatable feeling.
Today I was counting primes from 1000 out of boredom, until I got to above 2000 and said “why not”. Sad that 2023 isn’t prime, but 2027 is, so we still have a few more years to go.
Judge : 4 was found guilty and is sentenced to become a part of Collartz Conjecture loop.
Lawyer : But almost all of the witnesses says 4 isn't guilty!
Judge : But 1662803, 23, 13, and 2 said that he is guilty!
What i like most about Brady's style of interviewing is, that it is on such a personal level. Also for example when he says "Brilliant, they are great people"
Are these star numbers found by checking every number up to the limit and seeing that they do not lie for any or is there a proof that gives this limit without having to check? I'm assuming the former but would be cool to know.
”10^45 is gonna be a very big number.” Yeah, it is. Heptilliard, to be precise :D.
Quddarodecillion
@@windowsuranusSP5 I’m doing ”the long system”, a.k.a. *_THE_* System.
Such a cool concept. Those unreliable witnesses...🤣
9:55 ”If they *_COSINE”_* 🙃
advanced congrats 4mil subs numberfile!
12:45 The better the witness, the bigger the price tag.
Excellent video, funny, interesting, well edited. 10/10.
This video made me so happy. It is so much fun
You know what does this video and the fed balance sheet have in common?
Billions are missing
The way the test is described in the video, it fails for Fermat primes like 257. When you subtract 1 and take out the 2s from what's left, the d value just becomes 1, so very few witnesses will yield a remainder of +-1 even though the test number is prime.
It also fails for primes lying above multiples of large powers of 2, such as 193, where d becomes 3. For instance, with a witness of 3, of course its cube (27) is not +-1 (mod 193), so the supplemental task starting at 8:08 is necessary rather than optional.
cant wait for the parker square numbers
Amazing video! Informative and thoroughly entertaining as well
Question: when using the “star witness” approach, which is more, start testing with the lower numbers first, the higher numbers first, or is there no difference?
Lawyer by trade, numberphile by hobby. This is SO up my alley.
Hey Numberphile I love the channel. Is there a chance you could do a video on celestial navigation?
Classic Parker Trillion! 3 orders of magnitude more than a Trillion... The Parker Trillion 🤣🤣🤣
That's a nice Casio, Matt. Can we get a review?!
The fact that all these large numbers feel so random is what makes this so interesting tbh lol
Off the top of my head, I wouldn't be surprised to see the strongest liar change as you test higher and higher numbers. For example: testing liars for all numbers up to 1001, you can't have 1001 having witnessed yet. But it could, by the time you've tested up to a million, be the strongest liar.
Well, 1 is the strongest liar of all, because 1^a = 1 (mod n) for any numbers a and n.
At 13:05, the number is mispronounced. The first digit is a trillion, not a quadrillion, because Matt skipped billions and went straight from trillions to millions.
So extrapolating from the groups, just take the first k primes to get to 2^f(k) for some function f? Or has this be disproven? How does this algorithm compare to other ways to test for primes in efficiency?
i'd like to congratulate the opening line for articulating why i was clicking on the video, even as i struggled to put my finger on it
I tried writing is myself and I am stuck on 673.
673 is 2^5*21+1
FIRST WITNESS: 2
2 ^ 21 mod 673 is 84 -> not a prime.
But 673 is a prime number ... Did I miss something?
(2^21) * (2 ^ 3) mod 673 = -1
We can multiply with 2^r where 0 < r < s.
From 8:00, you can pull 2's off the first part. 2^21 mod 673 doesn't work, but 2^168 mod 673 [168 is 21*2*2*2] is -1.
Same thing with the prime number 149 (picked randomly). If we test with a=2 or even a=23, they say it's not a prime because we don't get 1 or -1 mod 149.
I suspect the rule given in the video is a Parker rule.
@@adamsbja correct, I wish they did 17 as an example of why the power of 2 multiplication is important.
I don't get it as well.
37 = 2 ^ 2 x 9 + 1
2 ^ 9 mod 37 = 512 mod 37 = 31 => not prime
but 37 is prime...
Edit:
Ok, the part at 8:00 is important
2 ^ (9 * 2^0) mod 37 = 512 mod 37 = 31 => not prime
2 ^ (9 * 2^1) mod 37 = 262 144 mod 37 = 36 => prime
Also, for smaller numbers (like, 91), you can call over 1/4 of all witnesses (like, a half); and, if all of them say it’s prime, it’s definitely prime. Of course, it won’t work for bigger numbers (like, a trillion); so, for those, you’d better call up the star witnesses.
The 4^-k probability of falsely declaring a number prime is a very pessimistic one as the number being tested gets bigger and the number of witnesses increases. And if you're worried, then iterate for 25 or 50 different witnesses. It's a sufficiently fast algorithm that you can afford to do that even for RSA-sized primes - 800 decimal digits or so - if you don't mind waiting a few milliseconds. Also, you can tweak Miller-Rabin to sometimes get a prime factor out of a number in addition to proving its compositeness.
Apparently around 4 or 5 random tests is sufficient. 1/4 liars is an upper bound and when dealing with cryptographic sized numbers it's actually far less. So in practice my intuition to do like you say k of 50 or 100 is no needed at all. Although your choices must be random.
As soon as I saw the title I knew this would be the Miller-Rabin test; I just happened to be working with it last week
is it a coicidence that all the star witnessses are prime as well? or at least the smaller ones seem to be
Watching this at 7:47pm😂
1 is perfectly unreliable, given that 1^d = 1 mod n for all n
M.C Escher print on the wall! Nice!
The primes are the best witnesses because they know who's in their crime family
1,662,803 - the Dirty Harry of witnesses x)
This is super cool and interesting, but I'm left to wonder why in the heck it works like it does.
This looks very similar to Fermat's Little Theorem, I can't remember whether Numberphile's ever done a video on the topic but some other channels definitely have (I'd recommend Mathologer's)
@@alexpotts6520 Numberphile does have a video on this topic called "Liar Numbers".
Super fun video! I loved it when you skipped the billions at 13:00 xD
"They get the job done!"
Something that wasn’t said in the video is that there’s a number that’s trivially always a strong liar if the number isn’t prime: 1, because 1 to the power of anything is 1, which is congruent to 1 modulo anything. 1 is the kind of witness who just wants to get out of the courtroom ASAP, so it’ll accuse anyone on the stand and leave.
"I'm gonna cheat and ask WolframAlpha"
Oh look, it's me doing my practice paper for each maths class every week 😂
Can you guys see whats so hard about Mersenne primes? I have this sneaky feeling twin primes and Mersenne primes are some strange bedfellows.
Well first of Mersenne numbers have their own primality test which only works for them and is much more efficient than this one. Also 2 is a liar for all Marsenne Numbers (and all Fermat Numbers), using this test with 2 will same Prime for all Marsenne Numbers, whether prime or composite
Methinks that a cool name for the witness numbers 31 and 73 would be "[the] Dirty Harry numbers"