Inspirado por esta pregunta en Mathematics .
El problema
Dejar
n
ser un número natural≥ 2
. Tome el divisor más grande den
, que es diferente den
sí mismo, y restarlon
. Repita hasta que llegue1
.
La pregunta
¿Cuántos pasos se necesitan para alcanzar 1
un número dado n ≥ 2
?
Ejemplo detallado
Dejar
n = 30
.
El mayor divisor de:
1. 30 is 15 --> 30 - 15 = 15
2. 15 is 5 --> 15 - 5 = 10
3. 10 is 5 --> 10 - 5 = 5
4. 5 is 1 --> 5 - 1 = 4
5. 4 is 2 --> 4 - 2 = 2
6. 2 is 1 --> 2 - 1 = 1
Se necesitan 6 pasos para llegar 1
.
Entrada
- La entrada es un número entero
n
, donden ≥ 2
. - Su programa debe admitir la entrada hasta el valor entero máximo del idioma.
Salida
- Simplemente envíe el número de pasos, como
6
. - Los espacios en blanco iniciales o finales o las nuevas líneas están bien.
Ejemplos
f(5) --> 3
f(30) --> 6
f(31) --> 7
f(32) --> 5
f(100) --> 8
f(200) --> 9
f(2016^155) --> 2015
Requisitos
- Puede obtener información de
STDIN
, argumentos de línea de comando, como parámetros de función o del equivalente más cercano. - Puedes escribir un programa o una función. Si es una función anónima, incluya un ejemplo de cómo invocarla.
- Este es el código de golf, por lo que la respuesta más corta en bytes gana.
- Las lagunas estándar no están permitidas.
Esta serie también se puede encontrar en OEIS: A064097
Un cuasi-logaritmo definido inductivamente por
a(1) = 0
ya(p) = 1 + a(p-1)
sip
es primo ya(n*m) = a(n) + a(m)
sim,n > 1
.
code-golf
math
arithmetic
insertusernamehere
fuente
fuente
2^32 - 1
. El resto depende de usted y su sistema. Espero, esto es lo que quisiste decir con tu pregunta.Respuestas:
Jalea , 9 bytes
Pruébalo en línea! o verificar todos los casos de prueba .
Antecedentes
La definición de secuencia A064097 implica que
Por la fórmula del producto de Euler
donde φ denota la función totient de Euler y p varía solo sobre los números primos.
Combinando ambos, deducimos la propiedad
donde ω denota el número de factores primos distintos de n .
Aplicando la fórmula resultante k + 1 veces, donde k es lo suficientemente grande como para que φ k + 1 (n) = 1 , obtenemos
De esta propiedad, obtenemos la fórmula
donde se mantiene la última igualdad porque ω (1) = 0 .
Cómo funciona
fuente
05AB1E ,
1311 bytesCódigo:
Explicación:
Utiliza la codificación CP-1252 . Pruébalo en línea! .
fuente
[¼Ñü-¤ÄD#]¾
- Estaba cerca de afeitarme un byte con pares, oh bueno ...[Ð#Ò¦P-¼]¾
.Ð
es mejor queDD
.Pyth, 11 bytes
Banco de pruebas
Un bucle sencillo de repetir hasta que sea verdadero.
Explicación:
fuente
f
Ilter.f
?f
sin un segundo argumento itera sobre todos los enteros positivos a partir de1
y devuelve el primer valor que da verdadero en la declaración interna. Este valor no se utiliza en este programa, por lo que devuelve el número de veces que se ejecutó. No indocumentado, simplemente no ortodoxo :) Si ayuda, puede pensar en esto como unfor
bucle como:for(int i=1; some_condition_unrelated_to_i; i++) { change_stuff_that_affects_condition_but_not_i;}
f <l:T> <none>
),f
es la primera entrada dondeA(_)
termina la verdad[1, 2, 3, 4...]
.Python 2,
5049 bytesEsto no va a terminar ese último caso de prueba en el corto plazo ...
Alternativamente, aquí hay un byte de 48 que devuelve en
True
lugar de1
paran=2
:fuente
Jalea , 10 bytes
Pruébalo en línea! o verificar la mayoría de los casos de prueba . Los últimos casos de prueba finalizan rápidamente localmente.
Cómo funciona
fuente
Retina , 12
Esto supone la entrada dada en unario y la salida dada en decimal. Si esto no es aceptable, podemos hacer esto por 6 bytes más:
Retina , 18
Pruébelo en línea: se agregó la primera línea para ejecutar todos los casos de prueba de una vez.
Lamentablemente, esto utiliza unario para los cálculos, por lo que la entrada de 2016 155 no es práctica.
1
sfuente
\b
.Pyth -
151413 bytesLa carcasa especial
1
realmente me está matando.Pruébelo en línea aquí .
fuente
1
?1
is[]
, que causa un error cuando tomo el primer elemento. Tengo que ponerlo en un caso especial para que vuelva de1
nuevo para que.u
termine el punto fijo. Encontré una mejor manera que.x
try, excepto que es lo que me ahorró esos 2 bytes..u
punto fijo eventualmente alcanzará1
todas las entradas, en cuyo punto tendrá que estar en una carcasa especial.JavaScript (ES6),
* 4438Editar 6 bytes guardados gracias @ l4m2
(* 4 marcado sigue siendo 4)
Función recursiva
Menos golf
Prueba
fuente
f=(n,d=n)=>n>1?n%--d?f(n,d):f(n-d)+1:0
?Mathematica, 36 bytes
Una función sin nombre toma los mismos bytes:
Esta es una implementación muy sencilla de la definición como una función recursiva.
fuente
Octava,
595855 bytesEjecuciones de muestra:
fuente
end
necesario en octava?Haskell, 59 bytes
Uso:
Puede ser un poco ineficiente para grandes números debido a la generación de la lista.
fuente
<1
lugar de==0
guardar unos pocos bytes:f 1=0;f n=1+f(n-last[a|a<-[1..n
div2],mod n a<1])
Julia,
56504539 bytesEsta es una función recursiva que acepta un entero y devuelve un entero.
Sin golf:
Pruébalo en línea! (incluye todos los casos de prueba)
¡Ahorré 6 bytes gracias a Martin Büttner y 11 gracias a Dennis!
fuente
PowerShell v2 +, 81 bytes
La más brutal de las fuerzas brutas.
Toma entrada
$a
, ingresa unfor
bucle hasta que$a
sea menor o igual que1
. Cada ciclo pasamos por otrofor
ciclo que cuenta hacia atrás$a
hasta que encontremos un divisor (!($a%$i
). En el peor de los casos, lo encontraremos$i=1
como divisor. Cuando lo hagamos, incremente nuestro contador$j
, reste nuestro divisor$a-=$i
y prepárese$i=0
para salir del bucle interno. Eventualmente, llegaremos a una condición en la que el bucle externo es falso (es decir,$a
ha alcanzado1
), por lo que sale$j
y sale.Precaución : esto llevará mucho tiempo en números más grandes, especialmente en números primos. La entrada de 100,000,000 toma ~ 35 segundos en mi computadora portátil Core i5. Editar : solo probé con
[int]::MaxValue
(2 ^ 32-1), y tardó ~ 27 minutos. No es demasiado mala, supongo.fuente
Matlab, 58 bytes
fuente
Japt , 12 bytes (no competidor)
¡Pruébelo en línea! No compite porque usa un montón de características que se agregaron mucho después de que se publicó el desafío.
Cómo funciona
Esta técnica se inspiró en la respuesta 05AB1E . Se usó una versión anterior
²¤
(empuje un 2, corte los dos primeros elementos) en lugar deÅ
porque es un byte más corto ques1
(espacio final de la nota); Solo me di cuenta después del hecho de que debido a que esto agrega un 2 al final de la matriz y los segmentos desde el principio , de hecho falla en cualquier número compuesto impar, aunque funciona en todos los casos de prueba dados.fuente
Python 3,
75, 70, 67 bytes.Esta es una solución recursiva bastante sencilla. Lleva mucho tiempo para los casos de prueba de gran número.
fuente
> <>, 32 bytes
Espera el número de entrada,,
n
en la pila.Este programa construye la secuencia completa en la pila. Como el único número que puede conducir
1
es2
, la construcción de la secuencia se detiene cuando2
se alcanza. Esto también hace que el tamaño de la pila sea igual al número de pasos, en lugar del número de pasos +1.fuente
Ruby, 43 bytes
Encuentre el número más pequeño de
i
manera que sex
dividax-i
y se repita hasta que alcancemos1
.fuente
Haskell, 67 bytes
Aquí está el código:
Y aquí hay una razón por la que Haskell es increíble:
Sí, en Haskell puedes definir
-->
ser equivalente a==
.fuente
Matlab, 107 bytes
fuente
MATL,
1716 bytesPruébalo en línea
Explicación
fuente
C99,
6261 bytes1 byte jugado por @Alchymist.
Llame como f (x, & y), donde x es la entrada e y es la salida.
fuente
Julia,
3936 bytesPruébalo en línea!
fuente
Clojure,
116104bytes-12 bytes filtrando un rango para encontrar múltiplos, luego usando
last
uno para obtener el mayorSolución ingenua que básicamente solo resuelve el problema tal como lo describe el OP. Desafortunadamente, encontrar el divisor más grande solo ocupa la mitad de los bytes utilizados. Al menos debería tener mucho espacio para jugar golf desde aquí.
Pregolfed y prueba:
fuente
Perl 6 , 35 bytes
Pruébalo en línea!
Cómo funciona
fuente
Pyth,
1716 bytesPruébalo en línea! (El
y.v
final es para llamadas a funciones)Original de 17 bytes:
Pruébalo en línea! (El
y.v
final es para llamadas a funciones)(De hecho, respondí esa pregunta con este programa Pyth).
fuente
u
probablemente sea más corta que la recursividad real.Pyke, 11 bytes (sin competencia)
Esto utiliza un nuevo comportamiento en el que si se produce una excepción después de un goto, restaura el estado anterior al goto (excepto las definiciones de variables) y continúa. En este caso es equivalente al siguiente código de Python:
Todo esto es posible usando Pyke sin una construcción de bucle while - ¡yay goto!
Pruébalo aquí!
fuente
JavaScript (ES6),
7054 bytesImplementación de la fórmula recursiva proporcionada, pero ahora actualizada para usar la recursividad para encontrar el divisor también.
fuente
Perl, 57 + 1 (
-p
bandera) = 58 bytesUso:
Sin golf:
fuente
Clojure,
9896 bytesutiliza
for
:when
para encontrar el divisor más grande, bucles hasta que no se encuentre dicho valor mayor que uno.fuente