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
Respuestas:
Mathematica, 16 bytes
Bien...
fuente
Python,
767367 bytesPrué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.
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 .
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
any
devuelve 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) .fuente
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).Mathematica sin incorporado,
5857 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:
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.
fuente
EulerPhi
para obtenerLCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&
57 bytes.Plantillas consideradas dañinas , 246 bytes
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).fuente
Haskell,
5756 bytesfuente
Jalea, 2 bytes
Gracias por la construcción, @ Lynn
fuente
Pyth -
191817 bytesUn byte guardado gracias a @TheBikingViking.
Fuerza bruta directa.
Pruébelo en línea aquí .
fuente
f!smt
es un byte más corto.Rubí,
5956 bytesfuente
J,
2827 bytesLa 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 2 ⋯ p 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.
Explicación
fuente
En realidad,
3028251926 bytesLa función Carmichael,
λ(n)
donden = 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áximasp_i**k_i
que se dividen enn
. Dado que para cada potencia principal, excepto donde está2
la 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 de2**k
dóndek ≥ 3
, solo verificamos si se2**3 = 8
divide aln
comienzo 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!
Ungolfing
fuente
totient
ygcd
builtins. Esto sería más corto si Realmente lo tuvieralcm
directamente, pero no me importa tanto y eso solo eliminaría 4 bytes como máximo, de todos modos.JavaScript (ES6),
143135 bytesEditar: guardado 8 bytes gracias a Neil
Una implementación utilizando programación funcional.
Ungolfed y comentó
Manifestación
Aunque funciona para
6511
y10000
, no los incluiré aquí, ya que tiende a ser un poco lento.fuente
0..n-1
rangos 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
Ruby,
101869190 bytesUn puerto rubí de mi respuesta en realidad . Sugerencias de golf bienvenidas.
Editar: -4 bytes de la eliminación,
a
pero +9 bytes de la corrección de un error donde se1
devuelvenil
. -1 byte gracias a Cyoce.Ungolfing
fuente
a=
. Desafortunadamente, regresasnil
para n = 1 :(.(n.prime_division<<[2,1])
Corrige eso. No estoy seguro si hay una forma más golfista.(n%8<1?n/2:n).prime_division...
guarda otros 2 bytes.a
es un remanente de un intento de golf anterior. Gracias por el recordatorioa
y por el aviso1
..reduce :lcm
lugar de.reduce(:lcm)
.JavaScript (ES 2016) 149
Implementación de referencia de Python portada a JS. Faltan algunos componentes sofisticados de Pyhton en js, like
gcd
ypow
, y la comprensión de la matriz no es estándar en ES 6. Esto funciona en Firefox.Menos golf
fuente
p=(a,b,c)=>b?a*p(a,b-1,c)%c:1;
Java,
209207202194192 bytesCódigo (96 bytes):
funciones adicionales (96 bytes):
Prueba y sin golf
Notas
a
ser unint
es más corto que si tuviera que usar unboolean
para realizar mis pruebas.valueOf
todos los nuevosBigInteger
que crear una función separada (hay 5, más laONE
constante es un obsequio).gcd
se calcula una y otra vez para los mismos valores.Afeitado
if(...)a=...;
->a=...?...:1;
a==1
->a<2
BigInteger
golfgcd
ymodPow
paraint
.modPow
-> recursivo==1
-><2
(parece funcionar para todos los casos de prueba, no sé para otros números).fuente
p
bastante 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é aBigInteger
(es decir,Math.pow(3, 100)%101
regresé en60.0
lugar de1
). Su implementación es inmune a esto porque realiza el mod en cada iteración. Sin embargo, todavía sufre de un error. Para grandesm
p
aún puede devolver resultados incorrectos. Además, debido a la recursividad,StackOverflowError
puede ocurrir fácilmente para una entrada grande con el tamaño de pila predeterminado.int
tipos. 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í.StackOverflowError
puede 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.Java8
3819 +287295253248241 =325333272267260 bytesImportaciones, 19 bytes
Explicación
Es una implementación sencilla. Los co-primos se calculan en la
Set p
potencia 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
Sin golf
Cualquier sugerencia para jugar más al golf es bienvenida :-)
Actualizar
B()
k()
método y el conjuntop
(primos).fuente
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 elc
método. ¡Supongo que ganarás bytes al hacerlo!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, utilizaO
dos veces, reemplace porB(1)
para reducir bytes.Java,
165 163 158 152143 bytesOtro puerto de mi aplicación C .
Pruébalo en Ideone
fuente
C ++,
208 200 149 144 140134 bytesUn puerto de mi aplicación C .
Pruébalo en Ideone
fuente
Raqueta 218 bytes
Versión sin golf:
Pruebas:
Salida:
fuente
C,
278 276 272 265 256 243 140 134125 bytesUtiliza un algoritmo de exponenciación modular lento, calcula el GCD con demasiada frecuencia y ya no pierde memoria.
Sin golf:
Pruébalo en Ideone
fuente
Axioma 129 bytes
menos golf
resultados
fuente