R49081 Is Prime

https://mersenneforum.org/showpost.php?p=602219&postcount=35

by colinprince • 4 years ago

160 95 4 years ago

smoldesu• 4 years 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.

noduerme6• 4 years ago

I'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• 4 years ago

Prime 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.

calebrob6• 4 years ago

I'm not sure this is an application where using AI makes sense. For example, there are a large number of algorithmic ways to determine if a number of probably prime -- https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality...

l33t233372• 4 years ago

I 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?

jxf• 4 years ago

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.

I suspect it's because "an artificial intelligence that can identify primes for quicker testing" is a phrase that would probably be recognized by experienced developers in this space as a bad idea. There are already very good ways to identify prime candidates; no artificial intelligence is needed. They just take a while because even though they're very efficient, it takes a long time to operate on staggeringly huge numbers.

For a more relatable example, you can build an artificial intelligence that understands what you mean when you type "2 + 2". But this is a fantastically inefficient and expensive way to compute the value "4". Therefore, no one does this in a serious way. Even GPT-3, one of the more advanced commercially available models with hundreds of millions of parameters, struggles with multiplying two-digit numbers together (one study found a success rate of 20%).

squeaky-clean• 4 years ago

If we consider prime numbers above 1000 digits

  def is prime(n):
      return False

Would be 99.99% accurate.

The issue is without 100% certainty, there's not really any use for a "this is very likely probably prime" checker.

eesmith3• 4 years ago

Why unpopular? You wrote "can identify primes 99.999% of the time for quicker testing", which shows several fundamental and basic flaws in your understanding.

We've had approximate primarily testing methods for a long time and they are quite effective. See https://primes.utm.edu/notes/prp_prob.html (citing https://www.ams.org/journals/mcom/1989-53-188/S0025-5718-198... ), for a 100,000-digit number the odds of Fermat's test for compositeness being a false is 1.3E-10584, which is 99.9999999999999{insert 560 nines here}999999999%.

This is why, in the AMS paper cited as [1] in this link, Dubner wrote "it is virtually certain that R49081 is prime." The full context is:

In September 1999, it was discovered that R49081 is a probable prime. This was verified on several different computers with different software. Although it is virtually certain that R49081 is prime, it is necessary to prove rigorously that it is prime.

A 99.999%-likely test is far less virtually certain than the test used, and in any case doesn't achieve the goal of rigorously proving it's prime.

Even worse, these standard primality testing methods have a 0% false negative rate, while your hypothetical AI might miss actual repunits even with a 0.000001% rate.

just a form of embedded randomness, behind any irrational number like Pi

This doesn't makes sense. There are irrational numbers with no randomness, like Liouville's constant and the Champernowne constant. And there are plenty of patterns in primes - the Ulam spiral Wikipedia entry even compares the clearly apparent structure of that spiral to a random distribution, at https://en.wikipedia.org/wiki/Ulam_spiral .

Your comment therefore comes across as very ill-informed, and your doubling down doesn't help.

incompatible• 4 years ago

Certification is the creation of a proof that the number is prime (consisting of some related numbers), while the verification checks that the certification is correct?

saghm3• 4 years ago

I was thinking that "certification" referred to ensuring that the program they wrote to test it was correct, and then verifying was running it, but your interpretation makes sense too

segfaultbuserr• 4 years ago

Yes. In particular, "certification" refers to the fact that the proof is computationally difficult to create, but once it's created, it's easy for a third-party to check its correctness (insert your P/NP reference here).

https://en.wikipedia.org/wiki/Primality_certificate

noobermin• 4 years ago

I'm more surprised, assuming their algorithm is somewhat parallelizable, that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months.

EDIT: reading a wiki page, this sounds like recreational mathematics, not actual research math, which is a shame really

dspillett4• 4 years ago

that they couldn't run their algo on an actual supercomputer, it likely wouldn't have taken 20 months

