A Clock Formula That Detects if a Number is Prime
Вставка
- Опубліковано 28 вер 2024
- It's a new year, but there are still a few more months in Grade -1. In this episode, I'll use clocks to explain an interesting formula that can test whether any number is prime or composite. Special thanks to my Patreon supporters at / comboclass (top tier supporters are listed in this video's credits and all supporters are listed below)
After you watch this video, check out my bonus video about shortcuts for testing prime numbers if you were doing it yourself with a calculator: • How Square Roots Can H...
Special thanks to: Tybie Fitzhugh, Henry Spencer, Mitch Harding, YbabFlow, Plenty W, Quinn Moyer, Julius 420, Philip Rogers, Ilmori Fajt, Brandon, August Taub, Ira Sanborn, Matthew Chudleigh, Cornelis Van Der Bent, Craig Butz, Mark S, Thorbjorn M H, Mathias Ermatinger, Edward Clarke, and Christopher Masto, Joshua S, Max, Joost Doesberg, Adam, Chris Reisenbichler, and Stan Seibert.
Disclaimer: Do not copy any physical actions you see in Combo Class episodes, including any use of fire, tools, or other science experiments.
COMBO CLASS LINKS:
Patreon: / comboclass
Bonus channel: / @domotro
Reddit: / comboclass
Discord: / discord
Some topics mentioned in this video include: prime numbers, factorials, clocks, modular arithmetic congruences, divisibility/remainders, Wilson’s theorem, Wilson primes, and more.
Stay tuned for next episode, which is a more casual science break where I do some bubble experiments and the rain makes my classroom flood.
If you're reading this, leave a comment about clocks.
Thanks for watching! Make sure to check out these Combo Class links:
Patreon: www.patreon.com/comboclass
Bonus channel: www.youtube.com/@domotro
Reddit: www.reddit.com/r/comboClass/
Discord: discord.gg/cHHvDcPPuc
🎶 #thank_you
"it aint gonna rain"
.
I love the deranged lore you're building alongside doing actual math lecturing
Did you feel me looking at your profile or something?
I’d never thought about a lot of these things, but they are intuitive if you spend time with them. Any square number larger than 4 is guaranteed to be included in the factorial test, because 2p < p^2 IFF p>2. It’s simple but just looking at how 3!(mod4) being congruent to 2 throws off the pattern is kinda confusing at first. You need to really become familiar with how intimate factors and factorials are. Yes I know factor is literally in the name but I don’t think a lot of people connect the dots unless they play with the numbers
Nice! You should consider doing a video on p-adic numbers.
Yeah I'll probably make a vid (or few) about p-adic numbers sometime in Grade -2. Also, for all the other viewers requesting the "base 2i" episode I promised, don't worry, that'll be coming in just a few episodes/weeks!
@@ComboClass shouldn't that be grade 0? because grade -2 is actually lower than grade -1
@@brighthades5968 Nah Grade 0 is rare footage/tales from my past which I haven't shared much of here yet. After Grade -1 is Grade -2 because we're going deeper / further. Also to people wondering if it'll go to Grade 1, I bet you already did 1st Grade in normal school haha
@@Domotro thanks for clarifying, I thought that grade 0 was being uneducated xD
Yo I saw a video on p-adic numbers, would be nice to see combo class's take on them
Someone: "Math is orderly"
Domotro: *Watch me*
I love the chaotic theme of episodes more than anything else!
Just wondering if the brackets around the "mod n" are necessary? Seems like they shouldn't be, but I did appreciate them for some reason. It just feels right. Like when you take logs to a particular base.
They are necessary, the result of the calculation is some large number, that when modified my n is the same as 0 modified by n.
Without modifying by n, it's not equal to zero, and doesn't prove anything.
Also in practical uses of the method, you calculate everything mod n. Why? It doesn't influence the result, but you only need 2 times the storage space needed to store n to store the whole calculation, instead of potentially millions, or billions of times as much space.
Any day Domotro uploads is a good day. Happy new year!
Is it computationally really that expensive? I think you should be able to multiply 2 adjacent numbers and take the remainder of the product. And then repeat this with the results. So in theory, you just need N multiplications and N remainders where the coefficients are always less than N and the dividend always less than N^2
It is quite efficient, actually, because if you calculate it with modular arithmetic you can use N-1 operations with integers from 0 to N-1 to check if it's prime!
Computers are ridiculously fast when working with integers instead of floats, doubles etc. and when you limit the size of the integers to N, it makes it even faster still!
Here's the operations you need: Multiplying 1 to N-1 is N-2 operations, the additon of 1 makes it N-1, (you add 1 to make all primes 0 mod N and all composites something else) and you're done!
If you have 0 at the end, you have a prime. If you have anything else, composite. (Even in the case of 4).
@@nbboxhead3866 Given that 101! (3 digits) is in the order of 10^159 (ie 160 digits) this "Clock formula" is not only less reliable but even more computationally expensive than Eratosthenes sieve. Doing math on more than 10 decimal digit integers cannot be done "ridiculously fast" without purpose build hardware because 160 decimal digits requires up to 540 bits, and thus a (circa) 640bit ALU shift register to do the final multiplications in a couple of instruction cycles rather than hundreds or thousands. All this just to test the lowest order 3 digit decimal (101). That is why this formula remains a mathematical amusement, rather than anything more serious. If you think about it carefully you will observe that this formula is actually the most computationally expensive calculation method, Both Trail division and Eratosthenes sieve exclude composites from subsequent calculations, whereas this Clock formula takes an axiomatic approach that does not take advantage of higher order logic. Because most people do not understand axiomatic methods they can easily be mistaken for advanced techniques, whereas the opposite is the case. Axiomatic methods were required to finally prove Fermat's Last Theorum and this video touches on the very same areas of Modular Theory and Elliptic Curves used by Andrew Wiles, so there is nothing wrong with axiomatic methods as such. The Clock formula is still worth knowing.
lol imagine being the only comment not to get domotro's heart sticker
@@MarcusAndersonsBlog theoretically, for all I know you are correct that Trail division and Eratosthenes sieve are computationally quicker and less expensive, because you only need to check the numbers up to a square root. But you are not correct that you need to work with that many digits. In fact, the modular method is incredibly efficient for RAM memory. Because you only need to remember 3 integers:
- var current_result = 1
- var iteration = 1
- const is_this_prime = 101
@@MarcusAndersonsBlog
define function 🤔(last_result, iteration){
if(iteration == is_this_prime){
return
}else{
🤔(last_result * iteration % is_this_prime, iteration + 1)
}
Me: hes gonna talk about what i used on my final exam today for that one congruence verification problem.
Him: on 11 and 7 the position lands one position counterclockwise to the 0
Me: i knew it.
this guy's videos are chaotic good in the best possible way
Feels like at the end of Grade -2 you will reveal the simple prime numbers formula that tells which next number will be a prime for any given number. 😅
love your videos!!! thanks for making math so interesting!
There are not many notifications that get me watching maths at 3am U.K. time but I make an exception for Combo Class. Another brilliant video 👍
Thanks
Thiis makes me wonder whether or not it's possible to somehow rearange that formula for n to generate prime numbers. Although, I have some idea on how you could do inverse factorial, I don't know how inverse mod would even work. Great video, it was very cool. My favourite video from grade -1 so far would have to be tied between the roots of unity one and the prime signature one.
There actually is a prime generating formula based on Wilson’s Theorem, called Willans’ formula! Look at Wikipedia’s “Formula for Primes” page, the formula is actually so interesting! There’s a really well-made UA-cam video about the formula by Eric Rowland, which I would highly recommend.
Trying to reverse modulo just results in an infinite set of possible answers. For instance, if x%10=1 (assuming x is positive), then x can be 1, 11, 21, 31, 41, 51, and so on. It's impossible to solve for something that gets pigeonholed like that.
nice video but this doesnt seem practical
it would take less computing power just to find prime numbers the normal way
(checking if its divisible by prime numbers before it)
light work
when is grade 0
Grade 0 will not happen here, grade -2 is next.
@@nbboxhead3866 ah
9th
I have seen all your videos and I am pleased to see such a nice work of you sir. I am a humble student of prime numbers,
wilson theorem states that p = 1 is prime (0! = 1 mod 1 = -1, lol, just take one more -1 over the 0, it lands on -1 like it should)
raabe integral approximation of the ln gamma function to get the factorial exactly, not calculating in-between values, at any precision
infinite converging series expansion representation of the exact factorial ln-gamma function
not the non-converging version, the raabe version
why is factorial of 0, as 0!, defined as 1, its clearly 0 or 0*1=0.
even factorials all have the "1" (one) component, in it, even if it does not matter over 2+ factorials, as a multiplicative composite
Don't let anyone tell you that math is a neat and tidy discipline
There should be an easier way to compute this via analogue systems
Man you’re low key the best math channel on UA-cam. Everyone should see your vids
The absolute chaos he creates around him, combined with his interesting subjects is something I highly appreciate. My wife asked why I was laughing out loud so much while watching the video with my earbuds in. Thank you for making me laugh so much and learn something at the same time.
Given that 101! (3 digits) is in the order of 10^159 (ie 160 digits) this "Clock formula" is not only less reliable but even more computationally expensive than Eratosthenes sieve. Doing math on more than 10 decimal digit integers cannot be done "ridiculously fast" without purpose build hardware because 160 decimal digits requires up to 540 bits, and thus a (circa) 640bit ALU shift register to do the final multiplications in a couple of instruction cycles rather than hundreds or thousands. All this just to test the lowest order 3 digit decimal (101). That is why this formula remains a mathematical amusement, rather than anything more serious. If you think about it carefully you will observe that this formula is actually the most computationally expensive calculation method, Both Trail division and Eratosthenes sieve exclude composites from subsequent calculations, whereas this Clock formula takes an axiomatic approach that does not take advantage of higher order logic. Because most people do not understand axiomatic methods they can easily be mistaken for advanced techniques, whereas the opposite is the case. Axiomatic methods were required to finally prove Fermat's Last Theorum and this video touches on the very same areas of Modular Theory and Elliptic Curves used by Andrew Wiles, so there is nothing wrong with axiomatic methods as such. The Clock formula is still worth knowing.
The thing that makes it good is you can both pick a random number to test, and use only n - 1 +-*/ operations in modular arithmetic mod n: n - 2 operations in the factorial and also 1 addition, and then 0 means prime, anything else is composite.
I hope you're familiar with modular arithmetic, I'll show an example of what I mean with n = 7.
In this case, if 1 * 2 * 3 * 4 * 5 * 6 + 1 is congruent to 0 when mod 7, (6 operations and 1 comparison) then 7 is prime.
Did you fall on purpose? I haven't laughed that hard in a while.
These videos are gold!
After you watch this video, check out my bonus video about shortcuts for testing prime numbers if you were doing it yourself with a calculator: ua-cam.com/video/dl7LLYw-xbQ/v-deo.html
OMG(factorial)... yet another amazing vid(factorial)(factorial)
Around 13:05 you say "factorials are big, so it would take a lot of computational power," but the reason that Wilson's Theorem is computationally inefficient is a bit more complex than that. It is true that simply taking (n - 1)! and seeing what that is mod n takes a lot of computation because (n - 1)! is enormous for even modestly large n. But one might think there's a way around that problem using the fact that mods "play nice" with arithmetic.
Specifically, since (ab) mod n = (a mod n)(b mod n), we could try the following algorithm:
let prod = 1
for k in [2, 3, ..., n - 1]:
prod = prod * k
prod = prod mod n
if prod == n -1 then n is prime
else n is composite
And technically, that algorithm works. It will tell you if n is prime or composite (for n > 1), and the computation never sees a number bigger than about n squared, so there's no issue with factorials being really big. But there's a new problem: this algorithm is strictly worse than naively checking if n has factors other than 1. Consider the naive prime algorithm:
for k in [2, 3, ..., sqrt(n)]: (technically, it should be either floor or ceiling of square root of n, but I can never remember which so let's say ceiling to be safe)
if n mod k == 0, then n is composite; stop
if we haven't already found n to be composite, then n is prime
The naive algorithm involves doing some modular division roughly square root of n times, and if n is anything other than a prime or square of a prime, the algorithm will actually get cut off early, saving some computation. The algorithm using Wilson's Theorem, on the other hand, involves doing some multiplication and some modular division n - 2 times. But we could actually make a better algorithm based on Wilson's Theorem. If the modular division ever results in 0, then it will continue to do so for the rest of the calculations, so we can just stop there knowing that it will not be congruent to n - 1 at the end. The improved version looks like this:
let prod = 1
for k in [2, 3, ..., n - 1]:
prod = prod * k
prod = prod mod n
if prod == 0 then n is composite; stop
if prod == n -1 then n is prime
else n is composite
And we can do slightly better by making special case for 4:
if n == 4 then n is composite; stop
let prod = 1
for k in [2, 3, ..., n - 1]:
prod = prod * k
prod = prod mod n
if prod == 0 then n is composite; stop
if we haven't already found n to be composite, then n is prime
For composite n, this version will stop at least as early as when k is half of n, since prod becomes 0 when k is equal to n divided by the smallest prime factor of n. So we only have to loop up to about half of n when n is composite, and if we don't hit 0 by that point we can cut it off early and say n is prime:
if n == 4 then n is composite; stop
let prod = 1
for k in [2, 3, ..., ceiling(n / 2)]:
prod = prod * k
prod = prod mod n
if prod == 0 then n is composite; stop
if we haven't already found n to be composite, then n is prime
But even with the optimizations we've done so far, it takes roughly n/2 multiplications and as many modular divisions to find out that n is prime, whereas the naive algorithm only required roughly the square root of n modular divisions. So the best version of the algorithm using Wilson's Theorem I can produce is still much worse than the naive algorithm, which is also a horrible algorithm for finding primes. *But*, as I said at the beginning, the reason Wilson's Theorem is bad for finding primes is more complex than the fact that (n - 1)! is huge. (I think we could still improve this by going from both ends at once and having each loop consider k equal to the lowest number that hasn't been k yet and j equal to the largest candidate factor that hasn't been j yet, but that will still not improve by much.)
I am not a big math guy😅, but i saw some of your shorts…., and liked many of them…. But this math is kind of too complicated for me…, so while at the 11 minute mark, 11 minutes half fulled of confusion, i am leaving the video…., but great work, appreciate it 👍
Calculating the entire factorial is not needed in order to check whether the number is prime or not. Because we only need the answer in modular arithmetic, we can apply the modulo operator at each step in order to keep the numbers low.
Please help me in my endeavour to explain this to the rest of the comment section. Also, you only need n - 1 operations mod n as well. Neat!
You had to just casually sneak in that we were getting close to grade -2
A comment about clocks
A reply about clocks
@@fantiscious A recursive reply about clocks
Okay but why take the factorial of n-1 and not n/2 (rounded down) the entire point is the mod of that number will be =0 if the factorial is divisible by the number, so if you divide the number by 2 you’ll still have all of the possible divisors of the number in the factorial which guarantees that if it’s composite it will still be 0 mod n. It also uses quite a bit less computing power so it only seems reasonable to divide by 2 instead of simply subtracting 1.
I've tried it manually with 22 (and counted down), and it worked until i came to 9. - 4! mod 9 = 24 mod 9 = 6. Even 5! mod 9 = 3. 6 Finally zerofied it.
Update: i've tested it up to 200 and it works. It probably doesn't work with 9 because it is too small of a number (similar how the 4 didn't work in this video). If you want some examples, i've made a google sheet (it has a formula and examples up to 125)
docs.google.com/spreadsheets/d/1CcA5IJ9gmSPeftA9Z9O9BwD5hrvCQXzzzmtEC7RsBVY/edit#gid=0
@@otakarbeinhauer Why is 9 too small?
@@Anonymous-df8it because there is only one 3 factor in 5! and for something to be divisible by 9 there has to be two 3 factors.
@@otakarbeinhauer Why isn't this a problem for numbers greater than 9?
What grade do we graduate into after we finish -1?
Grade -2
@@ComboClass So getting dumber?!
Great blend of chaos and order
nice
I hate that UA-cam doesn’t show Combo Class on my notifications. I’m subscribed, wth?!
i love your lessons but i wish there were 1/3rd the amount of 'hahah whoops clumsy' moments
Demasiado complicado. Necesitamos algo más sencillo
My handwriting looks so similar to yours, but I'm a lefty 😂
I wonder when grade - imagination starts 🤣
An interesting fact that I discovered which is probably trivial to everyone else is that, based upon the fact that (p-1)! is congruent to -1 mod p, and that p-1 is congruent to -1 mod p, when we divide (p-1)! by p-1, we get (p-2)!, which is guaranteed to be congruent to 1 mod p. (p-2)! is congruent to 1 mod p!!! Weird
yeah, you are right. Be careful with the triple exclamation mark though :D might mean different things
@@otakarbeinhauer oh I was just testing you, I totally meant to do that 😅😉
@@otakarbeinhauer I almost did the same... luckily I avoided it xD
Why do you love clocks ?
are you disastrous?
Why so awesome
Cool.
I love your antique setup as it's quite nostalgic!! I WANT TO VISIT IT SO BADLY 😅!!!
Very cool! As soon as you said "clock-like" algorithm, I knew we were going modular 😊 Has anyone proved whether 7! is the last factorial in the list of super-duper-whatsit composite numbers?
Yeah it can be proven that further factorials are not highly composite :)
@@ComboClassVery cool! Thanks for the info :D
Absolutely wonder sir!. I love the old saying that when a physicist breaks new ground, they find a mathematician has already been there, just for kicks, messing around with clocks probably
Combo Class: Unlike a stopped clock, we're right more than twice a day!
For checking if 101 is prime, wouldn't it almost be less computationally intensive to try to divide it by 2 through 50? Great videos btw
For a N, you need only to check for 2 and then for odd K less that sqrt(N) (assuming you don't know all primes below sqrt(N)), because if N=AB and A>sqrt(N), then B
On a basic computer or calculator, you wouldn't use this video's method, it's more of a beautiful mathematical relationship than a practical computation technique. I'm going to also be posting a demonstration about a simpler (but less elegant) way to check primes on my bonus channel www.youtube.com/@domotro later today
No 2-11
hi!
@1:01 I shouted "Wilson Primes!" at my TV, which my cats responded to with what I can only assume to be amazement and pride hidden beneath the indifferent looks they both gave me. I knew this because I am merely a dirty, nerdy Numberphile viewer. This absolutely didn't detract from my enjoyment of the episode--Domotro goes into much more detail and makes interesting connections with other parts of maths. Loving the channel!
Thank you for the prime detector, I've needed one of these. I now have it put into python.
@@garywilliams9689 Really? I mean for really large numbers, but it can do smaller numbers really quickly. Is there a better one?
@@evenaxin3628 just calculate everything while mod n and you only need the storage capacity to store n squared.
@Gary Williams no it's not that bad, it only needs n - 1 operations to calculate the answer, you can pick any number you want, and if you calculate while mod n, storage problems fade away.
Great video again! Maybe make a video about derivatives/integrals for complex graphs in more than two dimensions (say x's turn into complex y's), it seems very funky and weird. Derivatives might be able to apply to some complex graphs, where the slope, at any/most points on the graph would be another complex number, creating a different-looking graph. So integrals might be possible here too, since they're technically just the opposite of derivatives. I believe these are possible, whether its a 1-dimensional line in a 3-dimensional or even 4-dimensional complex space, or a 2-dimensional sheet-looking graph.
Stay safe Dimotro! The comedic effect of the totally not careful transition to the porch is very much present, but we dont want you ending up in the hospital!
I have a friend who is destructive and chaotic, and narrowly puts up with my love of primes. I sent them this video and said this, and they told me that you even looked like a fusion of the two of us. You aren't us from the future after we learned the fusion dance, are you?
neato, Domotro, I'dn't've thought of clocks as being akin to modular arithmetic, but that's an interesting concept
I didn't know about Wilson's Theorem before watching this, (maybe Willson's, idk if I can trust youtube captions for this one) but I knew the formula's applications and was trying to figure it out myself, and it was a nice surprise that you mentioned it!
One thing that could be done to make the method more efficient is to calculate the factorial mod n, but you probably already know it, but it turns prime testing from factorization to n-1 basic +-*/ operations while mod n, which is very useful and neat! (n-2 multiplications, add 1 and then if you have 0 you have a prime, anything else is not 0)
I ended up having to edit the number of operations 2 times... hope that's it...
(Also sorry about not doing stuff with my digit-in-any-base formula, I'm easing into publicizing my findings currently)
Domotro, I discovered an interesting pattern.
99^2 = 9,801. If you add the first two digits of the answer and the square root of the last two digits of the answer (98+1), you get 99. I tested this for other numbers as well. 98^2 = 9,604 (96+2=98), 97^2 = 9,409 (94+3), etc. Surprisingly, this works for numbers with a different number of digits as well. Let's take 3 digits. 999^2 = 998,001 (998+1), 998^2 = 996,004 (996+2), 997^2 = 994,009 (994+3). You get the point. You might argue that at one point, this doesn't work. For example, 90^2 = 8100 but 81+0 isn't 90. This is because for the second number, the limit is only 99 and if it passes that, it does not work. However, if you rewrite it as 8000 + 100, we can do 80 + 10, which equals 90. Let's take the simplest case, which is 1 digit, and see if it works out for all 1 digit numbers
9^2 = 81, 8 + sqrt(1) = 9
8^2 = 64, 6 + sqrt(4) = 8
7^2 = 49, 4 + sqrt(9) = 7
6^2 = 36 (second number crosses 10). We can rewrite this as 20 + 16. 2 + sqrt(16) = 6
5^2 = 25. We can rewrite this as 0 + 25. sqrt(25) = 5. This is similar to the cases for numbers 1-4.
So basically, x^2 can be written as a + b, and the sum of the first half of the digits of 'a' plus the square root of 'b' equals x in at least one case. I think that this is true for every number (I might be wrong tho). Idk why this happens but it does. I just discovered it. It probably has been discovered before, but it is always nice to find things out on your own.
And if x is an integer that is 6 or more, then 'a' doesn't have to be 0
The a=0 cases (which are kinda boring) are only required for numbers 1-5, for numbers 6 or more we can actually get some interesting cases like 998^2 = 996000 + 4.
Yeah nvm this doesn't work for 101^2. 101^2 = 10201 and I haven't found a way in which I can write it in a + b = x form where a is not equal to 0 and the first half of the digits of a plus the square root of b equals x. Maybe there is one in the negative numbers, but I haven't found it yet.
It probably just doesn't work if the answer has an odd number of digits cuz you can't really take half the digits of a 5 digit number, for example. I guess that the answer HAS to have an even number of digits.
Sounds cool, I’ll look into that sometime!
cool
I did not know that. Very useful and interesting.