Calcule la función Carmichael

36

Descripción de la tarea

En teoría de números, la función Carmichael  λ toma un número entero positivo  n y devuelve el número entero menos positivo k, de modo que la potencia k -ésima de cada número entero coprimo a n es igual a 1 módulo n .

Dado un entero positivo n , su solución debe calcular λ (n) . El código más corto en bytes gana.

Teóricamente, su programa debería funcionar para entradas arbitrariamente grandes, pero no necesita ser eficiente.

Consejos

La secuencia de todos los λ (n) es OEIS A002322 .

Una implementación de Python sin golf se vería como

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)computa eficientemente pow(A, B) % C).

Casos de prueba

Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500
Lynn
fuente
¿Qué significa teóricamente aquí? ¿Puedo suponer que la entrada n cabe en un entero de 16 bits? ¿Puedo suponer que n ^ λ (n) cabe en un doble?
Dennis
2
Sí y sí, diría. Como en, teóricamente incluye la simulación de que sus tipos nativos son arbitrariamente precisos y grandes (pensé que era un consenso, pero no estoy seguro).
Lynn

Respuestas:

48

Mathematica, 16 bytes

CarmichaelLambda

Bien...

Martin Ender
fuente
38
..... De Verdad. ._.
Acrolith
12
No me gusta usted
Mathica
29

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)

Pruébalo en línea!

Se podría guardar un byte adicional devolviendo True en lugar de 1 .

Implementación alternativa

Usando el mismo enfoque, también existe la siguiente implementación de @feersum que no utiliza listas de comprensión.

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)

Tenga en cuenta que esta implementación requiere O (n λ (n) ) tiempo. La eficiencia podría mejorarse drásticamente mientras se reduce la puntuación a 66 bytes , pero la función devolvería True para la entrada 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)

Fondo

Definiciones y notación

Todas las variables empleadas denotarán enteros; n , k y α denotarán enteros positivos ; y p denotará un primo positivo .

a | b si b es divisible por a , es decir, si hay q tal que b = qa .

a ≡ b ( mod m) si una y b tienen el mismo residuo módulo m , es decir, si m | a - b .

λ (n) es la k más pequeña tal que a k ≡ 1 ( mod n) , es decir, tal que n | un k - 1 - para todos una que son primos entre sí a n .

f (n) es la k más pequeña de manera que a 2k + 1 ≡ a k + 1 ( mod n) , es decir, tal que n | a k + 1 (a k - 1) - para todo a .

λ (n) ≤ f (n)

Arregle ny deje que a sea ​​coprime a n .

Por la definición de f , n | a f (n) +1 (a f (n) - 1) . Desde una y n no tienen un factor primordial común, ni hacer una f (n) 1 y n , lo que implica que n | a f (n) - 1 .

Como λ (n) es el entero más pequeño k tal que n | a k - 1 para todos los enteros a que son coprimos a n , se deduce que λ (n) ≤ f (n) .

λ (n) = f (n)

Como ya hemos establecido la desigualdad λ (n) ≤ f (n) , es suficiente verificar que k = λ (n) satisfaga la condición que define f , es decir, que n | a λ (n) +1 (a λ (n) - 1) para todo a . Para este propósito, estableceremos que p α | a λ (n) +1 (a λ (n) - 1) siempre que p α | n .

λ (k) | λ (n) siempre que k | n ( fuente ), entonces (a λ (k) - 1) (a λ (n) -λ (k) + a λ (n) -2λ (k) + ⋯ + a λ (k) + 1) = a λ (n) - 1 y, por lo tanto, a λ (k) - 1 | a λ (n) - 1 | a λ (n) +1 (a λ (n) - 1) .

Si una y p α son primos entre sí, por la definición de λ y el anterior, p α | a λ (p α ) - 1 | a λ (n) +1 (a λ (n) - 1) sigue, según se desee.

Si a = 0 , entonces a λ (n) +1 (a λ (n) - 1) = 0 , que es divisible por todos los enteros.

Finalmente, debemos considerar el caso donde a y p α tienen un factor primo común. Como p es primo, esto implica que p | a . El teorema de Carmichael establece que λ (p α ) = (p - 1) p α - 1 si p> 2 o α <3 y que λ (p α ) = p α - 2 de lo contrario. En todos los casos, λ (p α ) ≥ p α - 2 ≥ 2 α - 2 > α - 2 .

Por lo tanto, λ (n) + 1 ≥ λ (p α ) + 1> α - 1 , entonces λ (n) + 1 ≥ α y p α | p λ (n) +1 | a λ (n) +1 | a λ (n) +1 (a λ (n) - 1) . Esto completa la prueba.

Cómo funciona

