[QUOTE=CRGreathouse;223615]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...[/QUOTE]

Hmm.. That problem seems interesting.

[QUOTE=3.14159;223617]Hmm.. That problem seems interesting.[/QUOTE]

I posted it here:
[url]http://mathoverflow.net/questions/34197/are-all-primes-in-a-pap-3[/url]

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

[code]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
[/code]

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.

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.

[QUOTE=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.
[/QUOTE]

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

[QUOTE=3.14159;223707]

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.)[/QUOTE]

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.

[CODE]
% 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
[/CODE]

[QUOTE=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?
[/QUOTE]

By small, I mean about 10-30 digits.

[QUOTE=3.14159;223720]By small, I mean about 10-30 digits.[/QUOTE]

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.

[QUOTE=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.
[/QUOTE]

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.

So, far, I have sieved up to about 2.66 * 10[sup]12[/sup] + 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.

[QUOTE=3.14159;223739]The candidates left are about 1 in 14. I need to get rid of about 12900 more candidates to get 1 in 20.[/QUOTE]

Sure. Just sieve till 1.17*10^17