Description de la tâche

Dans la théorie des nombres, la fonction de Carmichael  λ prend un nombre entier positif  n et retourne le plus petit entier positif k de telle sorte que la k puissance -ième de chaque entier coprime à n est égal à 1 modulo n .

Étant donné un entier positif n , votre solution doit calculer λ (n) . Le code le plus court en octets gagne.

Votre programme devrait théoriquement fonctionner pour des entrées arbitrairement grandes, mais n'a pas besoin d'être efficace.

Conseils

La séquence de tous les λ (n) est OEIS A002322 .

Une implémentation de Python non-golfée ressemblerait à

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

(En Python, pow(A, B, C)calcule efficacement pow(A, B) % C.)

Cas de test

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

Mathematica, 16 octets

CarmichaelLambda

Bien...

Python, 76 73 67 octets

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

Essayez-le en ligne!

Un autre octet peut être sauvegardé en retournant True au lieu de 1 .

Mise en œuvre alternative

En utilisant la même approche, il y a aussi l'implémentation suivante de @feersum qui n'utilise pas les compréhensions de liste.

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)

Notez que cette implémentation nécessite O (n ^{λ (n)} ) temps. L'efficacité pourrait être considérablement améliorée tout en réduisant le score à 66 octets , mais la fonction renverrait True pour l'entrée 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)

Contexte

Définitions et notation

Toutes les variables employées désigneront des entiers; n , k et α désigneront des entiers positifs ; et p désignera un nombre premier positif .

a | b si b est divisible par a , c'est-à-dire s'il y a q tel que b = qa .

a ≡ b ( mod m) si a et b ont le même résidu modulo m , c'est-à-dire si m | a - b .

λ (n) est le plus petit k tel que a ^k ≡ 1 ( mod n) - c'est-à-dire tel que n | a ^k - 1 - pour tous les a qui sont coprimes à n .

f (n) est le plus petit k tel que a ^{2k + 1} ≡ a ^{k + 1} ( mod n) - c'est-à-dire tel que n | a ^{k + 1} (a ^k - 1) - pour tous a .

λ (n) ≤ f (n)

Fixez n et laissez a être coprime à n .

Par la définition de f , n | a ^{f (n) +1} (a ^{f (n)} - 1) . Depuis un et n n'ont pas un facteur premier commun, non plus un ^{f (n) 1} et n , ce qui implique que n | a ^{f (n)} - 1 .

Puisque λ (n) est le plus petit entier k tel que n | a ^k - 1 pour tous les entiers a qui ont la priorité pour n , il en résulte que λ (n) ≤ f (n) .

λ (n) = f (n)

Puisque nous avons déjà établi l'inégalité λ (n) ≤ f (n) , il suffit de vérifier que k = λ (n) vérifie la condition qui définit f , c'est-à-dire que n | a ^{λ (n) +1} (a ^{λ (n)} - 1) pour tout a . Pour cela, nous allons établir que p ^α | a ^{λ (n) +1} (a ^{λ (n)} - 1) chaque fois que p ^α | n .

λ (k) | λ (n) chaque fois que k | n ( source ), donc (a ^{λ (k)} - 1) (a ^{λ (n) -λ (k)} + a ^{λ (n) -2λ (k)} + ⋯ + a ^{λ (k)} + 1) = a ^{λ (n)} - 1 et donc un ^{λ (k)} - 1 | a ^{λ (n)} - 1 | a ^{λ (n) +1} (a ^{λ (n)} - 1) .

Si a et p ^α sont coprimes, par la définition de λ et celle ci-dessus, p ^α | a ^{λ (p α )} - 1 | Un ^{λ (n) +1} (un ^{λ (n)} - 1) suit, comme vous le souhaitez.

Si a = 0 , alors un ^{λ (n) 1} (a ^{λ (n)} - 1) = 0 , ce qui est divisible par tous les nombres entiers.

Enfin, nous devons considérer le cas où a et p ^α ont un facteur premier commun. Puisque p est premier, cela implique que p | a . Le théorème de Carmichael établit que λ (p ^α ) = (p - 1) p ^{α - 1} si p> 2 ou α <3 et que λ (p ^α ) = p ^{α - 2} sinon. Dans tous les cas, λ (p ^α ) ≥ p ^{α - 2} ≥ 2 ^{α - 2} > α - 2 .

