Witness Numbers (and the truthful 1,662,803) - Numberphile

Подписаться 4,5 млн

Просмотров 425 тыс.

50% 1

Featuring Matt Parker - more Parker links below.
Check out Brilliant (get 20% off their premium service): brilliant.org/numberphile (sponsor)
More links & stuff in full description below ↓↓↓
MATT PARKER STUFF
Stand-Ups Maths on RU-vid: / standupmaths
Matt's website: standupmaths.com
Matt's Books (Amazon): amzn.to/3absFfV
Matt's playlist on Numberphile: bit.ly/Matt_Videos
Parker Square Merch: numberphile.creator-spring.co...
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from the Akamai Foundation: www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Patreon: / numberphile
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9

Наука

Опубликовано:

27 ноя 2021

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 985

@TheJVBlackbelt 2 года назад

"Well I happen to know, below 91 there are 90 numbers" The things I learn from Numberphile are priceless.

@raphaelschmitz-dumont4426 2 года назад

*negative numbers and zero*: "Are we a joke to you?"

@OrangeC7 2 года назад

@@raphaelschmitz-dumont4426 The rationals: "Are we a joke to you?"

@timallgood4108 2 года назад

@@OrangeC7 The irrationals: "Are we a joke to you?"

@Ludwig-MariaAKern-yz2vs 2 года назад

@@timallgood4108 the complex:" hey look over there!"

@theantimatter 2 года назад

@@Ludwig-MariaAKern-yz2vs unfortunately, the complex are neither below nor over 90, afaik.

@RibusPQR 2 года назад

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.

@451Duke 2 года назад

Elegant.

@vigilantcosmicpenguin8721 2 года назад

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.

@ivarangquist9184 2 года назад

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.

@nicholasleclerc1583 2 года назад

@@ivarangquist9184 I see that the spirit of Pythagoras lives well & strong inside you, my child

@xCorvus7x 2 года назад

@@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.

@mlcastle 2 года назад

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

@aleksapetrovic7088 2 года назад

Thats cool

@truebark3329 2 года назад

That is COOOOOOOOOLLLL

@JLo_24 2 года назад

Taught by the one who made it XD

@will1603 2 года назад

I love how in america you can just choose to take a class. One of the few things from America id like in theuk

@mlcastle 2 года назад

@@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

@NardiPaffon 2 года назад

55,648 is the 50,000th composite number. I ran the script for each number between 2 to 55,648. Runtime: ~27 minutes on my machine. The numbers which turned up to be false-witnesses the most times were: (The number, how many times found lying) (2401, 183) (625, 182) (6561, 173) (529, 166) (81, 164) (729, 152) (4096, 149) (4225, 126) (3481, 125) (256, 123) Nice to see that these biggest liars are all (almost) powers of primes: 2401 =7 ^ 4 625 =5 ^ 4 6561 =3 ^ 8 529 =23 ^ 2 81 =3 ^ 4 729 =3 ^ 6 4096 =2 ^ 12 4225 =65 ^ 2

@ytkerfuffles6429 Год назад

thats so cool. i wonder why that is.

@talastra 7 месяцев назад

They are all perfect squares: 49^2, 25^2, 81^2, 23^2, 9^2, 27^2, 64^2, 65^2, 59^2, 16^2 ... also, taking powers of 4 rather than perfect squares, there is 3,4,5,7,8,9 (6 is missing; did 1296 not quite make the cut)? Meanwhile, 23, 59 and 65 seem quite random relative to the others. If I was to try to screw around with it, I would notice that 65 is 23*3-1, I would note that 59 = 23 + 36, and 65 = 23 + 42. I'm not sure this would get me anywhere :)

@ensiehsafary7633 5 месяцев назад

How you did the test with an even number

@therealelement75 2 месяца назад

@@talastra welp guess I'm not trusting squares then

@talastra 2 месяца назад

Yeah, don't trust anyone over 30@@therealelement75

@dro56789 2 года назад

"Witness, is this number prime?" "Yes!" "Objection, your honour. We have evidence that this witness is a strong liar." "Sustained."

@qovro 2 года назад

A Parker witness, you might say.

@tonymiller8244 2 года назад

@@qovro uh oh

@cossaertom 2 года назад

he gave it a go, but wasn't quite right.

@DergPH 2 года назад

Oh no

@adamqazsedc 2 года назад

SUS

@flan1591 2 года назад

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

@TabooGroundhog 2 года назад

Gotta have at least one per video

@Ojisan642 2 года назад

The billion is sus.

