Calculer la fonction Carmichael

36

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
Lynn
la source
Que signifie théoriquement ici? Puis-je supposer que l'entrée n correspond à un entier de 16 bits? Puis-je supposer que n ^ λ (n) s'inscrit dans un double?
Dennis
2
Oui et oui, je dirais. Comme dans la théorie comprend feignent vos types natifs sont arbitrairement précis et grande (je pensais que c'était un consensus, mais je ne suis pas sûr).
Lynn

Réponses:

48

Mathematica, 16 octets

CarmichaelLambda

Bien...

Martin Ender
la source
38
..... vraiment. ._.
acrolithe
12
Je ne aime pas u Mathematica
downrep_nation
29

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

Dennis
la source
Vous pouvez économiser au moins 4 avec la récursivité au lieu d'une liste de compréhension: 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)(Ajoutez un octet en arrière si vous ne l'aimez pas prendre n ** λ (n) fois).
feersum
1
Merci! Entre-temps, j'ai trouvé une amélioration de mon algorithme qui semble annuler l'avantage de la récurrence au lieu d'utiliser une compréhension par liste.
Dennis
14

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.

Greg Martin
la source
Vous pouvez utiliser EulerPhipour obtenir LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&57 octets.
miles
@miles bien repéré! Je compte 56 octets, pouvez-vous vérifier?
Greg Martin
Oui, c'est 57 octets .
miles
clairement j'essaye même de jouer au golf mon compte ....: /
Greg Martin
12

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

feersum
la source
10

Haskell, 57 56 octets

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

Gelée, 2 octets

Æc

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

Dianne
la source
31
............. ._.
Maltysen
10
Je ne comprends jamais l’intérêt de mettre en œuvre de telles fonctions intégrées ridiculement spécifiques.
Fatalize
31
C'est presque un ajout au langage spécialement conçu pour ce défi. Commit par Lynn il y a un jour, défi par @Lynn aujourd'hui
edc65
5
@ edc65 Sans oublier que cette intégration est quasiment inutile en dehors de ce défi et de ses dérivés.
Fatalise
3
Eh bien, la fonction Carmichael est importante dans la théorie des nombres (comme le montre la réponse actuelle), je ne dirais donc pas qu'elle est inutile.
Greg Martin
6

Pyth - 19 18 17 octets

Un octet enregistré grâce à @TheBikingViking.

Straight up force brute.

f!sm*t.^dTQq1iQdQ

Essayez-le en ligne ici .

Maltysen
la source
f!smtest un octet plus court.
TheBikingViking
@TheBikingViking oh, oui merci
Maltysen
Ça fait mal aux yeux, comment diable est ce python ..? J'ai quand même adoré haha ​​:)
Yohan Obadia
6

