Sorceress

Generate Sorcerean Primes

May 21st, 2020
1,620
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
RAW Paste Data