Thread for posting tiny primes

[science_man_88]

Originally Posted by CRGreathouse

I'm not sure what you're saying. Do you have an example of a prime larger than 10^1999 which does not qualify for #19?*

* Or should I say, #19 as of 07 Sep 10 08:41 PM, since these definitions are fairly malleable.

see (2.5*10^1999)*2^2+c = 10^2000 + c so just find all c that give primes and then check for the special forms he doesn't allow.


forstep(n=1,100,2,if(isprime(10^2000+n),print(n))) is what I've been using up to you what n you search.

[CRGreathouse]

OK, so #19 as stated definitely covers precisely those primes greater than 10^1999. It suffices to use and b = n = 2.

[science_man_88]

Originally Posted by CRGreathouse

OK, so #19 as stated definitely covers precisely those primes greater than 10^1999. It suffices to use and b = n = 2.

I never knew that it had a covering set and my code doesn't give 101,103 because i start at 10^2000 not 10^1999 but pretty much.

[CRGreathouse]

Originally Posted by science_man_88

I never knew that it had a covering set and my code doesn't give 101,103 because i start at 10^2000 not 10^1999 but pretty much.

4N + 1 and 4N + 3 cover all primes > 2, right? So do that with 4N + 101 and 4N + 103.

10^1999 is the first 2000-digit number, just like 10^9 is the first 10-digit number.

[CRGreathouse]

I have verified the primality of 7984559573504259856359124657, a p28, through trial division.

[3.14159]

Originally Posted by Charles

I have verified the primality of 7984559573504259856359124657, a p28, through trial division.

I'm inclined to call bullshit, but, whatever, I won't bother. I'm busy looking for a 166350-digit prime anyway.

Odds: 1 in 7294.

So, 1 n 7294 candidates should be prime.

Each test should take about 10 minutes.

10 * 7294 = 72940 minutes ≈ 52 days.

Actually, it is 8.5 minutes. 8.5 * 7294 ≈ 43 days.

[CRGreathouse]

Originally Posted by 3.14159

I'm inclined to call bullshit, but, whatever, I won't bother.

That's your prerogative. I spent many hours trial-dividing (though, happily, my prediction on its timing was accurate -- I guessed the completion time within 5 minutes!).

Of course, your skepticism bolsters one of my points on this category: it's essentially unverifiable. By contrast, if we were using modern algorithms, we could provide certificates:

[2 5 1]

[3 3 1]

[11 3 1]

[103 3 1]

[149 2 1]

[9376643 3 1]

Someone proposed that you could ask for residues mod all the primes less than the square root of the number, but asymptotically that takes something like bits, or 32 TB in this case... using a mixed-radix method allows for smaller 'certificates', but I doubt the improvement is great.

[CRGreathouse]

Originally Posted by 3.14159

I'm busy looking for a 166350-digit prime anyway.

Odds: 1 in 7294.

If your base has no small prime factors, you must have sieved up to about 6 trillion to get odds that good.

[3.14159]

Originally Posted by Charles

If your base has no small prime factors, you must have sieved up to about 6 trillion to get odds that good.

I used b = 2, and indeed sieved to about 6.2 trillion.

[3.14159]

[2 5 1]

[3 3 1]

[11 3 1]

[103 3 1]

[149 2 1]

[9376643 3 1]

Quit using PARI, guy. It doesn't work for anything larger than 2000 digits.

[CRGreathouse]

Originally Posted by 3.14159

Quit using PARI, guy. It doesn't work for anything larger than 2000 digits.

Considering that the number has 28 digits, and 28 <= 2000, I think I was using the appropriate tool.

Basically, I'm interested in things that will expand my mind rather than simply test the speed of my CPU. When there's a good reason I'll use powerful tools outside of Pari, but for the most part if I need other tools I'm in the range of brute CPU calculations that I don't care about.