Un número entero positivo k
es un número de Loeschian si
k
se puede expresar comoi*i + j*j + i*j
parai
,j
números enteros.
Por ejemplo, los primeros números positivos de Loeschian son: 1
( i=1
, j=0
); 3
( i=j=1
); 4
( i=2
, j=0
); 7
( i=2
, j=1
); 9
( i=-3
, j=3
); ... Tenga en cuenta que i
, j
por cierto k
, no son únicos. Por ejemplo, 9
también pueden generarse con i=3
, j=0
.
Otras caracterizaciones equivalentes de estos números son:
k
se puede expresar comoi*i + j*j + i*j
parai
,j
números enteros no negativos. (Para cada par de enterosi
,j
hay un par de enteros no negativos que dan lo mismok
)Hay un conjunto de
k
hexágonos contiguos que forman una teselación en una cuadrícula hexagonal (ver ilustraciones parak = 4
y parak = 7
). (Debido a esta propiedad, estos números encuentran aplicación en redes móviles de comunicación celular ).Vea más caracterizaciones en la página OEIS de la secuencia.
El reto
Dado un número entero positivo , genera un resultado verdadero si es un número de Loeschian , o un resultado falso de lo contrario.
El programa o la función deben manejar (digamos en menos de un minuto) entradas hasta 1000
, o hasta limitaciones de tipo de datos.
Código de golf. Las victorias más cortas.
Casos de prueba
Los siguientes números deberían generar un resultado verdadero:
1, 4, 7, 12, 13, 108, 109, 192, 516, 999
Los siguientes números deberían generar un resultado falso:
2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
fuente
i, j non-negative integers
o9 (i=-3, j=3)
, ¿cuál es?Respuestas:
Jalea ,
119 bytesPruébalo en línea! o verificar todos los casos de prueba .
Fondo
En los resultados elementales sobre la forma cuadrática binaria a² + ab + b² , el autor demuestra el siguiente teorema sobre los números de Löschian.
Como se señaló en la página OEIS relevante , dado que todos los enteros son congruentes con 0 , 1 o 2 módulo 3 , el número 3 es el único primo congruente con 0 , y todos los números de la forma (6k + 1) son congruentes con 1 , el teorema puede expresarse alternativamente como sigue.
Un número entero no negativo n es un número de Löschian si y solo si todos los factores primos de n que son congruentes con 2 módulo 3 tienen exponentes pares.
Cómo funciona
fuente
Retina ,
6663454336 bytesA pesar del título que dice Retina, esta es solo una expresión regular .NET que acepta representaciones unarias de números de Loeschian.
Las entradas 999 y 1000 toman bastante menos de un segundo.
Pruébalo en línea! (La primera línea permite un conjunto de pruebas separadas por salto de línea, y las dos siguientes se encargan de la conversión a unario por conveniencia).
Explicación
La solución se basa en la clasificación de que la entrada se puede escribir como
i*i + j*(i + j)
positivai
y no negativaj
(ya que no tenemos que manejar la entrada0
), y eson*n
es solo la suma de los primerosn
enteros impares. Jugar al golf fue un ejercicio interesante en referencias avanzadas.Una "referencia hacia adelante" es cuando coloca una referencia hacia atrás dentro del grupo al que hace referencia. Por supuesto, eso no funciona cuando el grupo se usa por primera vez, ya que no hay nada a lo que hacer referencia todavía, pero si lo coloca en un bucle, la referencia inversa obtiene la captura de la iteración anterior cada vez. Esto a su vez, le permite construir una captura más grande con cada iteración. Esto se puede usar para crear patrones muy compactos para cosas como números triangulares, cuadrados y números de Fibonacci.
Como ejemplo, usando el hecho de que los cuadrados son solo sumas de los primeros
n
enteros impares, podemos hacer coincidir una entrada cuadrada como esta:En la primera iteración,
..\1
no puede funcionar, porque\1
todavía no tiene un valor. Entonces comenzamos con la^.
captura de un solo personaje en grupo1
. En las iteraciones posteriores,^.
ya no coincide debido al ancla, pero ahora..\1
es válido. Coincide con dos caracteres más que la iteración anterior y actualiza la captura. De esta manera emparejamos números impares crecientes, obteniendo un cuadrado después de cada iteración.Ahora, desafortunadamente, no podemos usar esta técnica tal como está. Después de hacer coincidir
i*i
, necesitamos obteneri
también, para poder multiplicarlo porj
. Una manera simple (pero larga) de hacer esto es hacer uso del hecho de que la coincidenciai*i
requierei
iteraciones, de modo que hemos capturado lasi
cosas en grupo1
. Ahora podríamos usar grupos de equilibrio para extraer estoi
, pero como dije, eso es costoso.En cambio, descubrí una forma diferente de escribir esta "suma de enteros impares consecutivos" que también produce
i
un grupo de captura al final. Por supuesto, eli
tercer número es justo2i-1
. Esto nos da una manera de incrementar la referencia directa solo en 1 en cada iteración. Esa es esta parte:Esto
()
simplemente empuja una captura vacía al grupo1
(inicializandoi
a0
). Esto es bastante equivalente a la^.|
solución simple anterior, pero usar|
en este caso sería un poco más complicado.Luego tenemos el bucle principal
(\1(?<1>.\1))
.\1
coincide con el anteriori
,(?<1>.\1)
luego actualiza el grupo1
coni+1
. En términos de lo nuevoi
, acabamos de hacer coincidir los2i-1
personajes. Exactamente lo que necesitamos.Cuando terminamos, hemos combinado algunos cuadrados
i*i
y el grupo1
todavía tienei
personajes.La segunda parte está más cerca de la simple coincidencia cuadrada que mostré arriba. Ignoremos la referencia a
1
por ahora:Esto es básicamente lo mismo que
(^.|..\4)*
, excepto que no podemos usarlo^
porque no estamos al comienzo de la cadena. En su lugar, utilizamos un condicional, para que coincida con el adicional.\1
solo cuando ya hemos usado group4
. Pero en efecto esto es exactamente lo mismo. Esto nos daj*j
.Lo único que falta es el
j*i
término. Combinamos esto con elj*j
hecho de que elj*j
cómputo todavía tomaj
iteraciones. Entonces, para cada iteración también avanzamos el cursori
con\1
. Solo tenemos que asegurarnos de no escribir eso en el grupo4
, porque eso podría interferir con números impares consecutivos. Así es como llegamos a:fuente
CJam (
1615 bytes)Demostración en línea
Este es un bloque (una "función anónima") que toma datos en la pila y se va
0
o1
en la pila. Utiliza la caracterización de que un número es Loeschian si no tiene un factor primo igual a 2 mod 3 con multiplicidad impar.Gracias a Dennis por un ahorro de un byte.
fuente
Python 2, 56 bytes
fuente
Haskell, 42 bytes
Ejemplo de uso:
f 501
->False
.Trata todas las combinaciones de
i
partir0
parak
yj
desde0
ai
.or
devuelveTrue
si la igualdad sek==i*i+j*j+i*j
cumple para al menos una de las combinaciones.@flawr encontró una versión ligeramente diferente con el mismo número de bytes:
fuente
or
, cool =) Quizás tengas una idea de cómo jugar a este fraseo alternativof k|v<-[0..k]=or[(i+j)^2==k+i*j|i<-v,j<-v]
:?Java 8, 81 bytes
Implementación simple e ingenua. casualmente el mismo código que C # pero usa en
->
lugar de=>
.fuente
;
. ¡MALDITA SEA!i
oj
.Python, 67 bytes
https://repl.it/Cj6x
fuente
Jalea ,
15141312 bytes1 byte gracias a millas.
Pruébalo en línea!
Verifique las cajas de prueba más pequeñas .
Un consejo a la hora de realizar pruebas para grandes números (mayores de 50): no lo hagas.
La verdad es un número positivo. Falsey es cero.
Explicación
fuente
Medusa ,
5643412928 bytes2 bytes gracias a Zgarb
Pruébalo en línea!
Un tenedor de mi respuesta de gelatina .
fuente
MATL ,
1413 bytesPruébalo en línea! O verificar todos los casos de prueba .
Salidas
1
o0
.Explicación
fuente
Python, 49 bytes
Utiliza la forma cuadrática equivalente dada en OEIS de
n == 3*i*i+j*j
. Verifique sin-3*i*i
es un cuadrado perfecto para cualquierai
tomando su raíz cuadrada y verificando si es un número entero, es decir, es igual a 0 módulo 1. Tenga en cuenta que Python calcula las raíces cuadradas de cuadrados perfectos exactamente, sin error de coma flotante. Esto lo+0j
convierte en un número complejo para evitar un error en la raíz cuadrada de un negativo.fuente
C (gcc),
7169 bytesfuente
i,j,r;f(n){for(r=i=n+1;i--;)for(j=n;j--;)r*=n!=i*i+j*j+i*j;return!r;}
.i
oj
.i
yj
.k
, pero noi
yj
. Mire más de cerca los ejemplos.k
se puede expresar comoi*i + j*j + i*j
para enterosi, j
no negativos ". Usted toma una mirada más cercana.C #,
848281 bytesUna solución ingenua. 1 = verdadero, 0 = falso
fuente
VBA,
6867 bytesBúsqueda ingenua, comenzando a disminuir un poco para n = 1000. Excel reconoce el retorno cero como falso, todos los demás retornos como verdaderos.
Tenga en cuenta que no es necesaria la investigación de i y j negativos , ya que dado i> j> = 0 :
(el mismo resultado que para i y j )
(si uno es negativo, no importa cuál), y luego
Y dado que tanto (ij) como j no son negativos, cualquier generación de números de Loeschian que involucre un número negativo se puede lograr usando números no negativos.
Guardado un byte,
Next:Next
->Next b,a
gracias a Taylor Scott.fuente
i
oj
.Next:Next
aNext b,a
:End Function
al final de su soluciónJavascript (usando una biblioteca externa - Enumerable) (63 bytes)
Enlace a la biblioteca: https://github.com/mvegh1/ Explicación de código numerable: Cree un rango de enteros de 0 a k (llame a esto el rango "i") y pruebe si alguna "i" satisface un determinado predicado. Ese predicado crea un rango de 0 a k (llame a esto el rango "j") y prueba si alguna "j" satisface un determinado predicado. Ese predicado es la fórmula loeschiana
fuente
Perl 6 ,
52 5150 bytesExplicación:
Prueba:
fuente
i
oj
.(0..$_ X 0..$_)
produce una lista vacía si$_
es menor que0
, por lo que no hay necesidad de verificar si es negativoi
yj
porque nunca serán negativos. Como solo se supone que produceTrue
un número Loeschian positivo, no tengo que hacer nada especial para el caso negativo.9 = (3*3)+(-3*-3)+(3*-3)
es un Loeschian positivo coni=3, j=-3
; PERO sobrepasé que cada número de Loeschian tiene no negativoi
yj
. Por lo tanto, no es necesario buscar números negativos. Entonces, de hecho, podríamos eliminar esos comentarios. Perdón por molestar; mi culpa.{grep ->(\i,\j){$_==i*i+j*j+i*j},(-$_..$_ X -$_..$_)}(9)
resultados((-3,0),(-3,3),(0,-3),(0,3),(3,-3),(3,0))
. Honestamente, probablemente lo acabo de adaptar de otras respuestas.PowerShell v2 +,
635655 bytesToma entrada
$k
, realiza bucles hacia arriba dos veces (bucle externo$i = 0 to $k
, bucle interno$j = 0 to $i
), cada iteración genera el resultado dei*i + j*j + i*j
(acortado ai*(i+j) + j*j
). Esos resultados se encapsulan en parens y se pasan como una matriz a-eq$k
. Esto actúa como un filtro para seleccionar solo elementos que son iguales a la entrada. Emite un valor distinto de cero (el número de regreso) para la verdad, o nada (vacío) para falsey. Procesos1000
en aproximadamente 15 segundos en mi máquina.Casos de prueba
fuente
Perl, 54 + 1 (
-n
bandera) = 55 bytesNecesidades
-n
y-M5.010
banderas para ejecutar:Emite algunas cosas si el número es un número de Loeschian, y nada de lo contrario.
Esta implementación es bastante aburrida, así que aquí hay otra, para 87 bytes, basada en expresiones regulares, solo para los ojos:
Tenga cuidado con este, ya que el retroceso usará mucha memoria, ¡así que no intente probar números demasiado grandes! (especialmente números que no son loeschianos)
fuente
Dyalog APL , 19 bytes
Comprueba si k ∊ ( i + j ) ² - ij , para cualquier 0 ≤ i , j ≤ k .
⊢
es k∊
un miembro de∘.
todas las combinaciones de×
i veces j-⍨
restado del2*⍨
cuadrado de+
i más j⍨
para todo i y j en0,
cero antepuesto a⍳
los enteros 1 a k1000 toma 3.3 segundos en mi M540 y aún menos en TryAPL .
fuente
Matlab,
5352 bytesBúsqueda simple sobre todas las posibilidades.
Emite una matriz vacía como falso y un vector no vacío como valor verdadero.
Considerando la matriz de todos ceros como falsa y la matriz de no todos ceros como verdadera, podemos deshacernos de la
find
función que resulta en una solución de4746 bytes :Un byte guardado gracias a @flawr
fuente
(a+b).^2-a.*b==n
Es más corto.C, 66 bytes
Llame
f()
con el número para probar. La función devuelve el número de soluciones que encontró.Pruébalo con ideone .
fuente
Mathematica, 44 bytes
Función sin nombre que toma un entero como entrada y devuelve
True
oFalse
. El comando0~Range~#~Tuples~2
crea todos los pares de enteros ordenados entre0
y la entrada#
. La función(+##)^2-##&
calcula el cuadrado de la suma de sus argumentos menos el producto de sus argumentos; cuando se le solicitan dos argumentosi
yj
, esto es exactamentei^2+j^2+ij
como se desea. Entonces esa función se llama en todas las tuplas, y luegoMemberQ[...,#]
verifica si la entrada es uno de los valores resultantes.fuente
ASP, 39 + 4 = 43 bytes
Salida: el problema es satisfactoria si k es Loeschian.
La programación del conjunto de respuestas es un lenguaje lógico, similar al prólogo. Utilizo aquí la implementación de Potassco , clingo .
La entrada se toma de los parámetros (
-ck=
tiene 4 bytes de longitud). Ejemplo de llamada:Muestra de salida:
Probado con 1000:
Muestra de salida:
Puedes probarlo en tu navegador ; desafortunadamente, este método no maneja los indicadores de llamada, por lo que debe agregar la línea
#const k=999
para que funcione.Código sin golf y explicado:
fuente
PHP, 70 bytes
toma datos del argumento de la línea de comando; sale con
1
para número Loeschian, con0
más.Corre con
-nr
.Descompostura
fuente