@blumousey 2 года назад

I'm pretty sure he puts them in intentionally, like his book

@markinnes4264 2 года назад

Could be the British Vs American definition.

@GeeItSomeLaldy 2 года назад

@@markinnes4264 No-one uses the Long-count any more in mathematics

@malice1105 2 года назад

There is a lot of character in this video, well done to both of you.

@toolebukk 2 года назад

New to numberphile, eh? 😄

@vigilantcosmicpenguin8721 2 года назад

Yeah, really made me invested in the plot of this crime drama.

@antonhengst8667 2 года назад

welcome to the wonderful world of matt parker

@proloycodes 2 года назад

@@toolebukk he is punning around...

@WakdominelwanNelwanWdm 2 года назад

@@katowo6521 berbahasa indonesia

@tomrivlin7278 2 года назад

I love how the numbers changed from witnesses to detectives to cops to juries as the video progressed XD

@hughcaldwell1034 2 года назад

Yeah, the story did seem somewhat judicially confused...

@efulmer8675 2 года назад

That's OK though, it makes for really interesting worldbuilding.

@42ArthurDent42 2 года назад

Spoiler alert : one of them is the killer.....

@dinklebob1 2 года назад

Detectives and cops can be witnesses, no? The only real jump was to jury.

@programmingpi314 2 года назад

Matt liked the numbers so much, that he kept promoting them.

@jmv333 2 года назад

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!

@Karolomen 2 года назад

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.

@benjaminshepard 2 года назад

Similar to the 'Parker Quadrillion' at 12:49 eh?

@Triantalex 5 месяцев назад

false.

@henrygreen2096 2 года назад

Absolutely admire the strength of Parker to not make a “Prime Suspect” joke in the whole video haha

@pyglik2296 2 года назад

I love these little anthropomorphisations of numbers and the stories of their relations :)

@PronatorTendon 2 года назад

I prefer onomatopoeic anthropomorphisations

@toxicara 2 года назад

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?

@DergPH 2 года назад

Hmmm

@limbridk 2 года назад

I'm ALWAYS team anthro! In fact, I dislike strongly when anybody tries to stop me from anthroing for a bit of spice.

@HypnosisBear 2 года назад

Love your pfp

@Honey-lx1ly 2 года назад

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.

@camicus-3249 2 года назад

Can't wait for the next video on N*ughty Numbers

@MySharpify 2 года назад

I wonder if it's because they're a power of 2. Who was second and third for each test respectively?

@annyone3293 2 года назад

81 seems naughty for all natural up to thousands.

@steven_porter 2 года назад

I think it's interesting that these are powers of two. Thanks for this!

@unvergebeneid 2 года назад

I wonder if this is an actual patten and if that's been proven already... 🤔

@KSignalEingang 2 года назад

It's like they say: Don't do the crime if you can't prove you're prime.

@AyatollahKhomeiniSalleh 2 года назад

Awesome one! 🤣🤣🤣

@samuelvilz 2 года назад

This comment is on fire 🔥

@asheep7797 2 года назад

@@samuelvilz then get some water

@una_10bananas 2 года назад

I had a lecturer who would pronounce "prime" as "crime"

@Triantalex 5 месяцев назад

false.

@joaquinclavijo7052 2 года назад

* ponts at 747 * "we're assuming this is odd"

@falquicao8331 2 года назад

One of the boldest assumptions a mathematician has ever said

@thatguyalex2835 2 года назад

The 747 airplane is kinda odd. It has a hump like a giant metal sky whale. It is my favorite mainstream aircraft though. :)

@SwervingLemon 2 года назад

@@thatguyalex2835 The hump is why I love the old Antonov's.

@d5uncr 2 года назад

It's a Parker conjecture.

@thatguyalex2835 2 года назад

@@SwervingLemon I like both models of planes. Are you talking about the AN-225?

@Einyen 2 года назад

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.

@adamqazsedc 2 года назад

Coolio

@hippasusofmetapontum6447 2 года назад

Cool, so if I wanted to figure out all liars for any given number I'd only have to check halfway.

@Falanwe 2 года назад

You should never call 1 and n-1 as witnesses: they will always tell you n is prime.

@Einyen 2 года назад

@@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

@Galakyllz 2 года назад

@@Einyen Thanks for the information. You rock.

@pierredefermat2559 2 года назад

I was waiting for this for about 500years!

@revenevan11 2 года назад

😆 well look who it is!

@volodyadykun6490 2 года назад

Is the comment to the video too small to put proof in?

