Compute the Carmichael function

Question

Task description

In number theory, the Carmichael function λ takes a positive integer n and returns the least positive integer k so that the k-th power of each integer coprime to n equals 1 modulo n.

Given a positive integer n, your solution must compute λ(n). The shortest code in bytes wins.

Your program should theoretically work for arbitrarily large inputs, but doesn’t need to be efficient.

Tips

The sequence of all λ(n) is OEIS A002322.

An ungolfed Python implementation would look like

from fractions import gcd

def carmichael(n):
    coprimes = [x for x in range(1, n) if gcd(x, n) == 1]
    k = 1
    while not all(pow(x, k, n) == 1 for x in coprimes):
        k += 1
    return k

(In Python, pow(A, B, C) efficiently computes pow(A, B) % C.)

Test cases

Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500

Answer 1

Mathematica, 16 bytes

CarmichaelLambda

Well...

Answer 2

Python, 76 73 67 bytes

f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)

Try it online!

A further byte could be saved by returning True instead of 1.

Alternative implementation

Using the same approach, there is also the following implementation by @feersum which doesn't use list comprehensions.

f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)

Note that this implementation requires O(n^λ(n)) time. Efficiency could be improved dramatically while actually decreasing score to 66 bytes, but the function would return True for input 2.

f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)

Background

Definitions and notation

All employed variables will denote integers; n, k, and α will denote positive integers; and p will denote a positive prime.

a | b if b is divisible by a, i.e., if there is q such that b = qa.

a ≡ b (mod m) if a and b have the same residue modulo m, i.e., if m | a - b.

λ(n) is the smallest k such that a^k ≡ 1 (mod n) – i.e., such that n | a^k - 1 – for all a that are coprime to n.

f(n) is the smallest k such that a^2k+1 ≡ a^k+1 (mod n) – i.e., such that n | a^k+1(a^k - 1) – for all a.

λ(n) ≤ f(n)

Fix n and let a be coprime to n.

By the definition of f, n | a^f(n)+1(a^f(n) - 1). Since a and n do not have a common prime factor, neither do a^f(n)+1 and n, which implies that n | a^f(n) - 1.

Since λ(n) is the smallest integer k such that n | a^k - 1 for all integers a that are coprime to n, it follows that λ(n) ≤ f(n).

λ(n) = f(n)

Since we've already established the inequality λ(n) ≤ f(n), it is sufficient to verify that k = λ(n) satisfies the condition that defines f, i.e., that n | a^λ(n)+1(a^λ(n) - 1) for all a. For this purpose, we'll establish that p^α | a^λ(n)+1(a^λ(n) - 1) whenever p^α | n.

λ(k) | λ(n) whenever k | n (source), so (a^λ(k) - 1)(a^λ(n)-λ(k) + a^λ(n)-2λ(k) + ⋯ + a^λ(k) + 1) = a^λ(n) - 1 and, therefore, a^λ(k) - 1 | a^λ(n) - 1 | a^λ(n)+1(a^λ(n) - 1).

If a and p^α are coprime, by the definition of λ and the above, p^α | a^λ(pα) - 1 | a^λ(n)+1(a^λ(n) - 1) follows, as desired.

If a = 0, then a^λ(n)+1(a^λ(n) - 1) = 0, which is divisible by all integers.

Finally, we must consider the case where a and p^α have a common prime factor. Since p is prime, this implies that p | a. Carmichael's theorem establishes that λ(p^α) = (p - 1)p^{α - 1} if p > 2 or α < 3 and that λ(p^α) = p^{α - 2} otherwise. In all cases, λ(p^α) ≥ p^{α - 2} ≥ 2^{α - 2} > α - 2.

Therefore, λ(n) + 1 ≥ λ(p^α) + 1 > α - 1, so λ(n) + 1 ≥ α and p^α | p^λ(n)+1 | a^λ(n)+1 | a^λ(n)+1(a^λ(n) - 1). This completes the proof.

How it works

While the definitions of f(n) and λ(n) consider all possible values of a, it is sufficient to test those that lie in [0, ..., n - 1].

