8 ms·
R49081 Is Prime
- quickthrower2 4y agoQuestion: how does the density of R(x) primes, with respect to x, compare to the density of primes. Are they the same?
- Someone 4y agoWe don’t even know whether there are infinitely many decimal Repunit primes (https://primes.utm.edu/glossary/page.php?sort=Repunit https://primes.utm.edu/glossary/page.php?sort=Repunit) Even if that were true, we know there always is a prime between n and 2n (https://en.wikipedia.org/wiki/Bertrand%27s_postulate https://en.wikipedia.org/wiki/Bertrand%27s_postulate). Since there’s a factor of about 10 between successive repunits, the repunits themselves are already spaced further apart, let alone those that are prime (for which the first filter is “for R(x) to be prime, x must be prime”) So, no, they aren’t equal.
- quickthrower2 4y agoThanks for the answer. I meant with respect to x. So if R1 to R100 were all prime for example, for that range I consider it 100% dense by my definition. Instead if 0.0000000…00000009% dense by computing: 100/R100. Hope that makes sense. My definition of course may be at odds with mathematical conventions.
- deleted 4y ago[deleted]
- smoldesu 4y ago> The certification took 20 months on an AMD 3990x computer (64 cores); and verification took about 13 hours. I'm absolutely dumbfounded (and awestruck) that there are people who dedicate this much compute power to solving these tasks.
- noduerme 4y agoI'm equally dumbfounded that with all this computing power no one has written an AI that can identify primes 99.999% of the time for quicker testing. Train that thing and reverse its logic. I'm not one of those people who think primes are the keys to the universe. I'm not sure how one day people realized there's no pattern, just a form of embedded randomness, behind any irrational number like Pi... yet still think the prime sequence is more important than that. [edit] it's as if we're so desperate for order to arise out of chaos that we'll bend reality to find the order in any sequence. Seems like our own problem, not God's. [edit2] I am eagerly awaiting any response to know why this is such an unpopular comment! I'm excited to have my mind changed. Tell me.
- pushedx 4y agoPrime numbers are the basis of most practical cryptosystems (including ones which you used to make your comment), and other applications of number theory, and are the heart of number theory itself.
- l33t233372 4y agoI believe this is an unpopular comment because “training an AI to identify primes” is pretty much technobabble. What sort of AI are you referring to? A deep neural network? Why should this be better than our current techniques?
- noduerme 4y agoReally? It's not techno babble. Encode the first few thousand primes in QR codes and pictures of ducks, throw 2000 GPUs at it and see how long it takes to train a model to pick them out of the other similarly encoded integers. Tune for success rate with the next few thousand primes. Even if it's only right 20% of the time you've vastly increased the efficiency of finding new prime numbers.
- tiagod 4y agoYou're making a lot of generic guesses and assumptions. Do you really think nobody has ever thought of this?
- jakelazaroff 4y agoCan someone ELI5 this post?
- loeg 4y ago
- layer8 4y agoR49081 is the natural number consisting of 49081 “1” digits in decimal base, or (10^49081 - 1)/9. This number has now been proven to be a prime number, using some number-crunching algorithm. Somebody else will have to ELI5 that algorithm.
- krasin 4y agoEdit: the OP is correct, I was confused by the forum name, as I thought it was about Mersenne primes, but this is about Repunit primes. Original response: Almost correct, but it's 2^49081-1, not (10^49081-1)/9. And there's no division by 9 at all. https://en.wikipedia.org/wiki/Mersenne_prime https://en.wikipedia.org/wiki/Mersenne_prime
- layer8 4y agohttps://primes.utm.edu/top20/page.php?id=57 https://primes.utm.edu/top20/page.php?id=57, linked in the article, begs to differ.
- krasin 4y agoThank you! You're right, this is not about a Mersenne prime, but about Repunit prime. Sorry about that!
- googlryas 4y agoNo, this is just on the mersenne prime forum. If you read [1] from the link it tells you OP is right.
- happytoexplain 4y ago
- dragontamer 4y agoR49081 means this was a ~49081 digit number, or a number that could be represented in maybe 163043-ish bits or ~20kB or so? I'm kinda curious if this is a data-size that might be better on CPU rather than GPU. GPUs of course are better compute, but GPU-registers tend to cap out at ~1024 bytes or so, and a number of this size probably would have to be stored in RAM (plus all the associated data structures in ... whatever algorithm happened here). If this were small enough, I can kinda imagine CPUs being better due to caching effects (L1 and L2 are incredibly fast on CPU, and GPUs kind of miss those tiers in some sense since GPUs focus on register space). It could just be that this eliptical-curve prime-testing program is currently a CPU kinda function. But I'm curious if this algorithm would be (or wouldn't be) suitable for GPU compute, with more TFLOPS and more VRAM bandwidth for cheaper. EDIT: A 20kB number would fit inside of __shared__ memory on GPU, so perhaps various operations (multiplication and/or division??) could be parallelized onto a 256-wide/1024-wide workgroup (~1024 to 4096 bytes per clock tick, or ~5 to ~20 clock ticks to perform most kinds of operations with the 20kB number on one compute unit). It really depends on the kind of algorithm going on here, as well as what needs to be searched for. I did a brief read into ECPP testing, and I honestly don't get anything they're saying in the paper (A. O. L. ATKIN AND F. MORAIN, 1993. "ELLIPTIC CURVES AND PRIMALITY PROVING").
- Dylan16807 4y agoThese are "repunit" primes, meaning that it's the digit "1" repeated N times, in this case 49081 times. So yes 20KB.
- jl2718 4y agoThis is probably a stupid question, but why do they use an elliptic group rather than, e.g. an ordinary exponential group? It seems they’re using the property that the group order is N-1.
- nullc 4y agoMy understanding is that this particular proof works by constructing a curve over a finite field built of the number to be tested with a "sufficiently large" prime order, you prove its order by just multiplying a generator by the order. The curve won't work right if the field isn't a field (or in other words unless our candidate is actually prime). The proof has to be applied recursively to prove the order of the test group is itself prime. Take your pick of redundant WP articles for a more technical explanation. https://en.wikipedia.org/wiki/Primality_certificate#Atkin%E2%80%93Goldwasser%E2%80%93Kilian%E2%80%93Morain_certificates https://en.wikipedia.org/wiki/Primality_certificate#Atkin%E2... https://en.wikipedia.org/wiki/Elliptic_curve_primality https://en.wikipedia.org/wiki/Elliptic_curve_primality
- throwaway81523 4y agoI wonder if the AKS algorithm might have been faster for numbers of this size.
- nullc 4y agoAKS doesn't produce a certificate so it would make the computation much less useful. Verifying a ECPP certificate is faster than running AKS for sure. Someone could go around claiming to have proved numbers prime with AKS when really they just passed strong Baillie-PSW ... if someone ever caught their fraud they'd at least make an important discovery of a Baillie-PSW pseudoprime. :)
- pbsd 4y agoYou can do the same thing with modular exponentiation, i.e. Pocklington's primality proving, but that requires finding a large factor of N-1, which is not easy in general. With elliptic curves you get as many shots at finding a group order with a large factor as you want, since if you fail the current attempt you can simply try another curve with a different order. So you can keep trying until you find a curve that has an easy to find large group order factor which, as it turns out, happens in probabilistic polynomial time.
- nullc 4y agodecimal repunit primes seem weird and less fundamental to me than binary repunit primes. does this make me weird?
- boston_clone 4y agonah, not at all - every Mersenne prime is a binary repunit. i always thought those and prime pairs were the coolest.
- psychoslave 4y agoDepends on your definition of weird. Someone who cares about primes in any way is already off of the mainstream charts to begin with.
- nullc 4y agoI dunno, primes are extremely useful!
- jl6 4y agoIn other mersenne news, it has now been the longest ever wait for the discovery of a new largest mersenne prime since the GIMPS project started (nearly 4 years now): https://www.mersenne.org/report_milestones/ https://www.mersenne.org/report_milestones/
- Someone 4y agoThis isn’t a Mersenne prime. https://www.ams.org/journals/mcom/2002-71-238/S0025-5718-01-01319-9/S0025-5718-01-01319-9.pdf https://www.ams.org/journals/mcom/2002-71-238/S0025-5718-01-... says “The Repunit R49081 = (10⁴⁹⁰⁸¹ − 1)/9 is a probable prime.”, so we’re talking numbers that get written as all ones in decimal, not binary.
- jl6 4y agoI’m referring to the forum name.
- andyjohnson0 4y agoQuestion for any mathematicians here: are properties of numbers that relate to their representation in particular number bases considered interesting or useful by mathematicians? I ask because the wikipedia page for repunit (a term I wasn't familiar with before) implies that it is in the domain of recreational mathematics. So my question refers to professional / non-recreational mathematicians.
- btdmaster 4y agoPrimality proof (which you can download!) is 114,314,839 bytes: http://factordb.com/index.php?id=1100000000013937242 http://factordb.com/index.php?id=1100000000013937242 (check section Primality)
- mi_lk 4y agopotentially stupid: what's the point of finding the prime number this big and why do we keep trying to calculate the next one
- mpreda 4y agoFirstly, this prime number is not so big compared to other big prime numbers, such as e.g. the largest known prime, 2^82589933 - 1, which has about 82 million bits. About the why.. well when we'll meet the aliens, for sure it'll come down to "who has the largest prime..", and we don't want to disappoint. https://www.mersenne.org/primes/ https://www.mersenne.org/primes/