Este desafío es bastante simple que es básicamente todo en el título: te dan un número entero positivo N y usted debe devolver el menor entero positivo que no es un divisor de N .
Un ejemplo: los divisores de N = 24 son 1, 2, 3, 4, 6, 8, 12, 24
. El entero positivo más pequeño que no está en esa lista es 5 , así que ese es el resultado que debería encontrar su solución.
Esta es la secuencia OEIS A007978 .
Reglas
Puede escribir un programa o una función y utilizar cualquiera de nuestros métodos estándar para recibir entradas y proporcionar salidas.
Puede usar cualquier lenguaje de programación , pero tenga en cuenta que estas lagunas están prohibidas de forma predeterminada.
Este es el código de golf , por lo que gana la respuesta válida más corta, medida en bytes .
Casos de prueba
Los primeros 100 términos son:
2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2,
3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3,
2, 3, 2, 4, 2, 3, 2, 3, 2, 7, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2,
3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 5, 2, 3, 2, 3
En particular, asegúrese de que su respuesta funcione para las entradas 1 y 2, en cuyo caso el resultado es mayor que la entrada.
Y para algunos casos de prueba más grandes:
N f(N)
1234567 2
12252240 19
232792560 23
fuente
Respuestas:
Mathematica, 19 bytes (codificación UTF-8)
Función sin nombre que toma un argumento entero distinto de cero y devuelve un entero positivo. La barra vertical aproximadamente a la mitad es en realidad el carácter de tres bytes U + 2223, que denota la relación de divisibilidad en Mathematica. Explicación:
Editado para agregar: ngenisis señala que
//.
, por defecto, iterará un máximo de 65536 veces. Entonces, esta implementación funciona para todos los números de entrada menores que el mínimo común múltiplo de los enteros del 1 al 65538 (en particular, en todos los números con un máximo de 28436 dígitos), pero técnicamente no para todos los números. Se puede reemplazarx//.y
conReplaceRepeated[x,y,MaxIterations->∞]
para solucionar este defecto, pero obviamente a costa de 34 bytes adicionales.fuente
For
,While
etcPyth, 3 bytes
Básicamente,
f
repite el código hasta que%QT
(Q % T
dondeT
está la variable de iteración) sea verdadero.Pruébelo en línea aquí.
fuente
.V1In%Qb0bB
vi tu respuesta y ya no me siento tan increíble.JavaScript (ES6),
2523 bytesNota: Una cosa interesante aquí es que el
k
parámetro se inicializa ex nihilo en la primera iteración. Esto funciona porquen % undefined
esNaN
(falso como se esperaba) e-~undefined
igual1
. En las próximas iteraciones,-~k
es esencialmente equivalente ak+1
.Prueba
Mostrar fragmento de código
fuente
Python,
433635 bytesfuente
Hexagonía , 12 bytes.
Embiggeded:
Pruébalo en línea!
fuente
R, 28 bytes
Bastante sencillo, nada lujoso. Toma la entrada de stdin, incrementa el valor
T
hasta que eli
móduloT
no sea cero.Si quieres algo un poco más elegante, hay lo siguiente para 29 bytes :
Explicado:
fuente
which.min
, pero luego vi la edición y parece quematch
hace un trabajo similar.T
, ahorrando la necesidad de definirlo antes delwhile
ciclo.while
enfoque, lo cual está bien, ya que requiere mucha memoria para el gran N. ElT
truco es una de esas delicias que es excelente para el golf pero absolutamente horrible para la programación real. (Y, por supuesto, también puedes usarloF
cuando necesites a0
.)%%
tiene prioridad sobre+
, por lo que los parens todavía son necesarios:(0:i+1)
con el mismo número de bytes que1:(i+1)
. De hecho, tuve el primero originalmente, pero lo cambié por el segundo ya que es más fácil de leer.Haskell, 26 bytes
¡Todo el mundo se olvida
until
!fuente
Brachylog , 10 bytes
Pruébalo en línea!
Esto salió muy similar a (pero más corto que) la solución original de Fatalize. Fatalize ha cambiado a un algoritmo diferente que se vincula con este a través de un método diferente, por lo que tendré que explicarlo yo mismo:
Cuando invertimos la función, intercambiando "entrada" y "salida", obtenemos un algoritmo bastante razonable (expresado de una manera incómoda): "intente posibles enteros positivos, en su orden natural (es decir, 1 hacia arriba), hasta que encuentre uno que no se puede multiplicar por nada para producir la entrada ". Brachylog no realiza cálculos de punto flotante a menos que se conozcan todas las entradas, por lo que solo considerará el entero A.
fuente
Brachylog ,
1110 bytesPruébalo en línea!
Explicación
fuente
VACA, 174 bytes
Pruébalo en línea!
Este código es solo parcialmente mío: implementa un algoritmo de módulo que porté desde brainfuck. El resto del código es mío. Sin embargo, como no escribí el algoritmo de módulo, no he investigado realmente cómo funciona y no puedo documentar esa parte del código. En cambio, daré mi desglose habitual, seguido de una explicación más detallada de por qué funciona el código.
Desglose de código
Explicación
El código primero lee el entero en [0]. Cada iteración del bucle principal (líneas 2 a 26) incrementa [1], luego copia todo lo necesario al algoritmo de módulo, que escupe su resultado en [5]. Si [5] contiene algún valor, entonces [1] es el número que necesitamos imprimir. Lo imprimimos y luego forzamos a salir del programa.
Dado que COW es un derivado de brainfuck, funciona de manera relativamente similar a la forma en que funciona brainfuck: una tira infinita de cinta, puede moverse hacia la izquierda o hacia la derecha, aumentar o disminuir, y hacer un "bucle" mientras el valor actual de la cinta no es cero. Además de brainfuck, COW viene con un par de características útiles.
El verdadero punto de interés aquí es la instrucción 3,
mOO
. El intérprete lee el valor de la cinta actual y ejecuta una instrucción basada en ese valor de la cinta. Si el valor es menor que 0, mayor que 11 o igual a 3, el intérprete finaliza el programa. Podemos usar esto como una salida rápida y sucia del bucle principal (y del programa por completo) una vez que hayamos encontrado nuestro no divisor. Todo lo que tenemos que hacer es imprimir nuestro número, borrar [1] (conOOO
), disminuirlo a -1 conMOo
, y luego ejecutar la instrucción -1 a través de lamOO
cual finaliza el programa.La cinta en sí para este programa funciona de la siguiente manera:
El algoritmo de módulo borra naturalmente [2], [3], [6] y [7] al final de la operación. El contenido de [4] se sobrescribe con el registro pegar en la línea 4, y [5] es cero cuando [0] es divisible por [1], por lo que no tenemos que borrarlo. Si [5] no es cero, forzamos el cierre en la línea 23 para no tener que preocuparnos por eso.
fuente
05AB1E , 7 bytes
Pruébalo en línea!
Explicación
fuente
Jalea , 5 bytes
Pruébalo en línea!
Explicación:
Este es un horrendo abuso de
#
; Hay muchos operadores en este programa, pero un montón de operandos faltantes.#
realmente quiere1
que se proporcione explícitamente por alguna razón (de lo contrario, intenta ingresar la entrada por defecto); sin embargo, todo lo demás que no se especifica en el programa por defecto es la entrada del programa. (Entonces, por ejemplo, si da 24 como entrada, este programa encuentra los primeros 24 números que no dividen 24, luego devuelve el primero; es un poco despilfarrador, pero funciona).fuente
2%@1#
C,
3235 bytesEditar: agregado
i=1
en el bucleUso
Versión completa del programa, 64 bytes:
fuente
C #,
3937 bytes¡Ahorré dos bytes gracias a Martin!
fuente
Perl, 19 bytes
18 bytes de código +
-p
bandera.Para ejecutarlo:
Explicaciones no muy detalladas :
-
$.
es una variable especial cuyo valor predeterminado es el número de línea actual del último identificador de archivo al que se accedió (stdin aquí), por lo que después de leer la primera línea de entrada, se establece en 1.-
$_
contiene la entrada y se imprime implícitamente al final (gracias a la-p
bandera).-
redo
(en ese contexto) considera que el programa está en un bucle y rehace la iteración actual (solo$.
será diferente ya que se incrementó).- Entonces, si encontramos el número más pequeño (almacenado
$.
) que no se divide$_
, entonces lo configuramos,$_
de lo contrario, probamos el siguiente número (gracias aredo
).fuente
Octava / MATLAB,
2624 bytesfind(...,1)
devuelve el índice (1
basado en) del primer elemento distinto de cero del vector en el primer argumento. El primer argumento es[n mod 1, n mod 2, n mod 3, n mod 4,...,n mod (n+1)]
Eso significa que tenemos que agregar+1
al índice, ya que comenzamos a probar en1
. Gracias @Giuseppe por -2 bytes.Pruébalo en línea!
fuente
@(n)find(mod(n,1:n+1),1)
es más corto, ¿no es así?Jalea , 6 bytes
Pruébalo en línea!
Explicación:
fuente
[1, 1, 1, 1, 5, ...]
.Perl 6 , 17 bytes
Intentalo
Expandido:
fuente
05AB1E , 6 bytes
Pruébalo en línea!
Además, deletrea "¡ENLACE!" ... Un poco ...
fuente
Jalea , 5 bytes
Pruébalo en línea!
Cómo funciona
fuente
Python 2.7.9, 32 bytes
Prueba de ideona
Recursivamente cuenta los posibles no divisores
d
. Es más corto recursivamente el incremento del resultado que la salidad
. El1
booleano de logra un desplazamiento deTrue
, que es igual1
, pero comod==1
siempre es un divisor, la salida siempre se convierte en un número.Python 2.7.9 se utiliza para permitir permitir
0or
. Las versiones que comienzan con 2.7.10 intentarán analizarse0or
como el inicio de un número octal y recibirán un error de sintaxis. Mira esto en Ideone .fuente
En realidad , 7 bytes
Pruébalo en línea! (nota: esta es una solución muy lenta y tomará mucho tiempo para casos de prueba grandes)
Explicación:
fuente
Haskell , 29 bytes
La expresión
[k|k<-[2..]]
solo crea una lista infinita[2,3,4,5,...]
. Con la condiciónmod n k>0
solo permitimos aquellosk
en la lista que no se dividenn
. Anexar!!0
solo devuelve la primera entrada (la entrada en el índice0
) de esa lista.Pruébalo en línea!
fuente
Dyalog APL , 8 bytes
1⍳⍨
posición del primer verdadero en0≠
los valores distintos de cero de⍳|
los restos de división de 1 ... N cuando se divide por⊢
norteTryAPL en línea!
Nota: esto funciona para 1 y 2 porque
1⍳⍨
devuelve 1 + la longitud de su argumento si no se encuentra ninguno.fuente
julia, 28 bytes
Nota: como
1:N+2
no asigna memoria, no hay problemas de memoria paraN
s grandes- @flawr
N+2
guarda algunos bytes- La sugerencia de @Martin guardó 1 bytes
fuente
QBIC , 14 bytes
Explicación:
fuente
PHP, 30 bytes
si se ejecuta desde la consola con la
-r
opción (thx a @ ais523)32 bytes
gracias a @manatwork por eliminar 1 byte
33 bytes (original)
fuente
<?
no tiene que ser parte de su recuento de bytes (porque PHP tiene un modo de línea de comandos que no lo requiere).<1
lugar de==0
.for(;!($argv[1]%$i);$i++);echo$i;
. La tuya es la evolución natural de la mía. ¡Esto tiene mi voto a favor!Cubix ,
1412 bytesGuardado 2 bytes gracias a MickyT.
Intentalo
Explicación
En forma de cubo, el código es:
Básicamente, esto solo toma la entrada y comienza un contador. Luego verifica cada valor sucesivo del contador hasta que encuentre uno que no sea un factor de la entrada.
fuente
I2/L/);?%<@O
por un par de bytes menos. El mismo proceso general, solo un camino diferente> <> , 15 +3 = 18 bytes
Se espera que la entrada esté en la pila al inicio del programa, por lo que +3 bytes para el
-v
indicador. Pruébalo en línea!fuente
Medusa ,
1210 bytesToma entradas de STDIN y salidas a STDOUT. Pruébalo en línea!
Martin Ender ahorró 2 bytes, ¡gracias!
Explicación
Esta parte es una función que utiliza el valor de entrada en su definición.
Esta
~
celda tiene una función, por lo que voltea sus argumentos: produce la función binaria "argumento izquierdo módulo (|
) argumento derecho". La función de módulo incorporada en Jellyfish toma sus argumentos en el orden inverso.A esta
~
celda se le asigna un valor y una función, por lo que realiza una aplicación parcial: produce la función binaria "input (i
) modulo right argumento". Llamemos a esa función f .La
\
celda-tiene dos funciones, por lo que realiza la iteración: produce la función unaria "increment (>
) hasta que la función f aplicada a valores anteriores y actuales da un resultado verdadero (distinto de cero), luego devuelve el valor actual". Esto significa que el argumento se incrementa hasta que no divide la entrada.Finalmente, aplicamos esta función al valor inicial
1
e imprimimos el resultado conp
.fuente