Si bien las definiciones de f (n) y λ (n) consideran todos los valores posibles de a , es suficiente probar los que se encuentran en [0, ..., n - 1] .

Cuando se llama f (n, k) , calcula un k + 1 (a k - 1)% n para todos los valores de a en ese rango, que es 0 si y solo si n | a k + 1 (a k - 1) .

Si todos los residuos calculados son cero, k = λ (n) y anydevuelve False , entonces f (n, k) devuelve 1 .

Por otro lado, mientras k <λ (n) , 1-any(...)devolverá 0 , por lo que f se llama recursivamente con un valor incrementado de k . Los -~valores iniciales incrementan el valor de retorno de f (n, k + 1) , por lo que agregamos 1 a f (n, λ (n)) = 1 una vez por cada entero en [1, ..., λ (n) - 1 ] . El resultado final es así λ (n) .

Dennis
fuente
Puede guardar al menos 4 con recursión en lugar de una comprensión de la lista: 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)(Agregue un byte si no le gusta que tome n ** λ (n) tiempo).
feersum
1
¡Gracias! Mientras tanto, encontré una mejora en mi algoritmo que parece anular el beneficio de recurrir en lugar de usar una lista de comprensión.
Dennis
14

Mathematica sin incorporado, 58 57 bytes

¡Gracias a Martin Ender por encontrar un error, y luego me guardó los bytes necesarios para solucionarlo!

¡Gracias a las millas por ahorrar 1 byte! (que me pareció 2)

Los complementos están totalmente bien ... pero para aquellos que quieran implementarlo sin usar la fuerza bruta, aquí hay una fórmula para la función Carmichael:

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

Si p es primo, la función Carmichael λ (p ^ r) es igual a φ (p ^ r) = (p-1) * p ^ (r-1), excepto cuando p = 2 y r≥3, en cuyo caso es la mitad de eso, es decir, 2 ^ (r-2).

Y si la factorización de potencia primaria de n es igual a p1 ^ r1 * p2 ^ r2 * ..., entonces λ (n) es igual al mínimo común múltiplo de {λ (p1 ^ r1), λ (p2 ^ r2), .. .}.

El tiempo de ejecución es un instante más que factorizar el entero en primer lugar.

Greg Martin
fuente
Puedes usar EulerPhipara obtener LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&57 bytes.
millas
@miles muy bien visto! Cuento 56 bytes, ¿puedes verificar?
Greg Martin
Sí, son 57 bytes .
millas
claramente incluso trato de jugar al golf ...: /
Greg Martin
12

Plantillas consideradas dañinas , 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>>>

Una función sin nombre (no es que haya funciones con nombre).

Este es un esolang olvidado que interpretan las plantillas de creación de instancias de un compilador de C ++. Con la profundidad de plantilla máxima predeterminada de g++, puede hacer λ (35), pero no puede hacer λ (101) (la evaluación perezosa empeora las cosas).

Feersum
fuente
10

Haskell, 57 56 bytes

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

Jalea, 2 bytes

Æc

Gracias por la construcción, @ Lynn

dianne
fuente
31
............. ._.
Maltysen
10
Nunca entiendo el punto de implementar incorporaciones tan ridículamente específicas.
Fatalize
31
Esto es casi una adición al lenguaje hecho específicamente para este desafío. Comprometerse por Lynn hace 2 días, desafío por @Lynn hoy
edc65
55
@ edc65 Sin mencionar que esta función incorporada es prácticamente inútil fuera de este desafío y sus derivados.
Fatalize
3
Bueno, la función Carmichael es importante en la teoría de números (como lo refleja la respuesta principal actual), por lo que no lo llamaría inútil.
Greg Martin
6

Pyth - 19 18 17 bytes

Un byte guardado gracias a @TheBikingViking.

Fuerza bruta directa.

f!sm*t.^dTQq1iQdQ

Pruébelo en línea aquí .

Maltysen
fuente
f!smtes un byte más corto.
TheBikingViking
@TheBikingViking oh, sí, gracias
Maltysen
Me duelen los ojos, ¿cómo diablos es esta pitón ...? Me encantó, jaja :)
Yohan Obadia
6

Rubí, 59 56 bytes

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

J, 28 27 bytes

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

La función Carmichael es λ ( n ) y la función totient es φ ( n ).

Utiliza la definición donde λ ( p k ) = φ ( p k ) / 2 si p = 2 y k > 2 más φ ( p k ). Entonces, para general n = p 1 k 1 p 2 k 2p i k i , λ ( n ) = LCM [λ ( p 1 k 1 ) λ ( p 2 k 2 ) ⋯ λ ( p i k i )] .

Uso

