local int = require "int"
local fmt = require "fmt"
require "bignum"

local circs = {}

local function is_circular(n)
    local nn = n
    local pow = 1  -- will eventually contain 10 ^ d where d is number of digits in n
    while nn > 0 do
        pow *= 10
        nn //= 10
    end
    nn = n
    while true do
        nn *= 10
        local f = nn // pow  -- first digit
        nn += f * (1 - pow)
        if nn in circs then return false end
        if nn == n then break end
        if !int.isprime(nn) then return false end
    end
    return true
end

print("The first 19 circular primes are:")
local digits = {1, 3, 7, 9}
local q = {1, 2, 3, 5, 7, 9}   -- queue the numbers to be examined
local fq = {1, 2, 3, 5, 7, 9}  -- also queue the corresponding first digits
local count = 0
while true do
    local f = q[1]    -- peek first element
    local fd = fq[1]  -- peek first digit
    if int.isprime(f) and is_circular(f) then
        circs:insert(f)
        count += 1
        if count == 19 then break end
    end
    q:remove(1)   -- pop first element
    fq:remove(1)  -- ditto for first digit queue
    if f != 2 and f != 5 then  -- if digits > 1 can't contain a 2 or 5
        -- add numbers with one more digit to queue
        -- only numbers whose last digit >= first digit need be added
        for digits as d do
            if d >= fd then
                q:insert(f * 10 + d)
                fq:insert(fd)
            end
        end
    end
end
fmt.lprint(circs)

print("\nThe next 4 circular primes, in repunit format, are:")
count = 0
mpz.init()
local rus = {}
local primes = int.primes(10_000)
local repunit
for i = 4, #primes do
    local p = primes[i]
    repunit = bigint.new(string.rep("1", p))
    if mpz.isprobableprime(repunit) then
        rus:insert($"R({p})")
        count += 1
        if count == 4 then break end
    end
end
fmt.lprint(rus)
print("\nThe following repunits are probably circular primes:")
for {5003, 9887, 15073, 25031, 35317, 49081} as i do
    repunit = bigint.new(string.rep("1", i))
    fmt.print("R(%-5d) : %s", i, mpz.isprobableprime(repunit))
end