That's not a primary source and wrong. A prime is most simply: it has no factors other than itself and 1. "Not being even" is a corollary, and would be redundant if included in the definition of primality.
Another way to see this is to observe that the Fundamental Theorem of Arithmetic would be wrong (or more difficult to state succinctly) if 2 were not considered prime or if 1 were considered prime.
For example, if 2 were not prime, it would be impossible to represent the number 256 (or the number 123456) as a product of primes.
It's not, though. It's one group of mathematicians appropriating prime numbers and jack-booting them into their favourite theorem. There are valid reasons to treat 1 as a prime number, just as there are for defining 0^0 as 1 in some cases.
Also for a fun pastime try asking an arithmetician to apply the fundamental theorem to 1 and watch them squirm.
This definition is also sensible because it also preserves uniqueness in both directions. The empty set is the only prime factorization of 1, and 1 is the only natural number whose prime factorization is the empty set. (Wikipedia has a footnote that "Using the empty product rule one need not exclude the number 1 [from the fundamental theorem of arithmetic], and the theorem can be stated as: every positive integer has unique prime factorization.")
The fundamental theorem doesn't have to state that the prime factorization is nonempty.
It's true that some mathematicians have defined 1 as a prime number and there's nothing logically inconsistent about doing so, but it makes most theorems and formulas in number theory more complex and so this definition has fallen out of favor.
Edit: I think the Wikipedia article on the empty product gives some quite nice examples of the benefits of a closely related concept. https://en.wikipedia.org/wiki/Empty_product
See? Squirming. Somehow multiplying 0 factors is supposed to result in 1.
I'm not saying it's incorrect, but you have to explain that edge case away. At the same time allowing 1 to be prime would remove that problem given that e.g. 6 = 2^1 * 3 ^1 and 6 = 1^81 * 2^1 * 3^1 are the same unique factorisation because, well, monoids.
> Presumably the arithmetician will answer that its factorization is the empty set.
Arithmetician (Ph.D. in number theory) here. This answer is completely correct.
As another reason why the factorization of 1 should be the empty set: suppose you have two positive integers m and n. Write S(m) and S(n) for their sets of prime divisors, counted with multiplicity.
Then S(mn) is the union of S(m) and S(n). We need S(1) to be the empty set to make this rule consistent.
Why would anyone "squirm"? You have an issue with multiplying 0 factors to obtain 1, but you don't have a problem with multiplying a number by itself 0 times to obtain 1?
What the sibling response to my own is correct. It's just the empty set.
Alternatively: "even" means "multiple of 2". Saying "no primes are even" is isomorphic to saying "no primes are multiples of 3 [or any other p you choose]". A claim "n can't be prime if none of the other primes are multiples of n", implies that cannot exist at all.
That may be true now, but perhaps not in the future.
Heck, mathematicians in general thought number theory was “useless” up until only around 40 years ago. Now we know that our world could not have developed this way without the creation of modern cryptography.
I think number theory serves as a great example for why basic research is so important to humanity.
Primality testing is actually much easier than integer factorization thanks to Fermat's "little" theorem. Methods based on this theorem, including the Lucas-Lehmer test for Mersenne primes, can identify prime numbers on classical computers in polynomial time. However, factorization is not possible with this method.
The universe is likely a simulation, so a soul maybe a prime primary key and so use a Mersenne prime to save space as a form of compression because only n needs to be stored, not the full bitstring. The real question is: does the universe have microcode opcodes to operate on Mersenne primes natively without expanding them?
Likely a simulation... Even though there isn't any empirical evidence of this fact... But you still believe? Is athiesm just another form of religion these days?
Well look at Godels Incompleteness Theorem... Not every statement in mathematics actually even has a proof inside mathematics. So math doesn't even have the tools to fully investigate itself.
That's an awesome point. The poor saps have to hand-waive around axioms within their own field. No way they're going to accept divine interventions and invisible dragons in some other line of work :)
You are correct in challenging the GP, but for the wrong reasons. Your statement reveals undue confidence in your assumptions on the nature of objective reality.
I used to be into this stuff in college--we were obsessed with the idea of generating very large or else very large numbers of odd numbers, such as weird numbers or untouchable numbers. I was into HPC and writing programs that run on clusters, and this gave me some good practice.
We eventually realized that no one really cared about the numbers we felt confident we could find--now Mersenne primes, though, people really care about those, but they're extraordinarily difficult to find. Always a cool day to see a new one.
We would write the number out for you, but it would fill up thousands of pages, give or take, and look like this gigantic zip file.
It's ironic to see that 11MB file being called "gigantic" in this day and age; many web pages are now unfortunately much larger, and the page of the article itself transfers at least 1MB of data.
It would be nice if this were used as the PoW problem for a blockchain. Since the Mersenne Primes are rare, the PoW problem shouldn't be to find new Mersenne Primes directly, but something that could make indirect progress on that. Also the blockchain should solve an actual problem, such as torrent tracking or DNS.
It makes me think that there should be a list of viable uses of blockchain, and another list of interesting problems that could be moulded into PoWs, and they should be paired up into blockchains.
How would you measure amount of work you want to reward with a coin? In both DNS and torrent examples one can influence a supply of work to be done rather easily
It's a broad idea to construct a secure PoW, with all that's required to make it secure, but to try and make it applicable to areas like number theory. See PrimeCoin for a successful example.
Also your concerns are unfounded: See Namecoin and Primecoin. I'm thinking these two ideas could be combined.
One problem is that a black hat could solve a lot of primes in secret, and then use those for a double spend attack.
Specifically,
a) Spend some coins to buy some other cryptocurrency
b) use all their secret primes creating a bunch of new blocks on a branch where they haven't spent their money. Since this is the longest branch now, all the other clients accept they haven't really spent it.
c) buy the other cryptocurrency again on this new branch.
No. The PoW problem should be derived according to the current state of the blockchain. That makes "solving a lot of primes" in secret inapplicable. You read my post far too literally.
The idea is to combine the ideas behind Namecoin with Primecoin.
Actually, the problem is that there is no way to control the difficulty. Finding new primes would be harder and harder, but you want the difficulty to adjust up or down to target a block time. Not sure how primecoin approached that problem?
67 comments
[ 2.9 ms ] story [ 114 ms ] threadHeh.
For example, if 2 were not prime, it would be impossible to represent the number 256 (or the number 123456) as a product of primes.
The fundamental theorem doesn't have to state that the prime factorization is nonempty.
It's true that some mathematicians have defined 1 as a prime number and there's nothing logically inconsistent about doing so, but it makes most theorems and formulas in number theory more complex and so this definition has fallen out of favor.
Edit: I think the Wikipedia article on the empty product gives some quite nice examples of the benefits of a closely related concept. https://en.wikipedia.org/wiki/Empty_product
I'm not saying it's incorrect, but you have to explain that edge case away. At the same time allowing 1 to be prime would remove that problem given that e.g. 6 = 2^1 * 3 ^1 and 6 = 1^81 * 2^1 * 3^1 are the same unique factorisation because, well, monoids.
Edit: `s/fields/monoids`
Now you are the one squirming.
Cleanly accounting for edge cases isn't squirming, it's logical thinking.
Arithmetician (Ph.D. in number theory) here. This answer is completely correct.
As another reason why the factorization of 1 should be the empty set: suppose you have two positive integers m and n. Write S(m) and S(n) for their sets of prime divisors, counted with multiplicity.
Then S(mn) is the union of S(m) and S(n). We need S(1) to be the empty set to make this rule consistent.
Analogous to how log(1) is equal to 0.
The analogy is a good one, as zero is the additive identity (https://en.wikipedia.org/wiki/Additive_identity) of the integers, and one is the multiplicative one (https://en.m.wikipedia.org/wiki/1#Mathematics)
What the sibling response to my own is correct. It's just the empty set.
https://news.ycombinator.com/newsguidelines.html
Heck, mathematicians in general thought number theory was “useless” up until only around 40 years ago. Now we know that our world could not have developed this way without the creation of modern cryptography.
I think number theory serves as a great example for why basic research is so important to humanity.
Google told me that, surprisingly, it's not even known that they are infinite!
I found this nice page on the Wagstaff Mersenne Conjecture:
https://primes.utm.edu/mersenne/heuristic.html
whoa
PS: Atheist ;)
And: "Likely"? Objection, your honor. Assumes facts not in evidence.
If it was real and explainable by science, we won't call them supernatural
https://en.m.wikipedia.org/wiki/Law_of_the_instrument
PS: I remember scheduling Prime95 to run on lab computers at work (a nuclear engineering shop) after-hours, c. 1998.
https://www.mersenne.org/various/math.php#lucas-lehmer
https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality...
We eventually realized that no one really cared about the numbers we felt confident we could find--now Mersenne primes, though, people really care about those, but they're extraordinarily difficult to find. Always a cool day to see a new one.
It's ironic to see that 11MB file being called "gigantic" in this day and age; many web pages are now unfortunately much larger, and the page of the article itself transfers at least 1MB of data.
A thorough joke.
It makes me think that there should be a list of viable uses of blockchain, and another list of interesting problems that could be moulded into PoWs, and they should be paired up into blockchains.
Also your concerns are unfounded: See Namecoin and Primecoin. I'm thinking these two ideas could be combined.
Specifically,
a) Spend some coins to buy some other cryptocurrency
b) use all their secret primes creating a bunch of new blocks on a branch where they haven't spent their money. Since this is the longest branch now, all the other clients accept they haven't really spent it.
c) buy the other cryptocurrency again on this new branch.
The idea is to combine the ideas behind Namecoin with Primecoin.
Update: found some clues here, https://www.reddit.com/r/primecoin/comments/1i71ma/strange_b...