Функция Кармайкла не увеличивает k
Для любого числа функция Кармайкла возвращает 0 независимо от входных данных n.
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)))
Итак, как именно мне изменить функцию, чтобы эта проблема больше не возникала?
Что ты хочешь сделать с k? Каков ожидаемый результат camichael(n)?
Ожидаемый результат — это число Кармайкла n, по сути, наименьшее число из набора действительных целых чисел, которое имеет свойство a^m = 1 (mod n), справедливое для каждого целого числа, взаимно простого с n здесь
Прочтите stackoverflow.com/questions/47761383/proper-carmichael-function, а затем примените то, чему вас там учит, в контексте Lua?
Один из возможных способов — не «возвращаться после одного совпадения», а использовать переменную, чтобы проверить, не прервался ли цикл. Если он выходит за пределы цикла for без нарушения, то все взаимно простые числа удовлетворяют условию, в противном случае переход к следующему k. Однако я думаю о другой проблеме, а именно о том, превышает ли coprime^k максимальное целое число в Lua.
@Mike'Pomax'Kamermans единственный ответ на этот вопрос - это не "правильная" функция Кармайкла, поскольку она не гарантирует, что все взаимно простые числа соответствуют условию a^m%n=1, только один, что приводит к выводу функции всегда быть 0
Ответы 1
Я исправил код, добавив проверку, чтобы убедиться, что цикл не был нарушен, и изменил проверку, чтобы убедиться, что все взаимно простые числа соответствуют условию, используя k, и изменил значение присваивания k с 0 на 1, чтобы coprime^k%n не всегда вычислялось. до 1, потому что все числа в степени 0 дают 1. Модифицированный код:
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
Должно быть хорошо для меньших чисел, но если coprime^k приведет к очень большому числу, это может привести к странному поведению. Чтобы понять, что я имею в виду под «очень большим», попробуйте unsafe_int = 2^53; print(unsafe_int == unsafe_int+1), который печатает true. Все, что больше значения 9007199254740991 ссылка
Если
coprime = 1, то(coprime^k)%nравно 1, поэтому оно переходит в частьelseи простоreturn k