@pierredefermat2559 2 года назад

@@volodyadykun6490 Unfortunately, yes.

@naszaalbania2576 2 года назад

Time Lord!

@brandonmarquette7476 2 года назад

Pierre! How’s it hangin? How’s the dirt nap? Did you dream of Bernhard Riemann?

@tejarex 2 года назад

Python's pow function takes an optional mod argument, making this test easy to program. For instance, pow(23, 373, 747) = 131.

@eac-ox2ly 2 года назад

Huh, did not know that!

@trueriver1950 2 года назад

How sensible for anyone programming any cryptographic stuff.

@ThePharphis 2 года назад

I think I'm going to have to start solving my project euler problems in python due to this lol

@1992jamo 2 года назад

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; }

@shoo7130 Год назад

@@1992jamo Try: while (y > 0) { if (y & 1) number = number * x % z; x = x * x % z; y >>= 1; } instead.

@LeventK 2 года назад

When I heard "In the future, entertainment will be randomly generated." I didn't think numbers would be this entertaining.

@TunaBear64 2 года назад

Numbers can lie- I mean WEED EATER

@amyshaw893 2 года назад

i mean, is entertainment not randomly generated anyway?

@abiwardani3944 2 года назад

Wait youre the chess guy

@vigilantcosmicpenguin8721 2 года назад

The funny thing is, that meme became popular when a RU-vid video of the clip went viral. That clip was uploaded by the user Tibees, who ended up becoming a math RU-vidr. It's full circle.

@DergPH 2 года назад

Same

@javik9165 2 года назад

Makes sense that the primes are the most apt witnesses for telling if another number is prime or not.

@dms1683 2 года назад

It takes one to know one

@dinklebob1 2 года назад

They see each other at the various prime meetings and functions.

@Triantalex 5 месяцев назад

@mathphysicsnerd 2 года назад

18/90 is the new Parker approximation for 1/4

@volodymyrgandzhuk361 2 года назад

He said AT MOST 1/4 of the numbers are liars

@mathphysicsnerd 2 года назад

@@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

@johannesvanderhorst9778 2 года назад

@@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.

@jamirimaj6880 2 года назад

Matt Parker and James Grime, really the two stars you need on the 10th anniversary of Numberphile

@BravoCharleses 2 года назад

Don't forget Cliff Stoll!

@UnderwurldChris 2 года назад

And Hannah Fry!

@5ucur 11 месяцев назад

Neil (what was his surname again... the OEIS founder) and Ben Sparks are also people I like to see in these videos!

@protocol6 2 года назад

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.

@soranuareane 2 года назад

Sounds very Miller-Rabin-y.

@protocol6 2 года назад

@@luxuryenby 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.

@Triantalex 5 месяцев назад

@rjginsburg 2 года назад

“I happen to know that below 91 there are 90 numbers”. Excellent

@KingLarbear 2 года назад

This comment is definitely perfect

@johnchessant3012 2 года назад

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.

@magsaysay84 7 месяцев назад

Fun that Ramanujan's Number is in there

@montrealleciester7277 2 года назад

"747 has been charged with homicide and vehicular manslaughter and will be serving 747 years in prison"

@MrCheeze 2 года назад

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.

@RecursiveTriforce 2 года назад

Well 1662803 is prime and 1662804 is very composite.

@Salan156 2 года назад

Why am I not suprised that you'd be thinking about something like that :D But it's definetly interesting

@DukeBG 2 года назад

Pretty sure "happens to cover up the holes of the other three numbers over that range"

@jamesknapp64 2 года назад

@@DukeBG my guess as well

@vigilantcosmicpenguin8721 2 года назад

They were just raised not to be a liar.

@phlogchamp 2 года назад

13:03 that’s a blunder if I’ve ever seen one, classic Matt Parker move.

@StefanReich 2 года назад

11:50 Another blunder

@JonathonV 2 года назад

Liar numbers should be called “perjurious numbers”! 😂

@vigilantcosmicpenguin8721 2 года назад

Because, if there's one things mathematicians like, it's giving catchy names to numbers.

@Quasarbooster 2 года назад

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.

@apuji7555 2 года назад

that sounds pretty interesting

@juandiaz3651 2 года назад

Professor: The test isn’t even that hard The test: Question 1: Guess the next number in the following sequence: 2, 13, 23, …?

@richjhart 2 года назад

687. That's my guess. Therefore I've done what you asked. Full marks, please!

@philipb4647 2 года назад

"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.

@amyshaw893 2 года назад

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

