Is (2^82589933-243)/19^2 prime?

[dcheuk]

Originally Posted by GP2

Most programming languages (other than C and C++) have modular exponentiation library functions.

For instance, in Python: pow(2,82589933,19*19) gives 243

Most of the time I wonder how these functions are programmed, I would imagine they have the best programmers working on them to ensure high efficiency and speed, probably no one except themselves would understand what is going on.

I need to read that book on Fourier transform still lol been slacking.

[Batalov]

Originally Posted by CRGreathouse

I assume your bet is that the number is composite?

Good catch! These days people constantly change their own posts.
It's a good thing that they cannot change the title.

mersenneforum.org > Extra Stuff > Blogorrhea > enzocreti > Is (2^82589933-243)/19^2 prime?

Originally Posted by Batalov

Bet you $100 against your 1 lira that it isn't.

Unfortunately, because of the primary behavior (some people change their posts), many others started (secondary to that) all the time quoting the page-long posts, ...only to answer then, "Yes".

[CRGreathouse]

Originally Posted by dcheuk

Most of the time I wonder how these functions are programmed, I would imagine they have the best programmers working on them to ensure high efficiency and speed, probably no one except themselves would understand what is going on.

Well, the kinds of people who hang out here would often understand them.

[Batalov]

Originally Posted by dcheuk

Most of the time I wonder how these functions are programmed, ...

I need to read that book on ...

Yes!
Well in this case one thing is not connected to the other. mod exponentiation for factoring has no Fourier in it. But if you are willing to read the book - absolutely! Regardless!

[CRGreathouse]

Is (2^82589933-243)/19^2 prime?

Originally Posted by Batalov

Bet you $100 against your 1 lira that it isn't.

Let me explain Serge's bet, for those who might be curious. If we came across a number N = (2^82589933-243)/361 and we knew nothing about it, we might guess that it was prime with 'probability' 1/log N or about 0.000000017. Of course either it is prime or it isn't, but without calculating this gives us a way to play the odds based only on its size: most numbers that big are composite.

But if we realized that N is odd, we should take this into account: it makes it twice as likely to be prime, or about 0.000000035. Checking that it's not a multiple of 3, we now know that it's 3/2 as likely to be prime, since normally only 2 out of every 3 pass this test.

But enzocreti knows more: it's not divisible by any prime up to 4e9. This means we can multiply its chances by 2/1 * 3/2 * 5/4 * ... * 3999999979/3999999978. But that's getting a bit tedious, so we use one of Mertens' theorems and approximate this as e^gamma * log(4e9) = 36.9.... (Note that Euler's constant gamma is implemented in PARI/GP as Euler.) So that bumps the chances all the way up to 0.00000064.

Had enzocreti instead gone up to 10^20, the probability could have been improved to 0.0000014. But I'd still bet with Serge.

[axn]

This number is sufficiently small that it can be PRP tested (using, say, P95) in a few core-week's time.

So the answer to "could you prove..." is "do it yourself".

[dcheuk]

Originally Posted by CRGreathouse

Well, the kinds of people who hang out here would often understand them.

It is truly amazing that there are brilliant people that can make these algorithms up, so is the ability to read dense and compact codes someone else wrote and fully comprehend the algorithms that was used.

Originally Posted by Batalov

Yes!
Well in this case one thing is not connected to the other. mod exponentiation for factoring has no Fourier in it. But if you are willing to read the book - absolutely! Regardless!

It is always fun to learn something new in math, especially things related to nt.

I am going through a book currently that explains quite a lot on computational number theory (mostly factoring, it's probably very basic for you guys) - The Joy of Factoring by Wagstaff.

I have the Fourier Analysis book by Stein on a corner somewhere, was planning to read it after finish his books on real and functional analysis, but progress has been slow lol.

There're way too much math to learn, read and digest ... and everything is so dense

[LaurV]

Originally Posted by CRGreathouse

Let me explain ...

+1

[enzocreti]

8#*2#*5#*8#*9#*9#*3#*3# - 82589933 is prime!
What is 82589933?
Obviously this my curio was published in Chris Caldwell page!

And just now I realized it is a prime p such that 2p-1 is also prime!

[enzocreti]

8401414020133=2*(8#*2#*5#...*3#-82589933)-1 is prime

and 8401414020133+/- 84(the two first digits of the prime) are primes!

[enzocreti]

8#*2#*5#...*3#-82589933 is a prime such that 2p-1 is also prime!


Do you guess what is 82589933?
The exponent of the last greatest Mersenne prime!