Rubis, 59 56 octets

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

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 1 k 1 p 2 k 2p i k i , λ ( n ) = PPCM [λ ( p 1 k 1 ) λ ( p 2 k 2 ) ⋯ λ ( 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
milles
la source
Cela donne la mauvaise réponse pour 10000 (1000 au lieu de 500), et pour chaque multiple de 8. 2 est un nombre premier particulier, et λ (2 ^ a) = 2 ^ {a-2} (et non 2 ^ { a-1}) quand a≥3.
Greg Martin
Merci de l'avoir remarqué, il semble que je ne puisse même pas lire mon propre texte
miles le
tu n'es pas seul parfois ... :)
Greg Martin
5

En fait, 30 28 25 19 26 octets

La fonction Carmichael, λ(n)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**kk ≥ 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.
Sherlock9
la source
2
En fait, je n'ai aucune idée de la façon dont vous avez fait cela en seulement 19 octets.
Tampon Over Lu
@TheBitByte Avec l'utilisation de totientet des commandes gcdintégrées. En réalité, ce serait plus court si cela avait été fait lcmdirectement, mais cela ne me dérangeait pas trop et cela ne supprimerait que 4 octets au maximum, de toute façon.
Sherlock9
1
L'affirmation que lcm (* a) = produit (* a) / gcd (* a) est vraie lorsque * a est une liste de deux nombres exactement; Cependant, il est généralement faux pour les listes plus longues (exemple: si * a est {6,10,15}, il donne 900 au lieu de la réponse correcte de 60). [D'ailleurs, c'est faux, c'est * a est aussi une liste d'un nombre!] Et vous pouvez vérifier que vous obtenez la mauvaise réponse pour plus de la moitié des cas de test listés dans l'OP.
Greg Martin
@ GregMartin Merci pour le heads-up. Fixé.
Sherlock9
4

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

Arnauld
la source
1
JS peut faire des 0..n-1gammes assez facilement: [...Array(n).keys()]. Cela nécessite non pas un mais deux cas spéciaux, mais je suis toujours en avance: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
Neil
2

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
Sherlock9
la source
Tu n'as pas besoin a=. Malheureusement, vous revenez nilpour n = 1 :(. (n.prime_division<<[2,1])Corrige cela. Je ne sais pas s'il existe un moyen plus golfeur.
m-chrzan
(n%8<1?n/2:n).prime_division...enregistre 2 autres octets.
m-chrzan
@ m-chrzan aest un vestige d'une tentative de golf antérieure. Merci pour le rappel sur aet pour la tête sur 1.
Sherlock9
Vous pouvez enregistrer un octet en utilisant à la .reduce :lcmplace de .reduce(:lcm).
Cyoce
1

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
} 
edc65
la source
modpow récursif est plus court:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire
1

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.)
Olivier Grégoire
la source
Hey! J'ai remarqué que la sortie n'est pas celle attendue. Voir la question pour les résultats attendus. Personnellement, j’écris souvent des tests unitaires avant de commencer à jouer mon code, ça aide! Je suppose que le problème pourrait être le modPow sur les entiers, j'avais aussi ce problème et c'est pourquoi j'ai utilisé BigInteger à la fin.
Master_ex
Hmmm… je suis surpris, je laisse mes tests se dérouler à chaque changement. Je vais vérifier ce qui ne va pas.
Olivier Grégoire
1
@ Master_ex je l'ai corrigé. Revenir à la version précédente est ok.
Olivier Grégoire le
Je trouve votre méthode de modpow récursive passez astucieuse. Au début, j’ai aussi essayé d’utiliser des entiers, mais comme je l’ai mentionné dans ma réponse, j’avais des problèmes de précision et c’est pourquoi je suis passé à BigInteger(c’est- à -dire Math.pow(3, 100)%101retourné 60.0au lieu de 1). Votre implémentation est immunisée contre cela car elle effectue le mod dans chaque itération. Cependant, il souffre toujours d'un bug. Pour les grands m ppeut encore retourner des résultats erronés. De plus, en raison de la récursivité, une StackOverflowErrorentrée importante avec la taille de pile par défaut peut facilement se produire.
Master_ex
@ Master_ex Oui, c'est une conséquence de la restriction aux inttypes. Je pourrais utiliser des longs au lieu de ints, ce serait 8 octets supplémentaires. Mais à mon avis, tous les cas de test sont valides, donc je le laisse comme ça. StackOverflowErrorpeut arriver, mais c'est ainsi que fonctionne récursif. Il existe des méthodes pour limiter à 32 piles, mais elles utilisent beaucoup plus d'octets. Cette implémentation est fragile, oui, vous avez tout à fait raison. Mais c'est assez fort pour les cas de test.
Olivier Grégoire
1

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.
Master_ex
la source
Pouvez-vous avoir une version non-golfée (avec sauts de ligne, commentaires ici et là, etc.)
OldBunny2800 le
@ OldBunny2800: Oui, bien sûr. Cependant, je le ferai plus tard aujourd'hui parce que maintenant je suis occupé!
Master_ex
@ OldBunny2800: J'ai ajouté une version non-golfée :-)
Master_ex
Hmmm ... Je ne suis pas sûr que cela compte car ce n'est ni une fonction ni un programme. Si c'est une fonction, il y a des éléments en dehors de celle-ci qui gardent l'état, ce qui en fait une méthode de facto (fonction est pure input-> output sans état externe), s'il s'agit d'un programme, toute la méthode principale est manquante. Si mes interprétations sont incorrectes, merci de me le dire! Je pense qu'il est préférable d'inclure k(int)dans la boucle car c'est un one-line et peut être fait. De plus, la constante O peut également être insérée dans la cméthode. Je suppose que vous gagnerez des octets en le faisant!
Olivier Grégoire
Concrètement, while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))supprime les octets et corrige les problèmes que j'ai mentionnés si vous remettiez l'ensemble et la constante dans la méthode. En outre, vous utilisez Odeux fois, remplacer par B(1)pour raser les octets.
Olivier Grégoire
1

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

plafondcat
la source
1

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

plafondcat
la source
0

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
rnso
la source
0

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

plafondcat
la source
0

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
RosLuP
la source