Definiciones
- Un cuadrado perfecto es un entero que se puede expresar como el cuadrado de otro entero. Por ejemplo,
36
es un cuadrado perfecto porque6^2 = 36
. - Un número libre de cuadrados es un número entero que no es divisible por ningún cuadrado perfecto, excepto por
1
. Por ejemplo,10
es un número libre de cuadrados. Sin embargo,12
no es un número libre de cuadrados, porque12
es divisible por4
y4
es un cuadrado perfecto.
Tarea
Dado un entero positivo n
, genera el número libre de cuadrados más grande que divide n
.
Casos de prueba
n output
1 1
2 2
3 3
4 2
5 5
6 6
7 7
8 2
9 3
10 10
11 11
12 6
13 13
14 14
15 15
16 2
17 17
18 6
19 19
20 10
21 21
22 22
23 23
24 6
25 5
26 26
27 3
28 14
29 29
30 30
31 31
32 2
33 33
34 34
35 35
36 6
37 37
38 38
39 39
40 10
41 41
42 42
43 43
44 22
45 15
46 46
47 47
48 6
49 7
50 10
Tanteo
Este es el código de golf . La respuesta más corta en bytes gana.
Se aplican lagunas estándar .
Referencia
code-golf
math
arithmetic
number-theory
Monja permeable
fuente
fuente
Respuestas:
05AB1E , 2 bytes
Pruébalo en línea!
Cómo funciona
fuente
Brachylog , 3 bytes
Pruébalo en línea!
Una respuesta muy original ...
Explicación
fuente
JavaScript (ES6),
55545046 bytesCitando OEIS :
a (n) es el divisor más pequeño u de n tal que n divide u ^ n
Implementación actualizada:
a (n) es el
divisormás pequeñou de nentero positivo u tal que n divide u ^ nfuente
MATL ,
64 bytes2 bytes guardados con ayuda de @LeakyNun
Pruébalo en línea!
Explicación
Considere la entrada
48
.fuente
Jalea , 4 bytes
Pruébalo en línea!
fuente
CJam , 8 bytes
¿Por qué cada operación en este programa tiene que ser de 2 bytes?
Pruébalo en línea!
fuente
Retina ,
363028 bytesEntrada y salida en unario .
Pruébalo en línea! (Incluye un encabezado y pie de página para la conversión decimal <-> unaria y para ejecutar múltiples casos de prueba a la vez).
Explicación
La idea es hacer coincidir la entrada como un cuadrado multiplicado por algún factor. La expresión regular básica para unir un cuadrado utiliza una referencia directa para unir sumas de enteros impares consecutivos:
Como no queremos hacer coincidir cuadrados perfectos, sino números que son divisibles por un cuadrado, lo reemplazamos
1
con una referencia misma:Así que ahora el grupo externo
1
se usará n veces donde n 2 es el cuadrado más grande que divide la entrada y el grupo2
almacena el factor restante. Lo que queremos es dividir el número entero entre n para eliminar el cuadrado. El resultado puede expresarse como el número de iteraciones de grupo por1
grupo2
, pero esto es un poco difícil de hacer. La retina$*
probablemente se mejorará pronto para tomar un token que no sea de personaje como argumento de la mano derecha, en cuyo caso podríamos simplemente reemplazarlo por$#1$*$2
, pero eso aún no funciona.En cambio, descomponemos los números impares de manera diferente. Volvamos al ejemplo más simple de combinar cuadrados perfectos con
(^1|11\1)+$
. En lugar de tener un contador\1
que se inicializa en 1 y se incrementa en 2 en cada iteración, tendremos dos contadores. Uno se inicializa a 0 y el otro a 1 , y ambos se incrementan en 1 en cada iteración. Básicamente, hemos descompuesto los números impares 2n + 1 en (n) + (n + 1) . El beneficio es que terminaremos con n en uno de los grupos. En su forma más simple, se ve así:Donde
\2
es n y\3
es n + 1 . Sin embargo, podemos hacer esto un poco más eficiente al notar que el n + 1 de una iteración es igual al n de la siguiente iteración, por lo que podemos ahorrar1
aquí:Ahora solo tenemos que volver a usar un factor inicial en lugar de
1
hacer coincidir las entradas divididas por un cuadrado perfecto:Ahora todo lo que tenemos que hacer es reemplazar todo esto
$3
al final, que almacena el factor inicial multiplicado por el número de pasos, lo que elimina un factor del cuadrado de la entrada.Esto se hace repetidamente con el
+
principio del programa, para tener en cuenta las entradas que contienen potencias más altas que los cuadrados.fuente
Octava, 27 bytes
Enfoque similar a las otras respuestas. La diferencia es: las funciones tienen nombres mucho más largos. Creo que el código se explica realmente: toma el efecto
prod
de losunique
números primosfactor
de un número.fuente
Wolfram Language,
2928 bytes-1 Gracias a @Martin Ender ♦
Explicación:
fuente
Times@@(#&@@@FactorInteger@#)&
Most
lo deja como una lista NecesitasFirst
obtener el valor.Python , 37 bytes
Pruébalo en línea!
El mayor divisor libre de cuadrados
n
es el número más pequeñor
con todosn
los factores primos de. Podemos verificar esto comor**n%n==0
, ya quer**n
hacern
copias de cada factor primo der
, y es divisible porn
solo si cada uno den
los factores primos está representado.El
1>>r**n%n
es equivalente aint(r**n%n==0)
. SiTrue
se puede usar la salida 1, es 2 bytes más corto para hacerlo.fuente
Matemáticas , 40 bytes.
Pruébalo en línea!
fuente
Times@@#&@@Transpose@FactorInteger@#&
ahorra 3 bytes (#&@@
es un truco estándar[[1]]
y, en casos como este, a menudo puede guardar algunos bytes adicionales entre paréntesis).Thread
lugar deTranspose
. En Mathematica también hay un operador de 3 bytesTranspose
, pero no sé si Mathics lo admite.#&@@(1##&@@FactorInteger@#)&
evita la necesidad porTranspose
completo. (1##&@@
solo estáTimes@@
disfrazado, lo que funciona muy bien en los pares ordenados cedidos porFactorInteger
; y'#&@@
estáFirst@
disfrazado.)Alice , 4 bytes
Pruébalo en línea!
La entrada y la salida se proporcionan como el punto de código de un carácter (funciona para todos los puntos de código Unicode válidos).
Explicación
Bueno, Alice tiene una
D
definición incorporada que es "Deduplicar factores primos". Es decir, siempre que un valor sea divisible por alguna p 2 para una prima p , divida ese valor entre p . Esta es exactamente la función requerida en este desafío. El resto es solo entrada, salida, terminar el programa.La razón por la que esto se agregó a Alice en realidad no tiene nada que ver con esta secuencia de enteros. Estaba tratando de mantener un tema de asociar divisores con subcadenas y factores primos con caracteres. Y necesitaba una función que vaya con "deduplicar caracteres" (que es mucho más útil en general, porque te permite tratar las cadenas como conjuntos, especialmente cuando se usan junto con los diversos operadores de conjuntos múltiples).
fuente
Haskell , 31 bytes
Pruébalo en línea!
fuente
Pyke , 3 bytes
Pruébalo en línea!
fuente
Prólogo (SWI) ,
8439 bytesPruébalo en línea!
Adaptó la idea de la respuesta de Haskell de @xnor a Prolog.
fuente
PHP, 70 bytes
Pruébalo en línea!
fuente
Pyth,
86 bytes* -2 bytes gracias a @LeakyNun
Sería 3 si Pyth tuviera una función incorporada para productos de listas ...
¡Intentalo!
fuente
*F+1{P
en su lugar.C,
6550 bytesGracias a @ Ørjan Johansen por eliminar la necesidad de
r
. ¡Gracias a este y algunos otros trucos sucios pude exprimir 15 bytes!while
se ha ido y reemplazado con un||
índice de giro.<=
debería haber estado<
todo el tiempo.<=
se gira<
moviendo el incremento para obtenern%(++d*d)
(debe estar bien definido debido a la precedencia del operador).Código original:
fuente
r
y en su lugar usarwhile(n%(d*d)<1)n/=d;
.++d*d
Es absolutamente no bien definida por los estándares de C - es un caso clásico de un comportamiento no definido de forma explícita. Pero vamos por implementaciones aquí, de todos modos.d++<n
, que está bien definido, seguir funcionando? Creo que la versión anterior fue completamenten+1
inofensiva.d++<n
ser correcto, por alguna razón no lo vi cuando reescribí el código.Axioma, 89 bytes
prueba y resultados
esta es la función de no usar factor ()
pero solo tiene 125 bytes
fuente
R, 52 bytes
lee
n
de stdin. Requieregmp
que se instale la biblioteca (para que TIO no funcione). Utiliza el mismo enfoque que muchas de las respuestas anteriores, pero se bloquea en una entrada de1
, porquefactorize(1)
devuelve un vector de clase vacíobigz
, que se bloqueaunique
, por desgracia.fuente
En realidad , 2 bytes
Pruébalo en línea!
Explicación:
fuente
Pari / GP , 28 bytes
Pruébalo en línea!
fuente
Pyt , 3 bytes
Explicación:
fuente