When f(n, k) is called, it computes a^k+1(a^k - 1) % n for all values of a in that range, which is 0 if and only if n | a^k+1(a^k - 1).

If all computed residues are zero, k = λ(n) and any returns False, so f(n, k) returns 1.

On the other hand, while k < λ(n), 1-any(...) will return 0, so f is called recursively with an incremented value of k. The leading -~ increments the return value of f(n, k + 1), so we add 1 to f(n, λ(n)) = 1 once for every integer in [1, ..., λ(n) - 1]. The final result is thus λ(n).

Answer 3

Mathematica without built-in, 58 57 bytes

Thanks to Martin Ender for finding an error, then saving me the bytes it took to fix it!

Thanks to miles for saving 1 byte! (which seemed like 2 to me)

Built-ins are totally fine ... but for those who want to implement it without using brute force, here's a formula for the Carmichael function:

LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&

If p is a prime, the Carmichael function λ(p^r) equals φ(p^r) = (p-1)*p^(r-1)—except when p=2 and r≥3, in which case it's half that, namely 2^(r-2).

And if the prime-power factorization of n equals p1^r1 * p2^r2 * ..., then λ(n) equals the least common multiple of { λ(p1^r1), λ(p2^r2), ...}.

Runtime is one instant more than factoring the integer in the first place.

Answer 4

Templates Considered Harmful, 246 bytes

Fun<Ap<Fun<If<Eq<A<2>,T>,A<1>,And<Eq<Ap<Fun<If<A<1>,Ap<A<0>,Rem<A<2>,A<1>>,A<1>>,A<2>>>,A<1,1>,A<2>>,T>,Sub<Ap<Fun<Rem<If<A<1>,Mul<A<2,1>,Ap<A<0>,Sub<A<1>,T>>>,T>,A<1,2>>>,A<1>>,T>>,Ap<A<0>,Add<A<1>,T>,A<1,1>>,Ap<A<0>,A<1>,Sub<A<2>,T>>>>,T,A<1>>>

An unnamed function (not that there are named functions).

This is a forgotten esolang of mine which is interpreted by a C++ compiler instantiating templates. With the default max template depth of g++, it can do λ(35), but it can't do λ(101) (the lazy evaluation makes things worse).

Answer 5

Haskell, 57 56 bytes

f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0

Answer 6

Jelly, 2 bytes

Æc

Thank you for the builtin, @Lynn

Answer 7

Pyth - 19 18 17 bytes

One byte saved thanks to @TheBikingViking.

Straight up brute force.

f!sm*t.^dTQq1iQdQ

Try it online here.

Answer 8

Ruby, 59 56 bytes

->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}

Answer 9

J, 28 27 bytes

[:*./@(5&p:%2^0=8&|)2^/@p:]

The Carmichael function is λ(n) and the totient function is φ(n).

Uses the definition where λ(p^k) = φ(p^k)/2 if p = 2 and k > 2 else φ(p^k). Then, for general n = p₁^k₁ p₂^k₂ ⋯ p_i^k_i, λ(n) = LCM[ λ(p₁^k₁) λ(p₂^k₂) ⋯ λ(p_i^k_i) ].

Usage

Extra commands used to format multiple input/output.

   f =: [:*./@(5&p:%2^0=8&|)2^/@p:]
   f 530
52
   (,.f"0) 1 2 3 10 35 101 530 3010 6511 10000
    1    1
    2    1
    3    2
   10    4
   35   12
  101  100
  530   52
 3010   84
 6511 3056
10000  500

Explanation

[:*./@(5&p:%2^0=8&|)2^/@p:]  Input: integer n
                          ]  Identity function, get n
                    2   p:   Get a table of prime/exponent values for n
                     ^/@     Raise each prime to its exponent to get the prime powers of n
