I love these simple web games! Great idea. One way to improve it is to add some more juice when you answer a question. Right now, the text in the number just swaps to the next question, so any sort of small visual feedback will help first time players get it more.
I also like to make these small web mini games on the side. Here's one where you guess the year that famous events happened: https://guess-the-year.davjhan.com/
I love it, but the game doesn't work for me! No response when I click Yes or No, or using the keyboard y and n. Just the clock ticking down. Chrome Version 91.0.4472.114 (Official Build) (64-bit) on Windows 10 Enterprise.
I wonder if the text could be dropped once it starts. I found myself reading it each time which ended up distracting me a little and sometimes I would rush and tapped the opposite of what I intended.
Is there a reason we're obsessed with primes beyond aesthetics? Why does this set of numbers garner all the headlines as opposed to some other arbitrary integer sequence like the Recamán numbers [0] ?
If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?
I'm not sure about a closed-form equation for the nth prime, but if integer factorization can be done in linear time then much of applied cryptography needs to be replaced.
The prime numbers are critical in cryptography. Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers.
Any major step towards understanding them (such as a closed-form equation for primes) would have major mathematical knock-on effects which may or may not undermine these methods, or provide us with a basis for even stronger cryptographic mechanisms to make use of in the future.
>Almost all of our current digital security infrastructure is based on the concept of multiplying large numbers together modulo suitably big prime numbers.
There are two main operations for whole numbers: addition and multiplication. A basic question is what are the "atoms". With respect to addition, the atom is 1, since every number can be written as a sum of 1's, and 1 isn't itself a nontrivial sum. With respect to multiplication, the atoms are the primes, where primes aren't nontrivial products.
A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number.
Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns.
The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution.
I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition.
Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.
> If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?
Btw, that kind of exists. There's a formula that produces nothing but prime numbers. It basically encodes sieving, and it coincidentally uses every letter of the English alphabet.
Beyond cryptography, there is the fundamental theorem of arithmetic, which plays an important role in encoding Gödel numbers in Gödel's theorem.
In algebra, the integers mod p are a finite field (addition, subtraction, multiplication, and division are defined) if and only if p is prime.
Primality in algebra also exists in a more general form with prime ideals. An ideal is the set of elements of a commutative ring in which any element of the ideal multiplied by any element of the ring is still in the ideal; there is a sort of 'closed' property. Even numbers form an ideal because if you multiply any number by an even number, you get an even number. For a prime ideal, if ab is in the ideal, a is in the ideal or b is (similar to how if a prime number divides ab, it divides a or b).
They have a number of interesting properties. For example, for a ring homomorphism (a function from one ring to another that preserves relationships between elements of the two rings), the pre-image of a prime ideal is also a prime ideal.
prime numbers let you abstract away parts of math that would normally require bruteforce to solve in the human mind.
Remember finding the common denominator in school, or reducing fractions to their lowest form. both require guess work to do the normally taught way, but both can be achieved using prime factorization in a "set" way that resolves to a solution.
I struggled in grade school to do fractions purely because of reducing and common denominators, but ended up tutoring people how to do them in college pre-algebra because thats when I learned about prime factors and what you can do with them.
If i had learned algebra before basic fractions i likely wouldn't had needed to dropout of high school and get a ged.
One is not a prime number. If you allow one to be a prime number, then you can no longer say that each natural number has a unique prime factorization.
This makes the concept of prime numbers much more useful when one is excluded.
> If you allow one to be a prime number, then you can no longer say that each natural number has a unique prime factorization.
I don't dispute that, by definition, 1 is not prime, but I don't see how this statement would follow if we considered it prime.
Edit: it seems more like it would be that every factorization would implicitly have 1^n tacked onto it, and while that isn't exactly useful, it doesn't break the game.
Could you please demonstrate an example of such a break? I think if we really look at it, we might see that it's really just convention and semantics. I don't want to seem like I'm cherry picking by providing my own example.
Let's call a number an Igelau prime if it is the number 1 or a prime number. Then an Igelau prime factorization of 15 is 3⋅5. Another Igelau prime factorization of 15 is 1⋅3⋅5. Another Igelau prime factorization of 15 is 1²⋅3⋅5. And so on. There are infinitely many Igelau prime factorizations of 15, thus there is no uniqueness.
and there will be no prime numbers above 1 if 1 is considered a prime (based on existing definitions)
Though if you think about it they can just modify the definition in that case
The definition I usually use (speaking loosely for the moment) is that prime numbers are natural numbers greater than one whose divisors are only one and itself.
Speaking more formally, a natural number p is a prime if and only if:
a) p > 1
b) for any natural number n satisfying 1 < n < p, p mod n ≠ 0
This reminds me of my favorite in-person magic trick to do.
First, memorize all the two-digit primes. 25 numbers isn't that hard to memorize.
Then, tell someone "Oh, I can instantly tell whether a number is prime or not. Give me a number, I'll tell you whether it's prime."
If they tell you a number between 1 and 100, use your memorized list. Otherwise, it's a game of cold reading; if they just generated a random string of many digits, there's a low chance that the number actually is prime. "21923847" is a keysmash, and it's almost certainly not prime, because the frequency of primes goes down as numbers get bigger. And most people will ask you a number, hear "no", and then go check the number's primality. Eventually, they'll look up a number in advance; that number is almost certainly prime.
After 8 attempts, I ran into "Game Over". Was just thinking about the satisfaction for the author of this site. There is just enormous fun in saying - Game Over - to another human :)
Also, most composites are divisible by 2, 3 or 5, all of which are very easy to check (for 3 just sum up the digits and if the result is divisible by 3, the original number is divisible by 3). 49, 77, and 91 are the only composites under 100 that is not divisible by one of those 3 numbers, making memorizing 25 numbers not even necessary. 49 and 77 are obviously composite to me making 91 the only number I bothered memorizing.
I hope the twin prime conjecture holds, since it would be pretty incredible to think that, despite what you said, there are infinitely many twin primes.
If I were able to count them out loud, in order? 999 nonillion, 999 octillion, 999 septillion, 999 sextillion, 999 quintillion, 999 quadrillion, 999 trillion, 999 million, 999 thousand, 999.
That is (after consulting a table), 1 decillion - 1.
I clearly come from from a short scale culture. If I switched to the long scale and Chuquet names I could, of course, go to 999 nonilliard, 999 nonnillion, 999 octilliard, etc.
It is very useful in the context of Chinese grade school. There are a lot of exam problems that require factorization, and calculators are banned. Having a list of primes memorized comes really handy.
Lol right because I never had to memorize the multiplication tables, states capitols, electron shell levels and numbers, periodic tables, etc in the US
I don't think that was a thing in France (at least where I went to school) but we often used them indirectly to simplify fractions, so all in all maybe we had to know all primes under 25 I think?
It isn't standard in the US, although at some point I memorized them to prepare for buzzer races in math competitions. It was in no way reflective of anything useful in real life, but it was fun.
There were a few sets of common numbers, formulas, and mental calculation tricks that were useful to just always have in the back of your head. Perfect squares and cubes under 1000, powers of 2 and 3, prime numbers below 100, interior angles of regular polygons up to 10 sides, binomial coefficients, Pythagorean triples, factorials up to 9!, common roots out to 3-4 decimal places, and a few others that I've no longer needed for almost 20 years at this point.
Now I, even I, would celebrate
In rhymes unapt, the great
Immortal Syracusan, rivalled (sic) nevermore
Who, in his wondrous lore,
Passed on before,
Left men his guidance
How to circles mensurate.
It's easy to determine divisibility by 2, 3, 5, and 11. 7² is also easy because it's a square. 7×13=91 is the only composite number under 100 that isn't caught by these rules.
51's an easy one because 5+1=6, and 6 is divisible by 3, so it must be divisible by 3.
It's easy to try 'divisible by 5' (ends in 5 or 0) and 'divisible by 3' (sum of digits is divisible by 3). 91 isn't found as prime by those two tests, so it needs the extra exceptional rule.
49 looks prime to me. Another commentator says it doesn't count because it's a square number, but square numbers don't really have a particular "look" to me in the same way that 2-digit numbers ending in 5 or with digits summing to a multiple of 3 do.
There's no "look" for me either. But I immediately know that 49 is not prime because I recognize it as the answer to one of the times table math problems that I learned.
Really like that! Presumably this is because most people's sense of what feels prime is: odd numbers which don't appear in the times tables; and only 39, 51, 57, 69, 87, 91 and 93 are red herrings in that regard, all of which bar 91 are divisible by 3, which people also have a good sense of, not least by using the add the digits rule.
I’ve always wondered: how feasible is it to implement an “isprime” function, via lookup table? If such methods are used, is cryptography getting weaker and weaker in practice as more large primes are discovered?
Time to generate I get, but you could always augment the table over time and fall back to standard methods otherwise (and store the result).
Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
If your question is purely "is the value prime" the Fermat primaility test is very fast, probably about as fast as a hash table lookup on a table that large. Running Baillie–PSW to eliminate false positives isn't a huge deal either as it will only need to run if Fermat passes. It's not a horrible idea on its face and may indeed be a little faster, at the cost of lots of memory. I don't know of a use case where it would be worth it.
It's interesting to compare the game play and design. My game is written in Elm and open source if anyone is interested. This website has keyboard inputs (y or n) which is a good idea. My game only does click/touch inputs.
I've started, if I wake up in the middle of the night, thinking of a 'prime-looking' number, then trying to factor it. Sometimes I discover interesting connections, other times I fall back asleep - either is a win.
138 comments
[ 2.9 ms ] story [ 212 ms ] threadI also like to make these small web mini games on the side. Here's one where you guess the year that famous events happened: https://guess-the-year.davjhan.com/
I wonder if the text could be dropped once it starts. I found myself reading it each time which ended up distracting me a little and sometimes I would rush and tapped the opposite of what I intended.
If tomorrow someone discovered a closed-form equation for the nth prime, how would mathematics/the world change?
[0] https://en.wikipedia.org/wiki/Recamán%27s_sequence
https://en.wikipedia.org/wiki/Recamán%27s_sequence
Any major step towards understanding them (such as a closed-form equation for primes) would have major mathematical knock-on effects which may or may not undermine these methods, or provide us with a basis for even stronger cryptographic mechanisms to make use of in the future.
That's not true of elliptic curves.
A cool thing about breaking a number into multiplicative atoms (the "prime decomposition") is that to multiply two numbers, you can just add up however many copies there are of each atom. Primes turn multiplication into addition in this way. In other words, each prime defines a sort of logarithm that measures the amount of that prime in a number, and knowing the "coordinate" in prime space is enough to determine the original number.
Then one might wonder what is the relationship between primes and addition. When you add two numbers, the prime decomposition of the result seems to be dramatically different from the decompositions of the summands. But there are patterns, like how the sum of even numbers is even. The abc conjecture[1] has to do with one of these patterns.
The relative order of the primes also is saying something about the relationship between addition and multiplication, since addition underlies how you compare two numbers. There are old results about the density of the primes as if they were following a random distribution.
I'm not sure if there's any deep structure that Recamán's sequence has anything to do with. All that seems to be interesting about it is that it evades our capabilities of determining whether every number eventually appears. The Collatz conjecture is similar in this way, though it is further complicated by the fact that it mixes the structures of multiplication and addition.
[1] https://en.wikipedia.org/wiki/Abc_conjecture
Going deeper, in algebraic geometry, what you do is take various number systems (called "rings" -- the integers are an example of a ring) and pretend each element is a function that measures some scalar quantity about an associated space. It's a bold and wild idea. There is a process by which you can figure out what the points of this associated space are, and, at least for the integers, there is one point for each prime. If you think about an integer n as a function defined on this space, then the evaluation of n at the point p ends up being equal to n mod p. All I'm trying to say by bringing this up is that primes are not just aesthetic, they have deep significance, with many analogs in other kinds of mathematics.
Btw, that kind of exists. There's a formula that produces nothing but prime numbers. It basically encodes sieving, and it coincidentally uses every letter of the English alphabet.
https://en.wikipedia.org/wiki/Formula_for_primes#Formula_bas...
In algebra, the integers mod p are a finite field (addition, subtraction, multiplication, and division are defined) if and only if p is prime.
Primality in algebra also exists in a more general form with prime ideals. An ideal is the set of elements of a commutative ring in which any element of the ideal multiplied by any element of the ring is still in the ideal; there is a sort of 'closed' property. Even numbers form an ideal because if you multiply any number by an even number, you get an even number. For a prime ideal, if ab is in the ideal, a is in the ideal or b is (similar to how if a prime number divides ab, it divides a or b).
They have a number of interesting properties. For example, for a ring homomorphism (a function from one ring to another that preserves relationships between elements of the two rings), the pre-image of a prime ideal is also a prime ideal.
Remember finding the common denominator in school, or reducing fractions to their lowest form. both require guess work to do the normally taught way, but both can be achieved using prime factorization in a "set" way that resolves to a solution.
I struggled in grade school to do fractions purely because of reducing and common denominators, but ended up tutoring people how to do them in college pre-algebra because thats when I learned about prime factors and what you can do with them.
If i had learned algebra before basic fractions i likely wouldn't had needed to dropout of high school and get a ged.
This makes the concept of prime numbers much more useful when one is excluded.
I don't dispute that, by definition, 1 is not prime, but I don't see how this statement would follow if we considered it prime.
Edit: it seems more like it would be that every factorization would implicitly have 1^n tacked onto it, and while that isn't exactly useful, it doesn't break the game.
Let's call a number an Igelau prime if it is the number 1 or a prime number. Then an Igelau prime factorization of 15 is 3⋅5. Another Igelau prime factorization of 15 is 1⋅3⋅5. Another Igelau prime factorization of 15 is 1²⋅3⋅5. And so on. There are infinitely many Igelau prime factorizations of 15, thus there is no uniqueness.
Edit: Clarifying what Igelau primes are.
Endlessly saying "primes other than 1" gets kind of tedious.
Speaking more formally, a natural number p is a prime if and only if:
a) p > 1
b) for any natural number n satisfying 1 < n < p, p mod n ≠ 0
So a solid majority of all computer users.
First, memorize all the two-digit primes. 25 numbers isn't that hard to memorize.
Then, tell someone "Oh, I can instantly tell whether a number is prime or not. Give me a number, I'll tell you whether it's prime."
If they tell you a number between 1 and 100, use your memorized list. Otherwise, it's a game of cold reading; if they just generated a random string of many digits, there's a low chance that the number actually is prime. "21923847" is a keysmash, and it's almost certainly not prime, because the frequency of primes goes down as numbers get bigger. And most people will ask you a number, hear "no", and then go check the number's primality. Eventually, they'll look up a number in advance; that number is almost certainly prime.
https://oeis.org/A000043
Curious if that is common in other countries?
That is (after consulting a table), 1 decillion - 1.
I clearly come from from a short scale culture. If I switched to the long scale and Chuquet names I could, of course, go to 999 nonilliard, 999 nonnillion, 999 octilliard, etc.
There were a few sets of common numbers, formulas, and mental calculation tricks that were useful to just always have in the back of your head. Perfect squares and cubes under 1000, powers of 2 and 3, prime numbers below 100, interior angles of regular polygons up to 10 sides, binomial coefficients, Pythagorean triples, factorials up to 9!, common roots out to 3-4 decimal places, and a few others that I've no longer needed for almost 20 years at this point.
+1... I lost two games in a row, both times on 91.
It's easy to determine divisibility by 2, 3, 5, and 11. 7² is also easy because it's a square. 7×13=91 is the only composite number under 100 that isn't caught by these rules.
It's easy to try 'divisible by 5' (ends in 5 or 0) and 'divisible by 3' (sum of digits is divisible by 3). 91 isn't found as prime by those two tests, so it needs the extra exceptional rule.
51 is #1, then 57, then 1
The "looks prime" rule assumes you check for multiples of 3, so that removes one.
All the rest end in an even digit or 5.
Keyboard short cuts would make it a bit better.
For smaller numbers see various prime sieves (Atkin, Eratosthenes)
Storage I have a harder time wrapping my head around. Aren’t primes quite sparse at cryptographic magnitudes? And are the primes used for (say) 256-bit encryption about the same magnitude, narrowing the dimension of storage required?
For RSA one typically use 2048 or 4096 bit primes.
It's interesting to compare the game play and design. My game is written in Elm and open source if anyone is interested. This website has keyboard inputs (y or n) which is a good idea. My game only does click/touch inputs.
https://github.com/alexlieberman/Prime-Numbers/blob/master/S...
https://en.m.wikipedia.org/wiki/Ulam_spiral
1 is non-prime by definition.
You correctly sorted 17 numbers.