61 lines
1.6 KiB
Text
61 lines
1.6 KiB
Text
require "bignum"
|
|
require "table2"
|
|
local fmt = require "fmt"
|
|
|
|
local min = 3
|
|
local max = 10
|
|
local zero = bigint.zero
|
|
local fact = zero
|
|
local factors = table.rep(max, 0)
|
|
local big_factors = table.rep(max, zero)
|
|
mpz.init()
|
|
|
|
local function is_prime_pretest(k)
|
|
if k % 3 == 0 or k % 5 == 0 or k % 7 == 0 or k % 11 == 0 or
|
|
k % 13 == 0 or k % 17 == 0 or k % 19 == 0 or k % 23 == 0 then
|
|
return k <= 23
|
|
end
|
|
return true
|
|
end
|
|
|
|
local function ccfactors(n, m)
|
|
if !is_prime_pretest( 6 * m + 1) then return false end
|
|
if !is_prime_pretest(12 * m + 1) then return false end
|
|
factors[1] = 6 * m + 1
|
|
factors[2] = 12 * m + 1
|
|
local t = 9 * m
|
|
local i = 1
|
|
while i <= n - 2 do
|
|
local tt = (t << i) + 1
|
|
if !is_prime_pretest(tt) then return false end
|
|
factors[i + 2] = tt
|
|
i += 1
|
|
end
|
|
for j = 1, n do
|
|
fact = bigint.new(factors[j])
|
|
if !mpz.isprobableprime(fact, 15) then return false end
|
|
big_factors[j] = fact
|
|
end
|
|
return true
|
|
end
|
|
|
|
local function ccnumbers(start, finish)
|
|
for n = start, finish do
|
|
local mult = 1
|
|
if n > 4 then mult = 1 << (n - 4) end
|
|
if n > 5 then mult *= 5 end
|
|
local m = mult
|
|
while true do
|
|
if ccfactors(n, m) then
|
|
local num = big_factors:slice(1, n):prod()
|
|
fmt.print("a(%d) = %s", n, num)
|
|
fmt.print("m(%d) = %s", n, m)
|
|
fmt.print("Factors: %,s\n", factors:slice(1, n))
|
|
break
|
|
end
|
|
m += mult
|
|
end
|
|
end
|
|
end
|
|
|
|
ccnumbers(min, max)
|