[:    (            )         Operate on the prime powers
                8&|            Take each modulo 8
              0=               Test if its equal to 0, 1 if true else 0
            2^                 Raise 2 to the power of each
       5&p:                    Apply the totient function to each prime power
           %                   Divide it by the powers of 2
  *./@                       Reduce using LCM and return

Answer 10

Actually, 30 28 25 19 26 bytes

The Carmichael function, λ(n) where n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, is defined as the least common multiple (LCM) of λ(p_i**k_i) for the maximal prime powers p_i**k_i that divide into n. Given that for every prime power except where the prime is 2, the Carmichael function is equivalent to the Euler totient function, λ(n) == φ(n), we use φ(n) instead. For the special case of 2**k where k ≥ 3, we just check if 2**3 = 8 divides into n at the beginning of the program, and divide by 2 if it does.

Unfortunately, Actually doesn't currently have an LCM builtin, so I made a brute-force LCM. Golfing suggestions welcome. Try it online!

;7&Yu@\w`iⁿ▒`M╗2`╜@♀%ΣY`╓N

Ungolfing

         Implicit input n.
;        Duplicate n.
7&       n&7 == n%8.
Yu       Logical NOT and increment. If n%8 == 0, return 2. Else, return 1.
@\       Integer divide n by 2 if n%8==0, by 1 otherwise.
          Thus, we have dealt with the special case where p_i == 2 and e_i >= 3.
w        Full prime factorization of n as a list of [prime, exponent] lists.
`...`M   Map the following function over the prime factorization.
  i        Flatten the array, pushing exponent, then prime to the stack.
  ⁿ▒       totient(pow(prime, exponent)).
╗        Save that list of totients in register 0.
2`...`╓  Get the first two values of n where the following function f(n) is truthy.
         Those two numbers will be 0 and our LCM.
  ╜@       Push the list in register 0 and swap with our n.
  ♀%       Get n mod (every number in the list)
  Σ        Sum the modulos. This sum will be 0, if and only if this number is 0 or LCM.
  Y        Logical NOT, so that we only get a truthy if the sum of modulos is 0.
N        Grab the second number, our LCM. Implicit return.

Answer 11

JavaScript (ES6), 143 135 bytes

Edit: saved 8 bytes thanks to Neil

An implementation using functional programming.

n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1

Ungolfed and commented

n =>                                          // Given a positive integer n:
  (A = [...Array(n).keys()])                  // Build A = [0 ... n-1].
  .find(k =>                                  // Try to find k in [1 ... n-1] such as
    k && !c.some(c =>                         // for each coprime c: c^k ≡ 1 (mod n).
      A.slice(0, k).reduce(y =>               // We use reduce() to compute
        y * c % n, 1                          // c^k mod n.
      ) - 1                                   // Compare it with 1.
    ),                                        // The list of coprimes is precomputed
    c = A.filter(x =>                         // before the find() loop is executed:
      (                                       // for each x in [0 ... n-1], keep
        g = (x, y) => x ? g(y % x, x) : y     // only integers that verify:
      )(x, n) == 1                            // gcd(x, n) = 1
    )                                         // (computed recursively)
  ) || 1                                      // Default result is 1 (for n = 1)

Demo

Although it does work for 6511 and 10000, I won't include them here as it tends to be a bit slow.

let f =
n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1

console.log(f(1));     // 1
console.log(f(2));     // 1
console.log(f(3));     // 2
console.log(f(10));    // 4
console.log(f(35));    // 12
console.log(f(101));   // 100
console.log(f(530));   // 52
console.log(f(3010));  // 84

Answer 12

Ruby, 101 86 91 90 bytes

A Ruby port of my Actually answer. Golfing suggestions welcome.

Edit: -4 bytes from removing a but +9 bytes from fixing a bug where 1 returned nil. -1 byte thanks to Cyoce.

require'prime'
->n{((n%8<1?n/2:n).prime_division<<[2,1]).map{|x,y|x**~-y*~-x}.reduce :lcm}

Ungolfing

require 'prime'
def carmichael(n)
  if n%8 < 1
    n /= 2
  end
  a = []
  n.prime_division.do each |x,y|
    a << x**(y-1)*(x-1)
  end
  return a.reduce :lcm
end

Answer 13

JavaScript (ES 2016) 149

Python reference implementation ported to JS. Some fancy Pyhton builtin is missing in js, like gcd and pow, and the array comprehension is not standard in ES 6. This works in Firefox.

n=>eval('for(g=(a,b)=>b?g(b,a%b):a,p=(a,b,c)=>eval("for(r=1;b--;)r=r*a%c"),c=[for(_ of Array(i=n))if(g(i--,n)<2)i+1],k=1;c.some(x=>p(x,k,n)-1);)++k')

Less golfed

n=>{
  g=(a,b)=>b?g(b,a%b):a
  p=(a,b,c)=>{ 
    for(r=1;b--;)
      r=r*a%c
    return r
  }
  c=[for(_ of Array(i=n)) if(g(i--,n)<2) i+1]
  for(k=1;c.some(x=>p(x,k,n)-1);)
    ++k
  return k
} 

Answer 14

Java8 38 19 + 287 295 253 248 241 = 325 333 272 267 260 bytes

BigInteger B(int i){return new BigInteger(""+i);}int c(int...k){int n=k[0];for(k[0]=1;n>1&!java.util.stream.IntStream.range(0,n).filter(i->B(n).gcd(B(i)).equals(B(1))).allMatch(x->B(x).modPow(B(k[0]),B(n)).equals(B(1)));k[0]++);return k[0];}

Imports, 19 bytes

import java.math.*;

Explanation

It is a straight forward implementation. The co-primes are calculated in the Set p and every one's kth power is used to check if it equals 1 modulo n.

I had to use BigInteger because of precision issues.

Usage

public static void main(String[] args) {
    Carmichael c = new Carmichael();
    System.out.println(c.c(3)); // prints 2
}

Ungolfed

// returns the BigInteger representation of the given interger
BigInteger B(int i) {
    return new BigInteger(""+i);
}
// for a given integer it returns the result of the carmichael function again as interger
// so the return value cannot be larger
int c(int... k) {
    int n = k[0];
    // iterate k[0] until for all co-primes this is true: (x^n) mod n == 1, if n==1 skip the loop
    for (k[0]=1;n > 1 && !java.util.stream.IntStream.range(0, n)
                .filter(i -> B(n).gcd(B(i)).equals(B(1)))
                .allMatch(x -> B((int) x).modPow(B(k[0]), B(n)).equals(B(1)));k[0]++);
    return k[0];
}

Any suggestions to golf it more are welcome :-)

