36
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ What does theoretically mean here? Can I assume that the input n fits in a 16-bit integer? Can I assume that n^λ(n) fits in a double? \$\endgroup\$ – Dennis Sep 20 '16 at 22:00
  • 2
    \$\begingroup\$ Yes and yes, I’d say. As in, the theoretically includes pretend your native types are arbitrarily precise and large (I thought that was consensus, but I’m not sure). \$\endgroup\$ – Lynn Sep 20 '16 at 23:23

20 Answers 20

48
\$\begingroup\$

Mathematica, 16 bytes

CarmichaelLambda

Well...

\$\endgroup\$
  • 38
    \$\begingroup\$ ..... really. ._. \$\endgroup\$ – acrolith Sep 18 '16 at 18:38
  • 12
    \$\begingroup\$ I don't like u mathematica \$\endgroup\$ – downrep_nation Sep 19 '16 at 9:00
29
\$\begingroup\$

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 ak ≡ 1 (mod n) – i.e., such that n | ak - 1 – for all a that are coprime to n.

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

λ(n) ≤ f(n)

Fix n and let a be coprime to n.

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

Since λ(n) is the smallest integer k such that n | ak - 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 ak+1(ak - 1) % n for all values of a in that range, which is 0 if and only if n | ak+1(ak - 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).

\$\endgroup\$
  • \$\begingroup\$ You can save at least 4 with recursion instead of a list comprehension: f=lambda n,k=1,a=1:a/n or(a**k*~-a**k%n<1)*f(n,k,a+2-n%2)or-~f(n,k+1) (Add back one byte if you don't like it to take n**λ(n) time). \$\endgroup\$ – feersum Sep 19 '16 at 19:01
  • 1
    \$\begingroup\$ Thanks! In the meantime, I found an improvement to my algorithm that seems to nullify the benefit of recursing instead of using a list comprehension. \$\endgroup\$ – Dennis Sep 19 '16 at 22:00
14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You can use EulerPhi to get LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)& for 57 bytes. \$\endgroup\$ – miles Sep 19 '16 at 13:11
  • \$\begingroup\$ @miles nicely spotted! I count 56 bytes, can you check? \$\endgroup\$ – Greg Martin Sep 19 '16 at 18:11
  • \$\begingroup\$ Yeah, it's 57 bytes. \$\endgroup\$ – miles Sep 19 '16 at 19:13
  • \$\begingroup\$ clearly I even try to golf my counting.... :/ \$\endgroup\$ – Greg Martin Sep 19 '16 at 19:23
12
\$\begingroup\$

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

\$\endgroup\$
10
\$\begingroup\$

Haskell, 57 56 bytes

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

Jelly, 2 bytes

Æc

Thank you for the builtin, @Lynn

\$\endgroup\$
  • 31
    \$\begingroup\$ ............. ._. \$\endgroup\$ – Maltysen Sep 18 '16 at 18:20
  • 10
    \$\begingroup\$ I never understand the point of implementing such ridiculously specific built-ins. \$\endgroup\$ – Fatalize Sep 18 '16 at 19:24
  • 31
    \$\begingroup\$ This is almost an addition to the language specifically made for this challenge. Commit by Lynn 2 days ago, challenge by @Lynn today \$\endgroup\$ – edc65 Sep 18 '16 at 19:59
  • 5
    \$\begingroup\$ @edc65 Not to mention that this built-in is pretty much useless outside this challenge and derivatives of it. \$\endgroup\$ – Fatalize Sep 19 '16 at 6:36
  • 3
    \$\begingroup\$ Well, the Carmichael function is important in number theory (as the currently top answer reflects), so I wouldn't call it useless. \$\endgroup\$ – Greg Martin Sep 19 '16 at 19:25
6
\$\begingroup\$

Pyth - 19 18 17 bytes

One byte saved thanks to @TheBikingViking.

Straight up brute force.

f!sm*t.^dTQq1iQdQ

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ f!smt is one byte shorter. \$\endgroup\$ – TheBikingViking Sep 18 '16 at 19:18
  • \$\begingroup\$ @TheBikingViking oh, yeah thanks \$\endgroup\$ – Maltysen Sep 18 '16 at 19:23
  • \$\begingroup\$ Hurts my eyes, how the heck is this python..? Loved it nonetheless haha :) \$\endgroup\$ – Yohan Obadia Apr 24 '18 at 14:22
6
\$\begingroup\$

Ruby, 59 56 bytes

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

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 λ(pk) = φ(pk)/2 if p = 2 and k > 2 else φ(pk). Then, for general n = p1k1 p2k2piki, λ(n) = LCM[ λ(p1k1) λ(p2k2) ⋯ λ(piki) ].

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
\$\endgroup\$
  • \$\begingroup\$ This gives the wrong answer for 10000 (1000 instead of the correct 500), and indeed for every multiple of 8. 2 is a peculiar prime, and λ(2^a) = 2^{a-2} (not 2^{a-1}) when a≥3. \$\endgroup\$ – Greg Martin Sep 19 '16 at 5:52
  • \$\begingroup\$ Thanks for catching that, seems I can't even read my own output \$\endgroup\$ – miles Sep 19 '16 at 12:30
  • \$\begingroup\$ you're not alone sometimes.... :) \$\endgroup\$ – Greg Martin Sep 19 '16 at 18:09