Comandos adicionales utilizados para formatear múltiples entradas / salidas.

   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

Explicación

[:*./@(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
millas
fuente
Esto da la respuesta incorrecta para 10000 (1000 en lugar de las 500 correctas), y de hecho para cada múltiplo de 8. 2 es un primo peculiar, y λ (2 ^ a) = 2 ^ {a-2} (no 2 ^ { a-1}) cuando a≥3.
Greg Martin
Gracias por entender eso, parece que ni siquiera puedo leer mi propia salida
millas del
a veces no estás solo .... :)
Greg Martin
5

En realidad, 30 28 25 19 26 bytes

La función Carmichael, λ(n)donde n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a, se define como el mínimo común múltiplo (MCM) de λ(p_i**k_i)las potencias máximas máximas p_i**k_ique se dividen en n. Dado que para cada potencia principal, excepto donde está 2la función principal , la función Carmichael es equivalente a la función totient de Euler λ(n) == φ(n), usamos en su φ(n)lugar. Para el caso especial de 2**kdónde k ≥ 3, solo verificamos si se 2**3 = 8divide al ncomienzo del programa, y ​​dividimos por 2 si lo hace.

Desafortunadamente, actualmente no tiene un LCM incorporado, así que hice un LCM de fuerza bruta. Sugerencias de golf bienvenidas. Pruébalo en línea!

;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
fuente
2
En realidad, no tengo idea de cómo lo hiciste en solo 19 bytes.
Buffer Over Read
@TheBitByte Con el uso de totienty gcdbuiltins. Esto sería más corto si Realmente lo tuviera lcmdirectamente, pero no me importa tanto y eso solo eliminaría 4 bytes como máximo, de todos modos.
Sherlock9
1
La afirmación de que mcm (* a) = producto (* a) / gcd (* a) es verdadera cuando * a es una lista de exactamente dos números; sin embargo, es falso en general para listas más largas (ejemplo: si * a es {6,10,15}, da 900 en lugar de la respuesta correcta de 60). [Para el caso, ¡está mal es * a es una lista de un número también!] Y puede verificar que obtiene la respuesta incorrecta para más de la mitad de los casos de prueba enumerados en el OP.
Greg Martin
@ GregMartin Gracias por el aviso. Fijo.
Sherlock9
4

JavaScript (ES6), 143 135 bytes

Editar: guardado 8 bytes gracias a Neil

Una implementación utilizando programación funcional.

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 y comentó

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)

Manifestación

Aunque funciona para 6511y 10000, no los incluiré aquí, ya que tiende a ser un poco lento.

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
fuente
1
JS puede hacer 0..n-1rangos bastante facilidad: [...Array(n).keys()]. Esto requiere no uno, sino dos casos especiales, pero todavía estoy por delante: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 bytes

Un puerto rubí de mi respuesta en realidad . Sugerencias de golf bienvenidas.

Editar: -4 bytes de la eliminación, apero +9 bytes de la corrección de un error donde se 1devuelve nil. -1 byte gracias a 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
fuente
No es necesario a=. Desafortunadamente, regresas nilpara n = 1 :(. (n.prime_division<<[2,1])Corrige eso. No estoy seguro si hay una forma más golfista.
m-chrzan
(n%8<1?n/2:n).prime_division...guarda otros 2 bytes.
m-chrzan
@ m-chrzan aes un remanente de un intento de golf anterior. Gracias por el recordatorio ay por el aviso 1.
Sherlock9
Puede guardar un byte utilizando en .reduce :lcmlugar de .reduce(:lcm).
Cyoce
1

JavaScript (ES 2016) 149

Implementación de referencia de Python portada a JS. Faltan algunos componentes sofisticados de Pyhton en js, like gcdy pow, y la comprensión de la matriz no es estándar en ES 6. Esto funciona en 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')

Menos 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
fuente
modpow recursivo es más corto:p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Olivier Grégoire
1

Java, 209 207 202 194 192 bytes

Código (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;}}

funciones adicionales (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;}

Prueba y sin 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);
  }
}

Notas

  • el uso de aser un intes más corto que si tuviera que usar un booleanpara realizar mis pruebas.
  • Sí, es más corto para valueOftodos los nuevos BigIntegerque crear una función separada (hay 5, más la ONEconstante es un obsequio).
  • El algoritmo es diferente al algoritmo @Master_ex ', por lo que no se trata solo de una nueva publicación de golf. Además, este algoritmo es mucho menos eficiente ya que gcdse calcula una y otra vez para los mismos valores.