Update

• No elements outside the functions that keep the state
• Followed Olivier Grégoire's advice and saved 1 byte from B()
• Removed the k() method and p (co-primes) Set.
• Removed not required casting to int.
• Added varags and use for instead of while.

Answer 15

Java, 209 207 202 194 192 bytes

Code (96 bytes):

n->{for(int x,k=1,a;;k++){for(a=1,x=0;++x<=n&&a<2;)a=g(x,n)<2?p(x,k,n):1;if(a<2||n<2)return k;}}

extra functions (96 bytes):

int g(int a,int b){return b<1?a:g(b,a%b);}int p(int n,int p,int m){return p<2?n:n*p(n,p-1,m)%m;}

Testing & ungolfed

import java.util.Arrays;
import java.util.function.IntUnaryOperator;

public class Main2 {

  static int g(int a,int b) { // recursive gcd
    return b < 1
        ? a
        : g(b,a%b);
  }

  static int p(int n, int p, int m) { // recursive modpow
    return p < 2
      ? n
      : n * p(n, p - 1, m) % m;
  }

  public static void main(String[] args) {

    IntUnaryOperator f = n -> {
      for(int x,k=1,a;;k++) { // for each k
        for(a=1,x=0;++x<=n&&a<2;) // for each x
          a=g(x,n)<2?p(x,k,n):1; // compute modpow(x,k,n) if g(x,n)
        if(a<2||n<2) // if all modpow(x,k,n)=1. Also check for weird result for n=1.
          return k;
      }
    };

    Arrays.stream(new int[]{1, 2, 3, 10, 35, 101, 530, 3010, 6511, 10000})
        .map(f)
        .forEach(System.out::println);
  }
}