5
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ Actually, I have no idea how you did this in only 19 bytes. \$\endgroup\$ – Buffer Over Read Sep 20 '16 at 2:07
  • \$\begingroup\$ @TheBitByte With use of the totient and gcd builtins. This would be shorter if Actually had lcm directly, but I don't mind it that much and that would only knock off 4 bytes at most, anyway. \$\endgroup\$ – Sherlock9 Sep 20 '16 at 2:10
  • 1
    \$\begingroup\$ The assertion that lcm(*a) = product(*a)/gcd(*a) is true when *a is a list of exactly two numbers; however, it is false in general for longer lists (example: if *a is {6,10,15}, it gives 900 instead of the correct answer of 60). [For that matter, it's wrong is *a is a list of one number as well!] And you can check that you get the wrong answer for over half the test cases listed in the OP. \$\endgroup\$ – Greg Martin Sep 20 '16 at 23:20
  • \$\begingroup\$ @GregMartin Thanks for the heads up. Fixed. \$\endgroup\$ – Sherlock9 Sep 21 '16 at 3:40
4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ JS can do 0..n-1 ranges quite easily: [...Array(n).keys()]. This requires not one but two special cases but I'm still ahead: 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 \$\endgroup\$ – Neil Sep 24 '16 at 18:52
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You don't need a=. Unfortunately, you return nil for n = 1 :(. (n.prime_division<<[2,1]) fixes that. Not sure if there's a golfier way. \$\endgroup\$ – m-chrzan Sep 20 '16 at 22:26
  • \$\begingroup\$ (n%8<1?n/2:n).prime_division... saves another 2 bytes. \$\endgroup\$ – m-chrzan Sep 20 '16 at 22:32
  • \$\begingroup\$ @m-chrzan a is a remnant of an earlier golfing attempt. Thanks for the reminder about a and for heads up on 1. \$\endgroup\$ – Sherlock9 Sep 21 '16 at 3:40
  • \$\begingroup\$ You can save a byte by using .reduce :lcm instead of .reduce(:lcm). \$\endgroup\$ – Cyoce Sep 24 '16 at 19:08
1
\$\begingroup\$

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
} 
\$\endgroup\$
  • \$\begingroup\$ recursive modpow is shorter: p=(a,b,c)=>b?a*p(a,b-1,c)%c:1; \$\endgroup\$ – Olivier Grégoire Sep 21 '16 at 11:05
1
\$\begingroup\$

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.)
\$\endgroup\$
  • \$\begingroup\$ Hey! I've noticed that the output is not the expected. See the question for the expected results. Personally, I often write unit tests before starting golfing my code, it helps! I guess that the problem could be the modPow on integers, I had also this problem and that's why I used BigInteger at the end. \$\endgroup\$ – Master_ex Sep 21 '16 at 7:14
  • \$\begingroup\$ Hmmm... I'm surprised, I let my tests run at every change. I'll check what's wrong. \$\endgroup\$ – Olivier Grégoire Sep 21 '16 at 7:45
  • 1
    \$\begingroup\$ @Master_ex I fixed it. Going back to the previous version is ok. \$\endgroup\$ – Olivier Grégoire Sep 21 '16 at 9:00
  • \$\begingroup\$ I find your recursive modpow method p pretty clever. I tried to use only integers at first too, but as I've mentioned in my answer, I had precision issues and that's why I've moved to BigInteger (i.e. Math.pow(3, 100)%101 returned 60.0 instead of 1). Your implementation is immune to this because it performs the mod in each iteration. However, it still suffers from a bug. For large m p may still return wrong results. Also, because of the recursion, StackOverflowError may easily occur for large input with the default stack size. \$\endgroup\$ – Master_ex Sep 22 '16 at 0:17
  • \$\begingroup\$ @Master_ex Yes, that's a consequence of the restriction to int types. I could use longs instead of ints, that'd be 8 extra bytes. But in my view, all the test cases are valid so I leave it like that. StackOverflowError can happen, but that's how recursive works. Methods exist to limit to 32 stacks, but these use many many more bytes. This implementation is fragile, yes, you are totally right. But it's strong enough for the test cases. \$\endgroup\$ – Olivier Grégoire Sep 22 '16 at 7:50
1
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Can you have an ungolfed version (with linebreaks, comments here & there, etc.) \$\endgroup\$ – OldBunny2800 Sep 20 '16 at 1:52
  • \$\begingroup\$ @OldBunny2800: Yeah, sure. However, I'll do it later today because now I am busy! \$\endgroup\$ – Master_ex Sep 20 '16 at 5:29
  • \$\begingroup\$ @OldBunny2800: I added an ungolfed version :-) \$\endgroup\$ – Master_ex Sep 20 '16 at 18:39
  • \$\begingroup\$ Hmmm... I'm not sure if this counts as it's neither a function nor a program. If it's a function, there are elements outside of it that keep the state, making it a de facto method (function is pure input->output without external state), if it's a program, the whole main method is missing. If my interpretations are incorrect, please tell me so! I think it's better to include k(int) in the loop as it's a one-liner and can be done. Plus, the constant O can be put in the c method as well. I guess you'll win bytes by doing so! \$\endgroup\$ – Olivier Grégoire Sep 20 '16 at 20:00
  • \$\begingroup\$ Concretely, while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O))) shaves bytes and fixes the issues I mentioned if you put the set and the constant back into the method. Also, you use O twice, replace by B(1) to shave bytes. \$\endgroup\$ – Olivier Grégoire Sep 20 '16 at 20:04
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.