@thatguyalex2835 2 года назад

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?

@U014B 2 года назад

@@thatguyalex2835 So you're saying it can do FACTs and Logic?

@ZedaZ80 2 года назад

@@thatguyalex2835 friend, that's a Casio

@thatguyalex2835 2 года назад

@@U014B Nope. :) It can't. It is not a Casio.

@thatguyalex2835 2 года назад

@@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.

@OzoneTheLynx 2 года назад

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.

@TheXtrafresh 2 года назад

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. 🤣

@zoerycroft4300 2 года назад

you meant 14:14 ?

@bourbonbournvita 2 года назад

This is great, I had learnt Miller Rabin test in my Cryptography class, but not so clearly with these Witness numbers.

@copperfield42 2 года назад

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

@choco_jack7016 2 года назад

never call 1 to the stand, it always gives 1

@countduckula9977 2 года назад

I love the 12 Angry Men reference.

@PunmasterSTP 5 месяцев назад

I gotta agree; it’s pretty cool to be able to infer primality or compositness without actually doing any division!

@heisenberg_fisher2890 2 года назад

One of the best numberphile videos I have seen!! Well done to both of you.

@holgerchristiansen4003 2 года назад

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 2 года назад

Proof?

@holgerchristiansen4003 2 года назад

@@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 2 года назад

@@holgerchristiansen4003 What would be the next strongest liars?

@holgerchristiansen4003 2 года назад

@@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...

@Anonymous-df8it 2 года назад

@@holgerchristiansen4003 Why quadratically? Wouldn't that make it run exponentially with the number of digits?

@ace_falken5362 2 года назад

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.

@johannesvanderhorst9778 2 года назад

Well, 1 is the strongest liar of all, because 1^a = 1 (mod n) for any numbers a and n.

@soranuareane 2 года назад

THANK YOU for finally covering Miller Rabin! I've always been fascinated with this particular primality test due to how incredibly simple it seems.

@matrefeytontias Год назад

13:06 the number jumps from trillions to millions, I want justice for my boys the billions digit

@heaslyben 2 года назад

I loved "primey". People assume that it's a strict primality test, but actually from a non-subjective viewpoint it's more like a big ball of wibbly-wobbly primey-wimey stuff.

@jamesharmon4994 2 года назад

I love what you did there!!

@hebl47 2 года назад

You two really had a lot of fun in this episode. Well done!

@EnigmacTheFirst 9 месяцев назад

13:34 “Just go through every single number.” Easier said than done.

@markiangooley 2 года назад

I saw 91 and something in my brain immediately said “it’s 70 plus 21 so 7 times 13”

@ringoferrer2343 2 года назад

advanced congrats 4mil subs numberfile!

@infinityinf1 2 года назад

A Numberphile Classic!

@SKyrim190 2 года назад

Amazing video! Informative and thoroughly entertaining as well

@KpxUrz5745 2 года назад

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!

@foodflare9870 2 года назад

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.

@Bodyknock 2 года назад

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.

@jamesharmon4994 2 года назад

That makes sense.. it would seem 2 would lie half the time. This is just my guess, though.

@hirokiendo7380 2 года назад

2 is the best witness yet the strongest liar lol

@keithbromley6070 2 года назад

Surely not 2? It was part of all the star witness groups! Perhaps the lowest non-prime? Dastardly number 4.

@AdamHill42 2 года назад

@@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!

@keithbromley6070 2 года назад

@@AdamHill42 I guess I don’t understand it enough to be sure either way!

@ishmiel21 2 года назад

This video made me so happy. It is so much fun

@nuzayerov 2 месяца назад

That's a very Parker Prime Number test!

@Verlisify 2 года назад

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

@DrGuppy-hg7xu 2 года назад

Hi Verlis didn’t expect to see you here lol

@michaelavanessian8558 2 года назад

I know this is unrelated to your comment but can I say how cool your profile picture looks? It looks really nice.

@Qermaq 2 года назад

I think it's insufficient for a legal claim.

@executeorder6613 2 года назад

@@Qermaq The bots aren’t smart enough to know that

@Qermaq 2 года назад

@@executeorder6613 Yeah but the bots aren't asked to match stuff like this.

@donaldmiller1782 2 года назад

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.

@Starwort 2 года назад

*mod ≠ ±1

@sherlock_norris 2 года назад

"The numbers don't lie." - "Well actually they do!"

@timothywhite8932 2 года назад

Hey Numberphile I love the channel. Is there a chance you could do a video on celestial navigation?

