74 lines
2.1 KiB
Text
74 lines
2.1 KiB
Text
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
|