 # Generate Sorcerean Primes

May 21st, 2020
2,542
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. 'Generate Sorcerean Primes
2. '-------------------------
3. 'Numbers whose residues are prime after being reduced modulo 2^n, for any n.
4. '1 is considered prime, for consistency. :)
5.
6. 'eg, 107 --> 43 (mod 64) --> 11 (mod 32 mod 16) --> 3 (mod 8 mod 4) --> 1 (mod 2)
7.
8. _DEFINE A-Z AS _UNSIGNED _INTEGER64
9.
10. PRINT "Generating powers..."
11. DIM pow(63)
12. pow(0) = 1: FOR i = 1 TO 63: pow(i) = pow(i - 1) * 2: NEXT
13.
14. PRINT "Generating small primes...";
15. DIM pr(99999)
16. pr(0) = 2: pr(1) = 3: pr(2) = 5
17. i = 2: n = 5
18. WHILE i <= 99999
19.   GOSUB ptest
20.   IF f = 1 THEN pr(i) = n: i = i + 1
21.   IF n MOD 6 = 1 THEN n = n + 4 ELSE n = n + 2
22. WEND
23. PRINT pr(99999)
24.
25. PRINT "Generating Sorcerean primes..."
26. PRINT 1; 3;
27. a = 5
28. DO
29.   b = INT(LOG(a) / LOG(2) + 1.5) 'estimate bits needed to represent n
30.   FOR i = 1 TO b
31.     n = a MOD pow(i)
32.     GOSUB ptest
33.     IF f = 0 THEN i = b
34.   NEXT
35.   IF f = 1 THEN PRINT a;
36.   IF a MOD 6 = 1 THEN a = a + 4 ELSE a = a + 2
37. LOOP
38.
39. ptest:
40. f = 1
41. s = SQR(n)
42. j = 0: DO
43.   IF n MOD pr(j) = 0 THEN f = 0
44.   j = j + 1
45. LOOP WHILE pr(j) <= s AND f = 1
46. RETURN