I am assuming that is how the result was verified much faster - >1,000x the computer power used. Without looking deeper (like actually reading the article!) I couldn't say way that would be in this particular case, but such a disparity between power used to make a finding and power used to verify it by repetition is often the case when the initial result is discovered by a recreational researcher or small group, not a better funded group.

Not unlike the human scaling seen when one individual or a small group publishes a proof that could be significant, and many others poor over it to see if they can find a flaw before it is generally accepted as a genuine new finding (an order of magnitude or more of human brains to check, than to initially find).

pclmulqdq3• 4 years ago

This problem is also hard to parallelize. There is a lot of reuired communication between computation lanes (sections of the number), and the calculation takes a lot of dependencies on that communication.

You could probably design a supercomputer specifically for prime searches, but it would be a weird one.

jakelazaroff• 4 years ago

Can someone ELI5 this post?

layer82• 4 years ago

R49081 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.

krasin2• 4 years ago

Edit: 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

loeg• 4 years ago

I don't think any of you have met five year olds.

mastazi• 4 years ago

I knew nothing about Repunit numbers until a few minutes ago. So far, the most interesting bit for me was that:

As of March 2022, the largest known prime number 282,589,933 − 1, the largest probable prime R8177207 and the largest elliptic curve primality prime R49081 are all repunits.

Source https://en.wikipedia.org/wiki/Repunit

romellem• 4 years ago

So this number is prime? Cool.

  const R49081 = BigInt('1'.repeat(49081));

pxmpxm• 4 years ago

Is there a practical applicate for this, or is that more of a large pizza problem? https://pbs.twimg.com/media/CHtVwLXXAAAeKR6?format=jpg&name=...

kristopolous3• 4 years ago

Apparently it's just that number of 1s followed by each other as a number.

https://en.wikipedia.org/wiki/Repunit

It's part of "recreational mathematics" which solves a longstanding question I've had after finding out about a "special" set of numbers that make me think "What the hell was that?"

Basically the question was "Why can't I just come up with any dumb rule I want? Like the number of letters in the number being equal to the number of digits in the base ten representation or some other noise like the number of toothpicks required to represent it in decimal and then do some wacky proofs regarding "toothpick count"?" Apparently the answer is "well you can!"

Alright then. There exists a non-serious branch of math.

defrost2• 4 years ago

There exists a non-serious branch of math.

This remains an unproven conjecture that many hope to be true . . .

schoen• 4 years ago

Like the number of letters in the number being equal to the number of digits in the base ten representation

You might not be happy that someone investigated this because you apparently made up this example in order to make fun of this kind of question, but I looked into this a little bit and it's more subtle than I first thought.