Notes

• the use of a being an int is shorter than if I had to use a boolean to perform my tests.
• Yes, it's shorter to valueOf all new BigInteger than create a separate function (there are 5, plus the ONE constant is a freebie).
• Algorithm is different than @Master_ex' algorithm, so it's not just a golfed repost. Also, this algorithm is much less efficient as gcd is computed again and again for the same values.

Shaves

1. 209 -> 207 bytes:
   • if(...)a=...; -> a=...?...:1;
   • a==1 -> a<2
2. 207 -> 202 bytes
   • Got rid of BigInteger by golfing gcd and modPow for int.
3. 202 -> 194 bytes
   • looping modPow -> recursive
4. 194 -> 192 bytes
   • ==1 -> <2 (seems to work for all the test cases, don't know for other numbers.)

Answer 16

C++, 208 200 149 144 140 134 bytes

[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};

A port of my C implementation.

Try it on Ideone

Answer 17

Java, 165 163 158 152 143 bytes

int l(int n){int k=1,x,a,b,t,d=1;for(;d>0;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;b>0;b=a%b,a=t)t=b;for(t=b=1;b++<=k;t=t*x%n);}return k;}

Another port of my C implementation.

Try it on Ideone

Answer 18

Axiom 129 bytes

c(n)==(r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1);repeat(for a in r repeat(v:=powmod(a,k,n);v~=1=>break);v<=1=>break;k:=k+1);k)

less golfed

cml(n)==
 r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1)
 repeat 
   for a in r repeat(v:=powmod(a,k,n);v~=1=>break)
   v<=1=>break
   k:=k+1
 k

results

(3) -> [i,c(i)] for i in [1,2,3,10,35,101,530,3010,6511,10000]
   Compiling function c with type PositiveInteger -> PositiveInteger

   (3)
   [[1,1], [2,1], [3,2], [10,4], [35,12], [101,100], [530,52], [3010,84],
    [6511,3056], [10000,500]]
                                             Type: Tuple List PositiveInteger

Answer 19

C, 278 276 272 265 256 243 140 134 125 bytes

k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;}

This uses a slow modular exponentiation algorithm, computes the GCD too often and no longer leaks memory!

Ungolfed:

int gcd( int a, int b ) {
  int t;
  while( b ) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}
int pw(int a,int b,int c){
  int t=1;
  for( int e=0; e<b; e++ ) {
    t=(t*a)%c;
  }
  return t;
}
int carmichael(int n) {
  int k = 1;
  for( ;; ) {
    int done = 1;
    for( int x=1; x<n; x++ ) {
      if( gcd(x,n)==1 && pw(x,k,n) != 1 ) {
        done = 0;
        k++;
      }
    }
    if( done ) break;
  }
  return k;
}

Try it on Ideone

Answer 20

Racket 218 bytes

(λ(n)(let((fl #f)(cl(for/list((i n) #:when(coprime? n i))i)))(for/sum((k(range 1 n))#:break fl)(set! fl #t)
(for((i(length cl))#:break(not fl))(when(not(= 1(modulo(expt(list-ref cl i)k)n)))(set! fl #f)))(if fl k 0))))

Ungolfed version:

(require math)
(define f
  (λ(n)
    (let ((fl #f)
          (cl (for/list ((i n) #:when (coprime? n i))
                i)))
             (for/sum ((k (range 1 n)) #:break fl)
               (set! fl #t)
               (for ((i (length cl)) #:break (not fl))
                 (when (not (= 1 (modulo (expt (list-ref cl i) k) n)))
                   (set! fl #f)))
               (if fl k 0)))))

Testing:

(f 2) 
(f 3)
(f 10)
(f 35)
(f 101)
(f 530)
(f 3010)
(f 6511)
(f 10000)

Output:

1
2
4
12
100
52
84
3056
500