mathluagreatest-common-divisor

Carmichael function not incrementing k


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)))

Solution

  • 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