Afeitado

  1. 209 -> 207 bytes:
    • if(...)a=...; -> a=...?...:1;
    • a==1 -> a<2
  2. 207 -> 202 bytes
    • Se libró del BigIntegergolf gcdy modPowpara int.
  3. 202 -> 194 bytes
    • bucle modPow-> recursivo
  4. 194 -> 192 bytes
    • ==1-> <2(parece funcionar para todos los casos de prueba, no sé para otros números).
Olivier Grégoire
fuente
¡Oye! He notado que la salida no es la esperada. Vea la pregunta para los resultados esperados. Personalmente, a menudo escribo pruebas unitarias antes de comenzar a jugar golf mi código, ¡ayuda! Supongo que el problema podría ser el modPow en los enteros, también tuve este problema y por eso usé BigInteger al final.
Master_ex
Hmmm ... estoy sorprendido, dejo que mis pruebas se ejecuten en cada cambio. Comprobaré qué pasa.
Olivier Grégoire
1
@ Master_ex lo arreglé. Volver a la versión anterior está bien.
Olivier Grégoire
Me parece que su método modpow recursivo es pbastante inteligente. Al principio intenté usar solo enteros, pero como mencioné en mi respuesta, tuve problemas de precisión y es por eso que me mudé a BigInteger(es decir, Math.pow(3, 100)%101regresé en 60.0lugar de 1). Su implementación es inmune a esto porque realiza el mod en cada iteración. Sin embargo, todavía sufre de un error. Para grandes m paún puede devolver resultados incorrectos. Además, debido a la recursividad, StackOverflowErrorpuede ocurrir fácilmente para una entrada grande con el tamaño de pila predeterminado.
Master_ex
@ Master_ex Sí, eso es consecuencia de la restricción de inttipos. Podría usar longs en lugar de ints, eso sería 8 bytes adicionales. Pero en mi opinión, todos los casos de prueba son válidos, así que lo dejo así. StackOverflowErrorpuede suceder, pero así es como funciona el recursivo. Existen métodos para limitar a 32 pilas, pero estos usan muchos muchos más bytes. Esta implementación es frágil, sí, tienes toda la razón. Pero es lo suficientemente fuerte para los casos de prueba.
Olivier Grégoire
1

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

Importaciones, 19 bytes

import java.math.*;

Explicación

Es una implementación sencilla. Los co-primos se calculan en la Set ppotencia k de cada uno y se utiliza para verificar si es igual a 1 módulo n.

Tuve que usar BigInteger debido a problemas de precisión.

Uso

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

Sin golf

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

Cualquier sugerencia para jugar más al golf es bienvenida :-)

Actualizar

  • No hay elementos fuera de las funciones que mantienen el estado.
  • Seguí el consejo de Olivier Grégoire y guardé 1 byte de B()
  • Se eliminó el k()método y el conjunto p(primos).
  • Eliminado no se requiere fundición a int.
  • Se agregaron varags y se usaron en lugar de while.
Master_ex
fuente
¿Puede tener una versión sin golf (con saltos de línea, comentarios aquí y allá, etc.)
OldBunny2800
@ OldBunny2800: Sí, claro. Sin embargo, lo haré más tarde hoy porque ahora estoy ocupado.
Master_ex
@ OldBunny2800: agregué una versión sin golf :-)
Master_ex
Hmmm ... no estoy seguro si esto cuenta ya que no es ni una función ni un programa. Si es una función, hay elementos externos que mantienen el estado, lo que lo convierte en un método de facto (la función es pura entrada-> salida sin estado externo), si es un programa, falta todo el método principal. Si mis interpretaciones son incorrectas, ¡dígamelo! Creo que es mejor incluir k(int)en el bucle, ya que es de una sola línea y se puede hacer. Además, la constante O también se puede poner en el cmétodo. ¡Supongo que ganarás bytes al hacerlo!
Olivier Grégoire
Concretamente, while(n>1&&!p.stream().allMatch(x->B((int)x).modPow(B(k), B(n)).equals(O)))elimina bytes y corrige los problemas que mencioné si vuelve a poner el conjunto y la constante en el método. Además, utiliza Odos veces, reemplace por B(1)para reducir bytes.
Olivier Grégoire
1

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

Otro puerto de mi aplicación C .

Pruébalo en Ideone

techo
fuente
1

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

Un puerto de mi aplicación C .

Pruébalo en Ideone

techo
fuente
0

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

Versión sin golf:

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

Pruebas:

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

Salida:

1
2
4
12
100
52
84
3056
500
rnso
fuente
0

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

Utiliza un algoritmo de exponenciación modular lento, calcula el GCD con demasiada frecuencia y ya no pierde memoria.

Sin golf:

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

Pruébalo en Ideone

techo
fuente
0

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

menos 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

resultados

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