Par conséquent, λ (n) + 1 ≥ λ (p ^α ) + 1> α - 1 , donc λ (n) + 1 ≥ α et p ^α | p ^{λ (n) +1} | a ^{λ (n) +1} | a ^{λ (n) +1} (a ^{λ (n)} - 1) . Ceci complète la preuve.

Comment ça marche

Alors que les définitions de f (n) et λ (n) considèrent toutes les valeurs possibles de a , il suffit de tester celles qui se trouvent dans [0, ..., n - 1] .

Lorsque f (n, k) est appelé, il calcule un ^{k + 1} (a ^k - 1)% n pour toutes les valeurs de a dans cette plage, qui est 0 si et seulement si n | a ^{k + 1} (a ^k - 1) .

Si tous les résidus calculés sont zéro, k = λ (n) et anyrenvoie False , donc f (n, k) renvoie 1 .

D'autre part, alors que k <λ (n) , 1-any(...)retournera 0 , f est appelé de manière récursive avec une valeur incrémentée de k . Le premier -~incrémente la valeur de retour de f (n, k + 1) , nous ajoutons donc 1 à f (n, λ (n)) = 1 une fois pour chaque entier de [1, ..., λ (n) - 1 ] . Le résultat final est donc λ (n) .

Mathematica sans intégré, 58 57 octets

Merci à Martin Ender d’avoir trouvé une erreur, puis de me sauver les octets nécessaires pour la réparer!

Merci aux miles d'avoir économisé 1 octet! (qui me semblait être 2)

Les fonctions intégrées conviennent parfaitement ... mais pour ceux qui veulent l'implémenter sans utiliser de force brute, voici une formule pour la fonction Carmichael:

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

Si p est un nombre premier, la fonction de Carmichael λ (p ^ r) est égale à (p ^ r) = (p-1) * p ^ (r-1) - sauf lorsque p = 2 et r≥3, auquel cas c'est la moitié, à savoir 2 ^ (r-2).

Et si la factorisation de la puissance première de n est égale à p1 ^ r1 * p2 ^ r2 * ..., alors λ (n) est égal au plus petit commun multiple de {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.

Le temps d'exécution est un instant de plus que la factorisation du nombre entier en premier lieu.

Modèles considérés comme nuisibles , 246 octets

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

Une fonction non nommée (pas qu'il y ait des fonctions nommées).

C'est un de mes esolang oublié qui est interprété par un compilateur C ++ instanciant des modèles. Avec la profondeur de gabarit maximale par défaut de g++, cela peut faire λ (35), mais pas λ (101) (l'évaluation paresseuse aggrave la situation).

Haskell, 57 56 octets

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

Gelée, 2 octets

Æc

Merci pour la fonction intégrée, @Lynn

Pyth - 19 18 17 octets

Un octet enregistré grâce à @TheBikingViking.

Straight up force brute.

f!sm*t.^dTQq1iQdQ

Essayez-le en ligne ici .

Rubis, 59 56 octets

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

J, 28 27 octets

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

La fonction de Carmichael est λ ( n ) et la fonction totale est ( n ).

Utilise la définition où λ ( p ^k ) = φ ( p ^k ) / 2 si p = 2 et k > 2 sinon φ ( p ^k ). Ensuite, pour générale n = p ₁ ^{k ₁} p ₂ ^{k ₂} ⋯ p _i ^{k _i} , λ ( n ) = PPCM [λ ( p ₁ ^{k ₁} ) λ ( p ₂ ^{k ₂} ) ⋯ λ ( p _i ^{k _i} )] .

Usage

Commandes supplémentaires utilisées pour formater plusieurs entrées / sorties.

   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

Explication

[:*./@(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

En fait, 30 28 25 19 26 octets

La fonction Carmichael, λ(n)où n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, est définie comme le plus petit commun multiple (LCM) de λ(p_i**k_i)pour les premiers pouvoirs maximaux p_i**k_iqui se divisent en n. Étant donné que pour chaque puissance principale, à l'exception de la puissance principale 2, la fonction Carmichael est équivalente à la fonction de Euler λ(n) == φ(n), nous utilisons φ(n)plutôt. Pour le cas particulier 2**koù k ≥ 3, nous vérifions simplement si 2**3 = 8divise en ndébut de programme et divise par 2 si c'est le cas.

Malheureusement, à l'heure actuelle, aucun LCM n'est intégré, j'ai donc créé un LCM à force brute. Les suggestions de golf sont les bienvenues. Essayez-le en ligne!

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

JavaScript (ES6), 143 135 octets

Edit: sauvegardé 8 octets grâce à Neil

Une implémentation utilisant la programmation fonctionnelle.

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 et commenté

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)

Démo

Bien que cela fonctionne pour 6511et 10000, je ne les inclurai pas ici car cela a tendance à être un peu lent.

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

Ruby, 101 86 91 90 octets

Un port Ruby de ma réponse actuelle . Les suggestions de golf sont les bienvenues.

Edit: -4 octets pour supprimer, amais +9 octets pour corriger un bogue 1renvoyé nil. -1 octet grâce à 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

JavaScript (ES 2016) 149

Implémentation de référence Python portée sur JS. Certains éléments de Pyhton sophistiqués manquent dans js, comme gcdet pow, et la compréhension du tableau n’est pas standard dans ES 6. Cela fonctionne dans 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')

Moins joué au golf

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
} 

Java, 209 207 202 194 192 octets

Code (96 octets):

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;}}

