Thread for posting tiny primes

[3.14159]

Originally Posted by CRGreathouse

Ah. I assumed you meant something nonobvious: that every odd prime was a member of a finite arithmetic progression of primes (with 3+ terms). Clearly every integer is in the arithmetic progression with common difference 1...

Hmm.. That problem seems interesting.

[CRGreathouse]

Originally Posted by 3.14159

Hmm.. That problem seems interesting.

I posted it here:
http://mathoverflow.net/questions/34...mes-in-a-pap-3

[3.14159]

My setup on Python for listing numbers that have no factors below a given prime number, in a given range: Note that n > largest prime listed

for n in range(1, 700):
	if n%2 !=0 and n%3 != 0 and n%5 != 0 and n%7 != 0 and n%11!= 0 and n%13 != 0 and n%17 != 0 and n%19 != 0 and n%23 != 0:
		print n

The obvious problem: Expression becomes too long even before I have used only the first 10 primes. I attempted if n%(2, 3, 5, 7, 11, 13, 17, ..) != 0, print n, but got a syntax error.

[CRGreathouse]

So either use a wheel sieve (dividing by, say, 30n + {1,7,11,13,17,19,23,29} in addition to the primes dividing the wheel, in this case 2,3,5) or make an array of small primes and loop through it.

[3.14159]

Originally Posted by CRGreathouse

So either use a wheel sieve (dividing by, say, 30n + {1,7,11,13,17,19,23,29} in addition to the primes dividing the wheel, in this case 2,3,5) or make an array of small primes and loop through it.

A wheel sieve: Pseudocode?

Also: A recommended list of programs for small primes? (I currently prove small primes via trial division or Miller-Rabin, in two separate applets. (About 30-60 iterations). Sadly, the latter applet cannot handle Proth numbers.)

[bsquared]

Originally Posted by 3.14159

Also: A recommended list of programs for small primes? (I currently prove small primes via trial division or Miller-Rabin, in two separate applets. (About 30-60 iterations). Sadly, the latter applet cannot handle Proth numbers.)

More info... How small is small? Do you want to generate a list of them? Prove an existing list of them? Only of special form?

YAFU can give you a list of primes in any range you want up to 4*10^18... of course I'd keep the range smallish (1 billion or less) unless you have equal (and very great) amounts of patience and hard disk space.

% time yafu "primes(0,1000000000,0)" -pfile

ans = 50847534

10.188u 1.249s 0:16.31 70.0%    0+0k 0+0io 0pf+0w

% tail primes.dat
999999733
999999739
999999751
999999757
999999761
999999797
999999883
999999893
999999929
999999937

[3.14159]

Originally Posted by bsquared

More info... How small is small? Do you want to generate a list of them? Prove an existing list of them? Only of special form?

By small, I mean about 10-30 digits.

[CRGreathouse]

Originally Posted by 3.14159

By small, I mean about 10-30 digits.

Proving the primality of a 30-digit number by trial division would take ~ pi(10^30) = 29844570422669 stored primes, which would take 217 TB @ 64 bits each.

[3.14159]

Originally Posted by CRGreathouse

Proving the primality of a 30-digit number by trial division would take ~ pi(10^30) = 29844570422669 stored primes, which would take 217 TB @ 64 bits each.

I use Miller-Rabin for those proofs. And, the app divides by any odd number that ends in 1, 3, 7, or 9, regardless of whether or not it is prime.

[3.14159]

So, far, I have sieved up to about 2.66 * 10¹² + 1 in NewPGen, while searching for a 66893 to 66896-digit prime. The candidates left are about 1 in 14. I need to get rid of about 12900 more candidates to get 1 in 20.

[axn]

Originally Posted by 3.14159

The candidates left are about 1 in 14. I need to get rid of about 12900 more candidates to get 1 in 20.

Sure. Just sieve till 1.17*10^17