For any number, the Carmichael function returns 0
no matter what the input n
is.
function gcd(a, b)
if b == 0 then
return a
else
return (gcd(b,a%b))
end
end
function carmichael(n)
coprimes = {}
for i = 1,n-1 do
if gcd(i,n) == 1 then
table.insert(coprimes,i)
end
end
k = 0
while true do
for counter = 1,#coprimes do
coprime = coprimes[counter]
if (coprime^k)%n ~= 1 then
break
else
return k
end
k = k+1
end
end
end
input = io.read()
print(carmichael(tonumber(input)))
I fixed the code by adding a check to see if the loop was broken and modified the check to make sure that all coprimes met the condition using k
, and changed the assignment value of k
from 0
to 1
, so that coprime^k%n
does not always evaluate to 1, because all numbers to the power of 0
result in 1
. Modified code:
function carmichael(n)
coprimes = {}
for i = 1,n-1 do
if gcd(i,n) == 1 then
table.insert(coprimes,i)
end
end
totient = #coprimes
k = 1
while k <= totient do
notcarmichael = false
for counter = 1,#coprimes do
coprime = coprimes[counter]
if (coprime^k)%n ~= 1 then
notcarmichael = true
break
end
end
if not notcarmichael then
return k
else
k = k+1
end
end
return totient
end