| 123456789101112131415161718192021222324252627282930313233343536373839404142434445 |
- #!/usr/bin/ruby
- # Recursively generate Fermat pseudoprimes to base 2, using primes of the form k*z + 1,
- # where z is the multimplicative order: znorder(2, n) and n and k are positive integers.
- var seen = Set()
- var PRIME_LIMIT = 1e6
- func generate_fermat_from_znorder(n) is cached {
- var z = znorder(2, n)
- #z < 3427425 || return nil
- #z < 4e6 || return nil
- z < PRIME_LIMIT || return nil
- for k in (1..1000) {
- var p = (z*k + 1)
- #p < 7e3 || break
- p < PRIME_LIMIT || break
- p.is_prime || next
- n.is_div(p) && next
- for r in (n.divisors(1e5)) {
- next if (r == n)
- var t = (n/r * p)
- if (t.is_psp && !seen.has(t)) {
- say t
- seen << t
- __FUNC__(t)
- }
- }
- }
- return nil
- }
- DATA.slurp.nums.each {|n|
- generate_fermat_from_znorder(n)
- }
- __DATA__
- 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68 69 70 72 74 75 76 77 78 80 81 82 84 85 86 87 88 90 91 92 93 94 95 96 98 99 100 102 104 105 106 108 110 111 112 114 115 116 117 118 119 120 121 122 123 124 125 126 128 129 130 132 133
|
