Boy does this bring me back to my college days in the days beyond recall. The first task in the Fortran lab was to write a program to print all the primes that would fit in a 16-bit signed integer, i.e. up to 32,767. The grad student lab assistant's program ran faster than everyone else's because he had written an interrupt driven driver for the printer. This allowed the IBM 1130 to calculate while waiting for the printer. But mine ran faster because I knew that if a number was composite at least one of its factors was less than or equal to the square root. Pretty fundamental fact, but the look on his face was priceless as he tried to figure out how this short little program was so fast (relatively speaking).
@@random6033 Even if you take the simplest algorithm that checks if N is prime (like dividing N y everything from 2 up to N-1), if you, instead, divide by 2 up to int(sqrt(N)), it will still be a lot faster, since, for the example of 32767, needs at most about 180 checks. Now, if you do a little more work, you can, instead of checking by everything up until a number's square root, check only by the primes in this interval (there are at most 40 primes
@@random6033 @Minding My Business has summarized it well. My program printed 2 and then tested all the odd numbers starting with 3 using the sieve of Eratosthenes, "the simplest algorithm", with divisors up to int(sqrt(N)). I had also calculated that I would need less than 10 kb of space to store the prime divisors as unsigned 16 bit integers to evaluate up to 2^32. But then it was off to the next lab assignment. This was all punched into cards of course.
I love how you spend an hour explaining what prime numbers are but just zoom through the parts that actually needed explanation. Maybe skip the comedy and sketches to make up room for more explanation.
Definitely was not expecting Pritchard to be still alive, what a twist! This feels like something that could've been discovered centuries ago but wasn't; it means even though math has gotten so specialized nowadays there are still plenty of "elementary" gems still waiting to be found!
There have been older sieves, Sieve of Eratosthenes and Sieve of Sundaram to name a couple. Pritchard's is a modern optimisation on those Sieves with tradeoffs afaik.
Wow I didn't know about Pritchard's sieve. This was really interesting. I thought the sieve of Atkin was the only sieve which could theoretically run faster than the sieve of Eratosthenes, but I guess I was wrong!
I've never seen your channel before, but saw this video in my recommended, and since I occasionally enjoy watching math videos, I clicked it. But man, you come off as extremely pretentious in this video. I really hope it is done in sarcasm.
This could have been explained much more clearly honestly, when you have been working with something for a long tike all feels obvious, but here we are listening to this for the first time, tyere are many logical eductions let to the viewer, for example the reason why the wheel keeps on working after one lap, its hard if not impossible to understand things without pausing making the experience frustrating.
he explained it actually. referentially tho, so the confusion is understandable. I think this is a more advanced video actually. try mathologer, his channel is very explanatory
Neat video. I felt like it went by too fast, as I had to watch it a few times to get what's going on. Also, are you left handed? The parts where you were writing, you were writing left handed, and covering the text with your hand which made it hard to read. (I doubt this helped the "going to fast" feeling) Maybe try using more of the virtual text, or showing us the text after writing it, and just cover the parts you don't want to show with another piece of paper, revealing the next bit by moving that paper down. (I've seen teachers do this on overheads when they wanted to re-use what the wrote in previously when teaching the same course at multiple times) I guess if you want a third option, you could try using a whiteboard/chalkboard, and write bigger, so that less is covered by your had. Or trick a friend into writing it for you. Anyways, neat video, though I am curious what the proof is that shows this is the most "efficient" method of generating primes (in whatever metric it is the best).
Your definition of prime numbers is inaccurate. A prime number is a number that has 2 and only 2 factors. This is the correct definition. Number 1 is not a prime number.
This is too fast. You are introducing something like a modulo without slowing down. It's not like we can prove everything you say immediately. How can I even understand the circle thing in a video format without pausing the vid? Yeah, I will like it if you started with proofs that is already true and build upon them.
I noticed this pattern independently several years ago, but couldn't explain it so clearly. Something else that's interesting about these patterns is that, unless I'm mistaken, every wheel must always contain at least some twin primes, since at each iteration we're eliminating things which have P as a factor and P must always span at least one set of twin primes. This falls a little short of proving that there's an infinite number of twin primes, because as mentioned in the video, the wheels grow very quickly and only a small section of each wheel will appear in the final prime sequence... However, I can't see a way to prevent that small visible section from periodically containing some of the twin primes that remain in the wheel.
0:49 I find it too much of a coincidence that both you and Graenolf (don't ask me why I'd remember this) both picked a random number that ends in 86, 286 and 7186 respectively. Now the number 7 is statistically the most commonly chosen number between 1 and 10 (Numberphile among others have stated this). I don't know why 86 should be the most commonly picked 2 digit number, but I'll say a few things: Given what we know about 7 there are clearly preferences. I believe when picking a two digit number you wouldn't want to choose extremes like 0, 1 and 9 or even the middleground 5, as your two digit number would be imbalanced. That leaves two sets {2, 3, 4} and {6, 7, 8} which you'd intuitevuly construct as 'small' and 'big'. If you pick a number from both sets you are likely to go for the middleground of both to get nice representation, so something like 73. If you pick a single set you probably prefer the 'big' set to make your number stand out (this is why I said 73 and not 37), maybe the 7 sticks out too much as the middle of the pack, maybe you decide to go for a bigger number and start with an 8 but not the biggest, somehow you end up at 86. To reiterate 0, 1, 5 and 9 shouldn't appear, you want a bigger number to be distinct, you pick 73 or 86. I swear this is not a coincidence.
Ah I'm pleased to have found a name for this. I'd worked out a similar method, but considering it as sliding windows on the number line rather than wheels. Window starts at the last found prime as is of primorial width.
here is a secret from a prime bro to a prime bro..for something to be something or not to be something there need to be a choice or a distinction ,2 is a prime only because it had no other choice!!! but to be a prime...also they left out part of prime definition...number is a prime when its only divisible by 1 and itself AND when there is atleast 1 other natural number inbetween 1 and itself,2 comes immediately after 1 and it didnt have enough time to choose!! :)))))
My dear boy, your fascination for the primes and your good intention to explore them in this video are praiseworthy...but sorry to say, your presentation is too technical and hard to comprehend. You'd do well to use more of graphics and animations along with a somewhat slower paced narration, to make your math videos more appealing to lay audience like me (who are also intrigued by these weird creatures called prime numbers!😂). God bless🙌
There’s another fun property to this sieve method, and that is that the numbers relatively prime to the primordial are all symmetrical along the length. For example, in the case of 30, you have [1 (-29), 7 (-23), 11 (-19), 13 (-17) …] mod 30. Another fun property is that you can use larger circles of the sieve to predict what primes have the highest likelihood to being a twin prime, and definitely discard certain ones from being twin primes, because the twins will maintain their positions with respect to the ones in the circle.
totalement inutile, cela revient juste à dire qu'on invente toutes les suites ax+b, avec une suite par nombre premier, et de regarder tout ce qui n'a pas a été pris par le passage de toutes les suites
"bro-terlude" is all I needed to subscribe. I needed more interesting math in my life anyway :) You sir... you are the Queen AND crown jewels of exhausting analogies. (but in all seriousness, super interesting video bromanguy, this was really neat!)
Great video! I had used the ideas up to 5:00 before to generate prime candidates that are guaranteed not to be divisible by the first k primes. Ofc, this went further than that! 4:38 You're already using p_n to refer the nth prime, so using p_k to refer to the kth primorial is confusing. Also, it's inconsistent with your earlier notation which used a subscripted capital Pi and your later notation which used a (unsubscripted) Q. Just be mindful of consistency/notation next time. Calling one thing by one name one time and by a different name another time leads to unnecessary confusion. Calling two different things by the same name also leads to unnecessary confusion. 4:45 prime p divides the primorial p_k if only if p
The proof of this solution is surprisingly simple. It may be interesting that, as you can see, the twin numbers in the form p # + - 1 ends at p = 11. The second remark is the vertical axis of symmetry of the circle. In my similar algorithm I use numerical sequences with cyclic differences. The use of wheels complicates and makes it difficult to understand the subject.
In the beginning was the Word, and the Word was with God, and the Word was God. 2He was with God in the beginning. 3Through him all things were made; without him nothing was made that has been made. (John 1:1-3)
Oh well... It is pretty obvious... Discovered this algorithm myself before youtube was a thing (saying it that way makes me feel old though) Though making wheel out of wheel is slightly more efficient than what i was doing
Also note that if you have a wheel built for factorial of p, you have p symmetries but they are not "compatible" with each other so you have to choose one to reduce the actual size of the wheel.
My favourite property is that the primorial set (that's what I called it when I first discovered this) contains numbers that are not only all coprime with each other, but are also coprime with each number (x) in the set + n * primorial_set_value. And there's more. Take any number x from the set, multiply it with each number in the set in order modulo primorial_set_value, and you will, I kid you not, get back every number in that primorial set, but each with a unique reordering. When you model the sequence as intervals, it's even more interesting. Firstly, you can clearly see that it produces an infinite seed for EVERY single prime gap from the previous primorial set (though it does not imply infinite prime gaps of any amount). This view of primes also gives you a remarkably different way of navigating and ordering potential primes. Aaand, one of my favourites ... going back to the aspect of any x,y pairing from the set modulo the primorial_set_value giving you a value from the primorial set (along with the unique shuffling behaviour) gives you a really simple method of private key encryption! I never found it faster for generating primes, but this was about 15 years ago, and written in Java in a very OO way (the JVM and most VMs are much more efficient now though).
This is coprime patterns that eventually filter out the primes as you add primes to filter. Current filters are very symmetric, even mirrored halfway betweeen periods. It's beautiful but still not efficient.
I have played with this, but more as a shifting ruler then a wheel. Good to have a different thought/method of it. Especially the cancellation of removing the smaller one from the larger one.
Unrelated question to the video topic. But how do you like the Art of Problem Solving books? I've never seen one in real life but have bought them before for nieces/nephews. Do they deliver as promised at least for those who work them? I'm not certain my money was well invested but don't know if that was down to the child, the parent or the book.
Beautiful books bro, I recognized his copy too, they are beyond insightful, and have given me an incredible amount of fun problem solving and learning moments. I would absolutely suggest reading them, but I’m a highschooler and idk if an adult would really find much use in them, I use them for primarily fun but also to study for contests
Ghandi's Recursive Formula for the next prime: Let p be an odd prime and let Q be the product of the primes less than p. In MathJax/LaTex let S=(-1/2)+\sum_{d|Q}\mu(d)/(2^d-1) where \mu is the Mobius function. Then 1
@@joseville No. The summation is over all divisors of Q, not over the prime divisors of Q. For each divisor d of Q there is a term \mu(d)/(2^d-1). If Q is the product of the first 46 primes then Q has 2^{46) divisors .
@@joseville To prove Ghandi's result, write each (2^d-1)=(2^{-d}+2^{-2d}+2^{-3d}+...). (power series). Now collect "like powers" of 2 in the expression for S. Now use the Mobius function property \sum_{d|n}\mu (d)=0 when n>1, and \mu (1)=1, to show S=\sum_{n\in K} 2^{-n}, where K is the set of all n>1 that are co-prime to Q. The smallest member of K is p, and all members of K are odd, so 2^{-p}
It's not the fastest. It's on par with the sieve of Atkin asymptotically(which pritchhard basically ripped off btw, he only made a slight change to reduce the space complexity), if anything it has higher constant factors usually speaking.
Boy does this bring me back to my college days in the days beyond recall. The first task in the Fortran lab was to write a program to print all the primes that would fit in a 16-bit signed integer, i.e. up to 32,767. The grad student lab assistant's program ran faster than everyone else's because he had written an interrupt driven driver for the printer. This allowed the IBM 1130 to calculate while waiting for the printer. But mine ran faster because I knew that if a number was composite at least one of its factors was less than or equal to the square root. Pretty fundamental fact, but the look on his face was priceless as he tried to figure out how this short little program was so fast (relatively speaking).
Do you post this on every video?
@@CARROTMOLD Nope. You?
which algorithm did you use?
@@random6033 Even if you take the simplest algorithm that checks if N is prime (like dividing N y everything from 2 up to N-1), if you, instead, divide by 2 up to int(sqrt(N)), it will still be a lot faster, since, for the example of 32767, needs at most about 180 checks.
Now, if you do a little more work, you can, instead of checking by everything up until a number's square root, check only by the primes in this interval (there are at most 40 primes
@@random6033 @Minding My Business has summarized it well. My program printed 2 and then tested all the odd numbers starting with 3 using the sieve of Eratosthenes, "the simplest algorithm", with divisors up to int(sqrt(N)). I had also calculated that I would need less than 10 kb of space to store the prime divisors as unsigned 16 bit integers to evaluate up to 2^32. But then it was off to the next lab assignment. This was all punched into cards of course.
I love how you spend an hour explaining what prime numbers are but just zoom through the parts that actually needed explanation.
Maybe skip the comedy and sketches to make up room for more explanation.
agree
@Larry Brin not at all! it was well-performed and entertaining. It can work a lot on the pacing but to call it cringey is just juvenile cynicism.
Definitely was not expecting Pritchard to be still alive, what a twist! This feels like something that could've been discovered centuries ago but wasn't; it means even though math has gotten so specialized nowadays there are still plenty of "elementary" gems still waiting to be found!
I also enjoyed this twist!
There have been older sieves, Sieve of Eratosthenes and Sieve of Sundaram to name a couple. Pritchard's is a modern optimisation on those Sieves with tradeoffs afaik.
Queen(Queen(Queen(natural science)))=prime numbers
Natural Sciences ->Mathematics -> Number Theory -> Prime Numbers
@@tejasvishrivastava5888 you for got PI
Wow I didn't know about Pritchard's sieve. This was really interesting. I thought the sieve of Atkin was the only sieve which could theoretically run faster than the sieve of Eratosthenes, but I guess I was wrong!
I've never seen your channel before, but saw this video in my recommended, and since I occasionally enjoy watching math videos, I clicked it. But man, you come off as extremely pretentious in this video. I really hope it is done in sarcasm.
This could have been explained much more clearly honestly, when you have been working with something for a long tike all feels obvious, but here we are listening to this for the first time, tyere are many logical eductions let to the viewer, for example the reason why the wheel keeps on working after one lap, its hard if not impossible to understand things without pausing making the experience frustrating.
he explained it actually. referentially tho, so the confusion is understandable. I think this is a more advanced video actually. try mathologer, his channel is very explanatory
@@raulgalets advanced or not, you still need to lay out the steps before you can walk into them
Neat video. I felt like it went by too fast, as I had to watch it a few times to get what's going on.
Also, are you left handed? The parts where you were writing, you were writing left handed, and covering the text with your hand which made it hard to read. (I doubt this helped the "going to fast" feeling) Maybe try using more of the virtual text, or showing us the text after writing it, and just cover the parts you don't want to show with another piece of paper, revealing the next bit by moving that paper down. (I've seen teachers do this on overheads when they wanted to re-use what the wrote in previously when teaching the same course at multiple times) I guess if you want a third option, you could try using a whiteboard/chalkboard, and write bigger, so that less is covered by your had. Or trick a friend into writing it for you.
Anyways, neat video, though I am curious what the proof is that shows this is the most "efficient" method of generating primes (in whatever metric it is the best).
Bro, I was thinking exactly about the same algorithm! However I didn't imagine it like wheels, rather repeated sequences.
Same!
Your definition of prime numbers is inaccurate. A prime number is a number that has 2 and only 2 factors. This is the correct definition. Number 1 is not a prime number.
This is too fast. You are introducing something like a modulo without slowing down. It's not like we can prove everything you say immediately. How can I even understand the circle thing in a video format without pausing the vid? Yeah, I will like it if you started with proofs that is already true and build upon them.
This is one of those videos I’ll have to rewatch over and over and really work through it 😭
I noticed this pattern independently several years ago, but couldn't explain it so clearly. Something else that's interesting about these patterns is that, unless I'm mistaken, every wheel must always contain at least some twin primes, since at each iteration we're eliminating things which have P as a factor and P must always span at least one set of twin primes. This falls a little short of proving that there's an infinite number of twin primes, because as mentioned in the video, the wheels grow very quickly and only a small section of each wheel will appear in the final prime sequence... However, I can't see a way to prevent that small visible section from periodically containing some of the twin primes that remain in the wheel.
Love this idea about prime DNA - never thought about it that way!
I can't believe the video was so well made! It was genuinely funny and easy to understand. Also I notice you have an aops book!
0:49 I find it too much of a coincidence that both you and Graenolf (don't ask me why I'd remember this) both picked a random number that ends in 86, 286 and 7186 respectively. Now the number 7 is statistically the most commonly chosen number between 1 and 10 (Numberphile among others have stated this). I don't know why 86 should be the most commonly picked 2 digit number, but I'll say a few things:
Given what we know about 7 there are clearly preferences. I believe when picking a two digit number you wouldn't want to choose extremes like 0, 1 and 9 or even the middleground 5, as your two digit number would be imbalanced. That leaves two sets {2, 3, 4} and {6, 7, 8} which you'd intuitevuly construct as 'small' and 'big'. If you pick a number from both sets you are likely to go for the middleground of both to get nice representation, so something like 73. If you pick a single set you probably prefer the 'big' set to make your number stand out (this is why I said 73 and not 37), maybe the 7 sticks out too much as the middle of the pack, maybe you decide to go for a bigger number and start with an 8 but not the biggest, somehow you end up at 86.
To reiterate 0, 1, 5 and 9 shouldn't appear, you want a bigger number to be distinct, you pick 73 or 86. I swear this is not a coincidence.
Aaron, as yoy like primes numbers study, than see my "Advanced Eratosthenes Sieve" in my channel about primes list.
Can you provide a link?
@@joseville In ua-cam.com/video/7ane1eJ1LTs/v-deo.html
Ah I'm pleased to have found a name for this. I'd worked out a similar method, but considering it as sliding windows on the number line rather than wheels. Window starts at the last found prime as is of primorial width.
You expect me to believe left hand proof?
Wouldn't Number Theory be more like the "Princess" of mathematics?
here is a secret from a prime bro to a prime bro..for something to be something or not to be something there need to be a choice or a distinction ,2 is a prime only because it had no other choice!!! but to be a prime...also they left out part of prime definition...number is a prime when its only divisible by 1 and itself AND when there is atleast 1 other natural number inbetween 1 and itself,2 comes immediately after 1 and it didnt have enough time to choose!! :)))))
My dear boy, your fascination for the primes and your good intention to explore them in this video are praiseworthy...but sorry to say, your presentation is too technical and hard to comprehend. You'd do well to use more of graphics and animations along with a somewhat slower paced narration, to make your math videos more appealing to lay audience like me (who are also intrigued by these weird creatures called prime numbers!😂). God bless🙌
Doesn't this proves that there are actually infinite primes and there are also infinite twin/cousin primes(prime pair with diff 2)?
There are no negative whole numbers so saying the study of POSITIVE whole numbers was unneeded
Queen?? Really??
Can you use Prime DNA using sets? It could be a good idea to tell if they're alike.
One ring to rule them all.😅 that was amazing and remind me again to do lotr marathon 😂😂. So see you soon 😂
It would be much easier to understand if you put past info from the video in the current explanation.
Honest question...I am not the smartest guy...at 4:52, the reminder of 37/5 is 2, not 1, right? What am I getting wrong?
The division of 7 & 37 is by 2, not 5, so remainder 1 is correct.
@@MichaelRothwell1 Oh, I think I get it now, the test for 5 would be 7%5=2 and 37%5=2 also. Thank you very much, Michael.
@@sanferrera Exactly.
@@MichaelRothwell1 🙏
Fun topic, but horrible explanation starting from 4:58 up to 7:16; the most important part…
There’s another fun property to this sieve method, and that is that the numbers relatively prime to the primordial are all symmetrical along the length. For example, in the case of 30, you have [1 (-29), 7 (-23), 11 (-19), 13 (-17) …] mod 30. Another fun property is that you can use larger circles of the sieve to predict what primes have the highest likelihood to being a twin prime, and definitely discard certain ones from being twin primes, because the twins will maintain their positions with respect to the ones in the circle.
Not that anyone cares, but here's the first 256 prime values in a decimal, hexadecimal and binary representation followed by a truth table entry. This is using an 8 bit unsigned integer scheme!
// -------------------------------------------------------------
// first true case (2) is the only even prime!
// --------------------------------------------------------------
0: 0x00: 0000 0000 false
1: 0x01: 0000 0001 false
2: 0x02: 0000 0010 true
// Every prime from here out is odd!
3: 0x03: 0000 0011 true
4: 0x04: 0000 0100 false
5: 0x05: 0000 0101 true
6: 0x06: 0000 0110 false
7: 0x07: 0000 0111 true
8: 0x08: 0000 1000 false
9: 0x09: 0000 1001 false
10: 0x0A: 0000 1010 false
11: 0x0B: 0000 1011 true
12: 0x0C: 0000 1100 false
13: 0x0D: 0000 1101 true
14: 0x0E: 0000 1110 false
15: 0x0F: 0000 1111 false
16: 0x10: 0001 0000 false
17: 0x11: 0001 0001 true
18: 0x12: 0001 0010 false
19: 0x13 0001 0011 true
20: 0x14: 0001 0100 false
21: 0x15: 0001 0101 false
22: 0x16: 0001 0110 false
23: 0x17: 0001 0111 true
24: 0x18: 0001 1000 false
25: 0x19: 0001 1001 false
26: 0x1A: 0001 1010 false
27: 0x1B: 0001 1011 false
28: 0x1C: 0001 1100 false
29: 0x1D: 0001 1101 true
30: 0x1E: 0001 1110 false
31: 0x1F: 0001 1111 true
32: 0x20: 0010 0000 false
33: 0x21: 0010 0001 false
34: 0x22: 0010 0010 false
35: 0x23: 0010 0011 false
36: 0x24: 0010 0100 false
37: 0x25: 0010 0101 true
38: 0x26: 0010 0110 false
39: 0x27: 0010 0111 false
40: 0x28: 0010 1000 false
41: 0x29: 0010 1001 true
42: 0x2A: 0010 1010 false
43: 0x2B: 0010 1011 true
44: 0x2C: 0010 1100 false
45: 0x2D: 0010 1101 false
46: 0x2E: 0010 1110 false
47: 0x2F: 0010 1111 true
48: 0x30: 0011 0000 false
49: 0x31: 0011 0001 false
50: 0x32: 0011 0010 false
51: 0x33: 0011 0011 false
52: 0x34: 0011 0100 false
53: 0x35: 0011 0101 true
54: 0x36: 0011 0110 false
55: 0x37: 0011 0111 false
56: 0x38: 0011 1000 false
57: 0x39: 0011 1001 false
58: 0x3A: 0011 1010 false
59: 0x3B: 0011 1011 true
60: 0x3C: 0011 1100 false
61: 0x3D: 0011 1101 true
62: 0x3E: 0011 1110 false
63: 0x3F: 0011 1111 false
64: 0x40: 0100 0000 false
65: 0x41: 0100 0001 false
66: 0x42: 0100 0010 false
67: 0x43: 0100 0011 true
68: 0x44: 0100 0100 false
69: 0x45: 0100 0101 false
70: 0x46: 0100 0110 false
71: 0x47: 0100 0111 true
72: 0x48: 0100 1000 false
73: 0x49: 0100 1001 true
74: 0x4A: 0100 1010 false
75: 0x4B: 0100 1011 false
76: 0x4C: 0100 1100 false
77: 0x4D: 0100 1101 false
78: 0x4E: 0100 1110 false
79: 0x4F: 0100 1111 true
80: 0x50: 0101 0000 false
81: 0x51: 0101 0001 false
82: 0x52: 0101 0010 false
83: 0x53: 0101 0011 true
84: 0x54: 0101 0100 false
85: 0x55: 0101 0101 false
86: 0x56: 0101 0110 false
87: 0x57: 0101 0111 false
88: 0x58: 0101 1000 false
89: 0x59: 0101 1001 true
90: 0x5A: 0101 1010 false
91: 0x5B: 0101 1011 false
92: 0x5C: 0101 1100 false
93: 0x5D: 0101 1101 false
94: 0x5E: 0101 1110 false
95: 0x5F: 0101 1111 false
96: 0x60: 0110 0000 false
97: 0x61: 0110 0001 true
98: 0x62: 0110 0010 false
99: 0x63: 0110 0011 false
100: 0x64: 0110 0100 false
101: 0x65: 0110 0101 true
102: 0x66: 0110 0110 false
103: 0x67: 0110 0111 true
104: 0x68: 0110 1000 false
105: 0x69: 0110 1001 false
106: 0x6A: 0110 1010 false
107: 0x6B: 0110 1011 true
108: 0x6C: 0110 1100 false
109: 0x6D: 0110 1101 true
110: 0x6E: 0110 1110 false
111: 0x6F: 0110 1111 false
112: 0x70: 0111 0000 false
113: 0x71: 0111 0001 true
114: 0x72: 0111 0010 false
115: 0x73: 0111 0011 false
116: 0x74: 0111 0100 false
117: 0x75: 0111 0101 false
118: 0x76: 0111 0110 false
119: 0x77: 0111 0111 false
120: 0x78: 0111 1000 false
121: 0x79: 0111 1001 false
122: 0x7A: 0111 1010 false
123: 0x7B: 0111 1011 false
124: 0x7C: 0111 1100 false
125: 0x7D: 0111 1101 false
126: 0x7E: 0111 1110 false
127: 0x7F: 0111 1111 true
128: 0x80: 1000 0000 false
129: 0x81: 1000 0001 false
130: 0x82: 1000 0010 false
131: 0x83: 1000 0011 true
132: 0x84: 1000 0100 false
133: 0x85: 1000 0101 false
134: 0x86: 1000 0110 false
135: 0x87: 1000 0111 false
136: 0x88: 1000 1000 false
137: 0x89: 1000 1001 true
138: 0x8A: 1000 1010 false
139: 0x8B: 1000 1011 true
140: 0x8C: 1000 1100 false
141: 0x8D: 1000 1101 false
142: 0x8E: 1000 1110 false
143: 0x8F: 1000 1111 false
144: 0x90: 1001 0000 false
145: 0x91: 1001 0001 false
146: 0x92: 1001 0010 false
147: 0x93: 1001 0011 false
148: 0x94: 1001 0100 false
149: 0x95: 1001 0101 true
150: 0x96: 1001 0110 false
151: 0x97: 1001 0111 true
152: 0x98: 1001 1000 false
153: 0x99: 1001 1001 false
154: 0x9A: 1001 1010 false
155: 0x9B: 1001 1011 false
156: 0x9C: 1001 1100 false
157: 0x9D: 1001 1101 true
158: 0x9E: 1001 1110 false
159: 0x9F: 1001 1111 false
160: 0xA0: 1010 0000 false
161: 0xA1: 1010 0001 false
162: 0xA2: 1010 0010 false
163: 0xA3: 1010 0011 true
164: 0xA4: 1010 0100 false
165: 0xA5: 1010 0101 false
166: 0xA6: 1010 0110 false
167: 0xA7: 1010 0111 true
168: 0xA8: 1010 1000 false
169: 0xA9: 1010 1001 false
170: 0xAA: 1010 1010 false
171: 0xAB: 1010 1011 false
172: 0xAC: 1010 1100 false
173: 0xAD: 1010 1101 true
174: 0xAE: 1010 1110 false
175: 0xAF: 1010 1111 false
176: 0xB0: 1011 0000 false
177: 0xB1: 1011 0001 false
178: 0xB2: 1011 0010 false
179: 0xB3: 1011 0011 true
180: 0xB4: 1011 0100 false
181: 0xB5: 1011 0101 true
182: 0xB6: 1011 0110 false
183: 0xB7: 1011 0111 false
184: 0xB8: 1011 1000 false
185: 0xB9: 1011 1001 false
186: 0xBA: 1011 1010 false
187: 0xBB: 1011 1011 false
188: 0xBC: 1011 1100 false
189: 0xBD: 1011 1101 false
190: 0xBE: 1011 1110 false
191: 0xBF: 1011 1111 true
192: 0xC0: 1100 0000 false
193: 0xC1: 1100 0001 true
194: 0xC2: 1100 0010 false
195: 0xC3: 1100 0011 false
196: 0xC4: 1100 0100 false
197: 0xC5: 1100 0101 true
198: 0xC6: 1100 0110 false
199: 0xC7: 1100 0111 true
200: 0xC8: 1100 1000 false
201: 0xC9: 1100 1001 false
202: 0xCA: 1100 1010 false
203: 0xCB: 1100 1011 false
204: 0xCC: 1100 1100 false
205: 0xCD: 1100 1101 false
206: 0xCE: 1100 1110 false
207: 0xCF: 1100 1111 false
208: 0xD0: 1101 0000 false
209: 0xD1: 1101 0001 false
210: 0xD2: 1101 0010 false
211: 0xD3: 1101 0011 true
212: 0xD4: 1101 0100 false
213: 0xD5: 1101 0101 false
214: 0xD6: 1101 0110 false
215: 0xD7: 1101 0111 false
216: 0xD8: 1101 1000 false
217: 0xD9: 1101 1001 false
218: 0xDA: 1101 1010 false
219: 0xDB: 1101 1011 false
220: 0xDC: 1101 1100 false
221: 0xDD: 1101 1101 false
222: 0xDE: 1101 1110 false
223: 0xDF: 1101 1111 true
224: 0xE0: 1110 0000 false
225: 0xE1: 1110 0001 false
226: 0xE2: 1110 0010 false
227: 0xE3: 1110 0011 true
228: 0xE4: 1110 0100 false
229: 0xE5: 1110 0101 true
230: 0xE6: 1110 0110 false
231: 0xE7: 1110 0111 false
232: 0xE8: 1110 1000 false
233: 0xE9: 1110 1001 true
234: 0xEA: 1110 1010 false
235: 0xEB: 1110 1011 false
236: 0xEC: 1110 1100 false
237: 0xED: 1110 1101 false
238: 0xEE: 1110 1110 false
239: 0xEF: 1110 1111 true
240: 0xF0: 1111 0000 false
241: 0xF1: 1111 0001 true
242: 0xF2: 1111 0010 false
243: 0xF3: 1111 0011 false
244: 0xF4: 1111 0100 false
245: 0xF5: 1111 0101 false
246: 0xF6: 1111 0110 false
247: 0xF7: 1111 0111 false
248: 0xF8: 1111 1000 false
249: 0xF9: 1111 1001 false
250: 0xFA: 1111 1010 false
251: 0xFB: 1111 1011 true
252: 0xFC: 1111 1100 false
253: 0xFD: 1111 1101 false
254: 0xFE: 1111 1110 false
255: 0xFF: 1111 1111 false
// ---------------------------------------------------------
// post 8 bit unsigned first two cases:
// ---------------------------------------------------------
256: 0x100: 0001 0000 0000 false
occurrences for those groups in order:
{6, 5, 4, 3, 4, 2, 5, 2, 3, 3, 3, 3, 3, 2, 4, 2} remember, this pattern is based on log 2 and log 16.
I didn't understand anything from this video :|
sorry, after my previous comment you told about algorithm)
At 4:25 you say "first k primes" and write p_n. Did you mean to write p_k?
The bit around 4:12 felt a little fast at first, so I had to watch it twice, but the animations afterwards made it more clear. Good video nonetheless.
I really enjoyed this video
Difficult to understand
The abundance of composites is 70.6%.
Egon Spengler, in his younger years.
We all were primerbros one time or another
totalement inutile, cela revient juste à dire qu'on invente toutes les suites ax+b, avec une suite par nombre premier, et de regarder tout ce qui n'a pas a été pris par le passage de toutes les suites
where did you find this algorithm?
Primes are the best🤔🤗🤗🤗🤗 1:42
OK, my main app is stuck in a loop...
"bro-terlude" is all I needed to subscribe. I needed more interesting math in my life anyway :)
You sir... you are the Queen AND crown jewels of exhausting analogies.
(but in all seriousness, super interesting video bromanguy, this was really neat!)
Great video!
I had used the ideas up to 5:00 before to generate prime candidates that are guaranteed not to be divisible by the first k primes. Ofc, this went further than that!
4:38 You're already using p_n to refer the nth prime, so using p_k to refer to the kth primorial is confusing. Also, it's inconsistent with your earlier notation which used a subscripted capital Pi and your later notation which used a (unsubscripted) Q. Just be mindful of consistency/notation next time. Calling one thing by one name one time and by a different name another time leads to unnecessary confusion. Calling two different things by the same name also leads to unnecessary confusion.
4:45 prime p divides the primorial p_k if only if p
The proof of this solution is surprisingly simple.
It may be interesting that, as you can see, the twin numbers in the form p # + - 1 ends at p = 11.
The second remark is the vertical axis of symmetry of the circle.
In my similar algorithm I use numerical sequences with cyclic differences.
The use of wheels complicates and makes it difficult to understand the subject.
7:40 ans: 49 time: 3 seconds
You sound like Sheldon Cooper
oh my gosh, you're cool
Not enough views yet for this meaningful algorithm...
Which reminds me of my own exploration and the very interesting things I found in this domain 😀
great video
Imagine the factors on the wheel were actually functions instead of numbers lol.
fyi that's lambda calculus
In the beginning was the Word, and the Word was with God, and the Word was God. 2He was with God in the beginning. 3Through him all things were made; without him nothing was made that has been made. (John 1:1-3)
LOL
WHO IS Paul Pritchard ?
I am.
Oh well... It is pretty obvious... Discovered this algorithm myself before youtube was a thing (saying it that way makes me feel old though)
Though making wheel out of wheel is slightly more efficient than what i was doing
Nice video, Egon Spengler.
Hi Aaron!
"If you can count you can understand number theory" 🤔 I'm pretty sure that doesn't logically follow
liked just for the "you can go back to the EXTREEEEMELY productive thing you were doing before" XDDD
Also note that if you have a wheel built for factorial of p, you have p symmetries but they are not "compatible" with each other so you have to choose one to reduce the actual size of the wheel.
My favourite property is that the primorial set (that's what I called it when I first discovered this) contains numbers that are not only all coprime with each other, but are also coprime with each number (x) in the set + n * primorial_set_value.
And there's more.
Take any number x from the set, multiply it with each number in the set in order modulo primorial_set_value, and you will, I kid you not, get back every number in that primorial set, but each with a unique reordering.
When you model the sequence as intervals, it's even more interesting. Firstly, you can clearly see that it produces an infinite seed for EVERY single prime gap from the previous primorial set (though it does not imply infinite prime gaps of any amount).
This view of primes also gives you a remarkably different way of navigating and ordering potential primes.
Aaand, one of my favourites ... going back to the aspect of any x,y pairing from the set modulo the primorial_set_value giving you a value from the primorial set (along with the unique shuffling behaviour) gives you a really simple method of private key encryption!
I never found it faster for generating primes, but this was about 15 years ago, and written in Java in a very OO way (the JVM and most VMs are much more efficient now though).
Your voice tone is should be more friendly, calm and exited, so that people tend to feel what you appear like feeling when talking
This is coprime patterns that eventually filter out the primes as you add primes to filter. Current filters are very symmetric, even mirrored halfway betweeen periods. It's beautiful but still not efficient.
I'm impressed with myself i actually got 49 almost immediately :D
nice one - thanks! And thank You Pritchard - in Poland the surname: Pritchard is mainly known by some S-F books :) but it wheel soon change :)
I have played with this, but more as a shifting ruler then a wheel. Good to have a different thought/method of it. Especially the cancellation of removing the smaller one from the larger one.
...the tissues on the table are a nice touch. (great video btw!!)
Great video !, Don't stop making vids lik these..
I felt personally attacked by prime bro
Please make the preview more appealing, more people would know about this great video
This is going to explode.
286 may be number theory but is it numberwang?
That's cool. I wrote some code years ago to do this. Didn't know anyone else who had done this.
Art of problem solving vol 1 is one of the books lying on the floor
The greeting in the beginning sounded like Agadmator
Please redo with higher volume.
Thank you for making my head hurt
Unrelated question to the video topic. But how do you like the Art of Problem Solving books? I've never seen one in real life but have bought them before for nieces/nephews. Do they deliver as promised at least for those who work them? I'm not certain my money was well invested but don't know if that was down to the child, the parent or the book.
Beautiful books bro, I recognized his copy too, they are beyond insightful, and have given me an incredible amount of fun problem solving and learning moments. I would absolutely suggest reading them, but I’m a highschooler and idk if an adult would really find much use in them, I use them for primarily fun but also to study for contests
3:10 this is what i did when i was in sixth grade😅😅
Isn't the sieve of Atkin faster?
Eso es como el círculo de quintas de la música.
ok but who plays the bro
Exceptionally well delivered.
Ghandi's Recursive Formula for the next prime: Let p be an odd prime and let Q be the product of the primes less than p. In MathJax/LaTex let S=(-1/2)+\sum_{d|Q}\mu(d)/(2^d-1) where \mu is the Mobius function. Then 1
What do you mean?
The summation has cardinality of Q terms.
@@joseville No. The summation is over all divisors of Q, not over the prime divisors of Q. For each divisor d of Q there is a term \mu(d)/(2^d-1). If Q is the product of the first 46 primes then Q has 2^{46) divisors .
@@danielgautreau161 Ah I see. Thanks for explaining!
@@joseville To prove Ghandi's result, write each
(2^d-1)=(2^{-d}+2^{-2d}+2^{-3d}+...). (power series). Now collect "like powers" of 2 in the expression for S. Now use the Mobius function property
\sum_{d|n}\mu (d)=0 when n>1, and \mu (1)=1, to show
S=\sum_{n\in K} 2^{-n}, where K is the set of all n>1 that are co-prime to Q. The smallest member of K is p, and all members of K are odd, so
2^{-p}
Beautiful !
Amazing!
Very cute
Gold ✨😂
Hmm.
truly amazing!!
Wilson's Theorem
How does it play into this? Just curious.
Awesome! I've always been fascinated by primes! Need to watch this few more times.
247
If primes are defined by what they are not, then Mersenne primes are the defined by…
Has it been proven to be theoretically fastest?
It's not the fastest. It's on par with the sieve of Atkin asymptotically(which pritchhard basically ripped off btw, he only made a slight change to reduce the space complexity), if anything it has higher constant factors usually speaking.
@@swagnegrocongucci134 but is it asymptomatically optimal?
@@tunafllsh Might be. There is n/logn as a trivial lower bound but there is not a tighter one known yet
@@swagnegrocongucci134 Atkin was introduced over 20 years later.
@@disoriented3971 Right, sorry. I got the names mixed up