The typical random integer small enough to have a well-defined English name (following Guy and Conway's prefixes at https://en.wikipedia.org/wiki/Names_of_large_numbers#Extensi... which will go up to 10³⁰⁰⁰-1) has a significantly longer English name than its decimal expansion. E.g. if we take fifty random digits like

96689907044105050355231217362382284051155144740067

the name of this number is "ninetysixquindecillionsixhundredeightyninequattuordecillionninehundredseventredecillionfortyfourduodecilliononehundredfiveundecillionfiftydecillionthreehundredfiftyfivenonilliontwohundredthirtyoneoctilliontwohundredseventeenseptillionthreehundredsixtytwosextillionthreehundredeightytwoquintilliontwohundredeightyfourquadrillionfiftyonetrilliononehundredfiftyfivebilliononehundredfortyfourmillionsevenhundredfortythousandsixtyseven"

or 430 letters, while the number is written with only 50 digits.

For small numbers, the closest approach between the lengths of the two is 10 (len("ten") == 3, len("10") == 2). And the typical word length grows faster than the digit length.

But the lengths do cross over many times up in the illions, as the illion terminology is unusually short compared to the size of the number described. Specifically, the smallest integer where this occurs is 1,000,000,000, where len("onebillion") == len("1000000000"). That's the smallest member of your set.

There are other examples such as 10¹³+1, 10¹³+2, 10¹³+6:

len("tentrillionone") == len("tentrilliontwo") == len("tentrillionsix") == len("10000000000001")

And there are many more further out into the illions.

For any example in which "one", "two", or "six" appears in the name of a number, any of the others can be substituted and the property will still hold. Likewise for "four"-"five"-"nine" and "three"-"seven"-"eight".

nullc5• 4 years ago

There exists a non-serious branch of math.

Try paging through OEIS sometime... https://oeis.org/

There are many seemingly silly bits of math. However, the answer in mathematics is often not the most interesting part (or even interesting at all), and a lot of important mathematics was created to produce answers for seemingly silly or pointless questions.

If you have a silly math problem and it's answered quickly-- well then it didn't waste much time. If you have a silly math problem and it's fiendishly hard to solve, then the discoveries that lead to the solution aren't silly-- they teach us how to do something we didn't know how to do before and may have important and useful implications.

For things like these primarily proofs the mathematical discoveries have already happened (at least until someone comes up with a new one!)-- and the ongoing effort is in engineering for numerical software and the IT work required to manage the computation in a cost effective manner.

Some families of primes have important mathematical structure that has a lot of known consequences, special algorithms that work with them (such as repunit primes in base 2), etc. Other's don't, or at least don't have any that we know of yet-- but they still divide up the literally infinite space of primes and give people interested in studying them a subset they can focus on.

IIAOPSW• 4 years ago

Its not just any old dumb rule. Say I wanted to make something really unlikely to be divisible. Well, let's try taking something very large and very evenly divisible, and then add or subtract a 1 so that it's always just a tiny fraction off from being divisible. In the addition case we might get something like 10000001. In the subtraction case for the same number we would get 9999999, after which we could factor out 9 to get 1111111. You could also do it with numbers that don't line up with base 10. 360 is a highly divisible number (hence its use for angles) but 361 / 359 are going to be 1/360th out of step with those divisors (and in fact, 359 is prime).

So, for this reason, a repeating sequence of 1s is a natural choice to try and find prime numbers.

softdevca• 4 years ago

I may have misconstrued that ELI5 was snark for "elide", in the same vein as I18N or A11Y.

Present me wishes I could explain Explain ELI5 Like I'm 5 to my past self.

charles_f• 4 years ago

Biiiiiig number with only 1s is magical and doesn't fear the other numbers to cut it in bits and pieces, which is awesome and exciting because it's fun. Daddy only hopes it's got a solid self estime and doesn't hang out too much in those shady unary parts of the universe

quickthrower25• 4 years ago

Question: how does the density of R(x) primes, with respect to x, compare to the density of primes. Are they the same?

Someone2• 4 years ago

We don’t even know whether there are infinitely many decimal Repunit primes (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). 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.

quickthrower25• 4 years ago

Thanks 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.

dragontamer5• 4 years ago

R49081 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• 4 years ago

These are "repunit" primes, meaning that it's the digit "1" repeated N times, in this case 49081 times. So yes 20KB.

dspillett4• 4 years ago

47.9KiB in fact, assuming we are using 8-bits to the byte.

mpreda2• 4 years ago

For the mersenne project (searching for prime numbers that are 110 million bits in size) GPUs are quite efficient.

One of the algorithms used, called PRP (probable prime), which uses the reciprocal of Fermat's little theorem (a^(p-1)==1 mod p if p is prime) involves computing 3^p mod p (where p is a 110million bits number). This is called "modular exponentiation", and is done efficiently with FFTs (Fast Fourrier Transform, used to implement multiplication, thus squaring).

The FFT of 110Mbits can be implemented efficiently on GPUs. The key for keeping the hot data in GPU registers or caches is "locality of data access". Although the FFT algorithm is non-local by excellence (has a tendency to access all the data all the time), it can be split into "blocks" which have a smaller hot-data size. And this allows efficient GPU implementations.

The problem with R49081 may be that it's a small number, thus hard to fill all the processing units of the GPU with the amount of parallel work the algo offers at this size. Another problem may be that the algorithm involving eliptic-curves is more complex, thus more work is needed to express it in GPU terms.

http://mersenne.org/

dragontamer5• 4 years ago

The problem with R49081 may be that it's a small number, thus hard to fill all the processing units of the GPU with the amount of parallel work the algo offers at this size. Another problem may be that the algorithm involving eliptic-curves is more complex, thus more work is needed to express it in GPU terms.

Well, 20kB is small, but also large. Too large to fit inside of 32-bit registers on the GPU (or even in 200+ such registers), too small to really take advantage of the GPU's much faster VRAM.

Its an interesting size. Larger primes almost certainly would benefit from a GPU no doubt. Smaller primes also would benefit from GPU (see cryptocurrency miners, where the entire program fits inside of a singular shader).

20kB though? Its... a weird size. Very interesting. If it were much bigger, or smaller, I'd be confident about porting the algorithm over to the GPU. But its actually more intimidating to be at that size (especially since 64kB L1 caches of CPUs is so darn good).

If I were forced to do this in GPU space, I'd have one-workgroup per number. I'd hope that the majority of the compute-time were spent on multiplication/division routines that would benefit from all 1024-threads (maxed size workgroup). But it'd be a more difficult program to write than a larger or smaller number.

retconn• 4 years ago

Intel is offering customer silicon on their latest architecture. So you could be ambitious and design your own block with as much SRAM as you can sacrifice other accelerator units for, depending on routing latency.

Edit: customer not custom, small difference but important if you're asking..

dragontamer5• 4 years ago

Custom / semi-custom is probably an old Altera FPGA kinda thing, which means verilog (or similar hardware-level programming languages), which is much more difficult to use in my experience.

I generally see the "compute" hierarchy as:

1. General Purpose CPUs -- easiest.

2. CPU acceleration -- AVX512, NEON, SVE, etc. etc. Specialized CPU instructions that only exist on certain versions of hardware.

3. General Purpose GPU -- OpenCL, DirectCompute, ROCm, CUDA. General purpose GPU instructions that work on a wide variety of hardware.

4. GPU accelerated units -- Raytracing, matrix-multiplication, bfloat16 support, wave intrinsics. I guess DirectX12 Ultimate has these but you definitely need to be checking to see if your hardware supports this before using them.

5. FPGAs -- Over here baby, but much much harder than #4 in practice.

-------

I know Intel has FPGA + Intel core chips, and that Microsoft has used them before for Bing search and other such projects. But no one ever told me it was easy.

Gordonjcp• 4 years ago

R49081 means this was a ~49081 digit number, or a number that could be represented in maybe 163043-ish bits or ~20kB or so?

A single (very large) number, that I could not represent on any computer I owned until Christmas morning 1983.

Mad.

jl2718• 4 years ago

This 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.

nullc5• 4 years ago

My 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...

https://en.wikipedia.org/wiki/Elliptic_curve_primality

throwaway81523• 4 years ago

I wonder if the AKS algorithm might have been faster for numbers of this size.

pbsd• 4 years ago

You 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.

nullc5• 4 years ago

decimal repunit primes seem weird and less fundamental to me than binary repunit primes.

does this make me weird?

boston_clone• 4 years ago

nah, not at all - every Mersenne prime is a binary repunit. i always thought those and prime pairs were the coolest.

psychoslave• 4 years ago

Depends on your definition of weird. Someone who cares about primes in any way is already off of the mainstream charts to begin with.

nullc5• 4 years ago

I dunno, primes are extremely useful!

jl62• 4 years ago

In 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/

Someone2• 4 years ago

This isn’t a Mersenne prime.

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.

jl62• 4 years ago

I’m referring to the forum name.

andyjohnson0• 4 years ago

Question 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• 4 years ago

Primality proof (which you can download!) is 114,314,839 bytes: http://factordb.com/index.php?id=1100000000013937242 (check section Primality)

mi_lk• 4 years ago

potentially stupid: what's the point of finding the prime number this big and why do we keep trying to calculate the next one

mpreda2• 4 years ago

Firstly, 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/

R49081 Is Prime

Related Stories