@mattasker1914 2 года назад

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.

@JavierSalcedoC 2 года назад

You know what does this video and the fed balance sheet have in common? Billions are missing

@UnrivaledLimit0500 Год назад

I loved this video and love matt parker. Great

@WaterCrane 2 года назад

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).

@PokeCastle 2 года назад

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!

@xenlol 2 года назад

cant wait for the parker square numbers

@ZacGames3 2 года назад

"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.

@PC_Simo Год назад

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.

2 года назад

Excellent video, funny, interesting, well edited. 10/10.

@MrDowntemp0 2 года назад

That's a nice Casio, Matt. Can we get a review?!

@JonSebastianF 2 года назад

14:17 “There you are! - That's putting a little *_boe_* on this figure, isn't it?...”

@YossiSirote 2 года назад

I’d Love more on this topic.

@bazyt1 2 года назад

Such a cool concept. Those unreliable witnesses...🤣

@chrisrj9871 2 года назад

You need a video about 7 and 11, and have it be sponsored by 7Eleven :D

@szymonrutyna166 2 года назад

Love this channel.

@michael_aigner 2 года назад

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"

@constantinburgi3995 2 года назад

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?

@GRBtutorials 2 года назад

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.

@shruggzdastr8-facedclown 6 месяцев назад

Methinks that a cool name for the witness numbers 31 and 73 would be "[the] Dirty Harry numbers"

@Seltyk 2 года назад

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

@davidgillies620 2 года назад

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.

@gregorymorse8423 2 года назад

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.

@UMosNyu 2 года назад

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?

@longtimenodotes2717 2 года назад

(2^21) * (2 ^ 3) mod 673 = -1 We can multiply with 2^r where 0 < r < s.

@adamsbja 2 года назад

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.

@ghislainbugnicourt3709 2 года назад

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.

@jamesknapp64 2 года назад

@@adamsbja correct, I wish they did 17 as an example of why the power of 2 multiplication is important.

@tomashrazdira1766 2 года назад

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

@PC_Simo Год назад

”10^45 is gonna be a very big number.” Yeah, it is. Heptilliard, to be precise :D.

@windowsuranusSP4 9 месяцев назад

Quddarodecillion

@PC_Simo 9 месяцев назад

@@windowsuranusSP4 I’m doing ”the long system”, a.k.a. *_THE_* System.

@jaredeudell8953 2 года назад

I didn't understand a word of this, but enjoyed it immensely.

@raedev 2 года назад

is it a coicidence that all the star witnessses are prime as well? or at least the smaller ones seem to be

@TronSAHeroXYZ 2 года назад

13:01 N< 1Trillion, 122 Billion, 4 Million, 669 Thousand, 633 Not 1 Quadrillion. Imagine if he was your banker/broker manager.

@PC_Simo Год назад

9:55 ”If they *_COSINE”_* 🙃

@agargamer6759 2 года назад

This is great!

@caderrabeth 2 года назад

This is super cool and interesting, but I'm left to wonder why in the heck it works like it does.

@alexpotts6520 2 года назад

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)

@zanti4132 2 года назад

@@alexpotts6520 Numberphile does have a video on this topic called "Liar Numbers".

@p11111 2 года назад

The primes are the best witnesses because they know who's in their crime family

@blackthedog6004 2 года назад

I really like this episode. That witness-cop description makes it really interesting(which is already interesting. A prime seeking method?)

@chrisingle5839 2 года назад

M.C Escher print on the wall! Nice!

@monkerud2108 2 года назад

Can you guys see whats so hard about Mersenne primes? I have this sneaky feeling twin primes and Mersenne primes are some strange bedfellows.

@jamesknapp64 2 года назад

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

@kjdude8765 2 года назад

When Matt talked about how large 23^373 was I was thinking: just punch it in Wolfram Alpha. Glad to see I was right.

@hexagonist23 2 года назад

...Or calculate it in python.

@Sam-ey1nn 2 года назад

Matt’s videos are always funny but this is his funniest yet. Star Witness, celebrity numbers. :)

@exponentmantissa5598 2 года назад

Your Quadrillion is missing 3 digits.

@egonmilanowski 2 года назад

I am looking forward to Legal Eagle's interpretation of this case.

@expomath9348 2 года назад

Contenu toujours intéressant et travail de grande qualité. Merci pour le partage. For non french speaker i translate : Hi how are you today. it's raining in my Paris. Thank you

@JeroenBaxexm Год назад

we need more Matt again :)

@bcullman 2 года назад

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?