fonctions supplémentaires (96 octets):

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;}

Test et non-golfé

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

Remarques

• l'utilisation d' aêtre un intest plus courte que si je devais utiliser un booleanpour effectuer mes tests.
• Oui, il est plus court à valueOftoute nouvelle BigIntegerque de créer une fonction distincte (il y a 5, plus la ONEconstante est un billet de faveur).
• L'algorithme est différent de l'algorithme de @Master_ex, il ne s'agit donc pas simplement d'un repost golfé. En outre, cet algorithme est beaucoup moins efficace, car il gcdest calculé encore et encore pour les mêmes valeurs.

Se rase

1. 209 -> 207 octets:
   • if(...)a=...; -> a=...?...:1;
   • a==1 -> a<2
2. 207 -> 202 octets
   • Je me suis débarrassé de BigIntegeren jouant au golf gcdet modPowpour int.
3. 202 -> 194 octets
   • bouclage modPow-> récursif
4. 194 -> 192 octets
   • ==1-> <2(semble fonctionner pour tous les cas de test, ne sait pas pour les autres nombres.)

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

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];}

Importations, 19 octets

import java.math.*;

Explication

C'est une mise en œuvre simple. Les co-nombres premiers sont calculés dans le Set pet la puissance de chacun est utilisée pour vérifier si elle est égale à 1 modulo n.

J'ai dû utiliser à BigIntegercause de problèmes de précision.

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];
}

Toutes les suggestions pour jouer au golf sont les bienvenues :-)

Mise à jour

• Aucun élément en dehors des fonctions qui maintiennent l'état
• Suivi des conseils d'Olivier Grégoire et sauvegarde de 1 octet de B()
• Suppression de la k()méthode et de p(co-nombres premiers).
• Suppression de la conversion non requise en int.
• Ajout de varags et utilisation pour au lieu de tant que.

Java, 165 163 158 152 143 octets

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;}

Un autre port de ma mise en œuvre C .

Essayez sur Ideone

C ++, 208 200 149 144 140 134 octets

[](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;};

Un port de mon mise en œuvre C .

Essayez sur Ideone

Raquette 218 octets

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

Version non-golfée:

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

Essai:

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

Sortie:

1
2
4
12
100
52
84
3056
500

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

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;}

Cela utilise un algorithme d'exponentiation modulaire lente, calcule le GCD trop souvent et ne perd plus de mémoire!

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;
}

Essayez sur Ideone

Axiome 129 octets

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)

moins golfé

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

résultats

(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