Abandona todos los cuadrados, ustedes que me dividen

37

Definiciones

  • Un cuadrado perfecto es un entero que se puede expresar como el cuadrado de otro entero. Por ejemplo, 36es un cuadrado perfecto porque 6^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, 10es un número libre de cuadrados. Sin embargo, 12no es un número libre de cuadrados, porque 12es divisible por 4y 4es 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 . La respuesta más corta en bytes gana.

Se aplican lagunas estándar .

Referencia

Monja permeable
fuente
1
... y se llama radical , ¡así que en la década de 1980!
Jonathan Allan
Estrechamente relacionado , simplemente multiplique las dos salidas. Editar: No importa, solo coincide en números sin cubo.
xnor

Respuestas:

45

05AB1E , 2 bytes

fP

Pruébalo en línea!

Cómo funciona

f   Implicitly take input and compute the integer's unique prime factors.
 P  Take the product.
Dennis
fuente
26
> _> realmente ... ??
HyperNeutrino
@HyperNeutrino sip: si un número no está libre de cuadrados es porque algunos de sus factores primos tienen multiplicidad.
Jonathan Allan
@ JonathanAllan Solo estoy interesado en el incorporado para factores primos únicos. Ojalá Jelly tuviera uno de esos ...
HyperNeutrino
@HyperNeutrino Es 05AB1E, acostúmbrate. 05AB1E tiene algunas construcciones realmente redundantes que aparentemente ahorran bytes.
Erik the Outgolfer
66
Corrección, "guardar bytes", probablemente no hay nada al respecto.
Draco18s
14

Brachylog , 3 bytes

ḋd×

Pruébalo en línea!

Una respuesta muy original ...

Explicación

ḋ          Take the prime factors of the Input
 d         Remove duplicates
  ×        Multiply
Fatalizar
fuente
1
Nuevamente, Brachylog le gana a Jelly porque un átomo de dos bytes es solo un byte aquí. >
:-P
44
La gelatina que tiene muchas acumulaciones a menudo se considera una ventaja; pero más incorporados significa que necesitan nombres más largos en promedio. Así que hay compensaciones involucradas en el diseño del lenguaje de golf.
2
No estoy tratando de ser "ese tipo", y tal vez simplemente no entiendo el conteo de bytes, pero ¿no son estos 6 bytes? mothereff.in/byte-counter#ḋd ×
Capitán Man
55
@CaptainMan Brachylog utiliza una página de códigos personalizados de 256 caracteres que puede encontrar aquí .
Fatalize
14

JavaScript (ES6), 55 54 50 46 bytes

Citando 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 divisor más pequeño u de n entero positivo u tal que n divide u ^ n

let f =

n=>(g=(p,i=n)=>i--?g(p*p%n,i):p?g(++u):u)(u=1)

for(n = 1; n <= 50; n++) {
  console.log(n,f(n));
}

Arnauld
fuente
Buen enfoque del problema, especialmente. dada la falta de factorización incorporada
Riking
12

MATL , 6 4 bytes

2 bytes guardados con ayuda de @LeakyNun

Yfup

Pruébalo en línea!

Explicación

Considere la entrada 48.

Yf   % Implicit input. Push prime factors with repetitions.  STACK: [2 2 2 2 3]
u    % Unique.                                               STACK: [2 3]
p    % Product of array. Implicit display.                   STACK: 6
Luis Mendo
fuente
Fuera de golf
Leaky Nun
@LeakyNun Heh, estaba a punto de publicar eso :-) Gracias
Luis Mendo
11

Jalea , 4 bytes

ÆfQP

Pruébalo en línea!

ÆfQP  Main link, argument is z
Æf    Takes the prime factors of z
  Q   Returns the unique elements of z
   P  Takes the product
Hiperneutrino
fuente
9

CJam , 8 bytes

rimf_&:*

¿Por qué cada operación en este programa tiene que ser de 2 bytes?

Pruébalo en línea!

ri       e# Read int from input
  mf     e# Get the prime factors
    _&   e# Deduplicate
      :* e# Take the product of the list
Gato de negocios
fuente
No pude encontrar una manera de deduplicar. ¡Agradable!
Luis Mendo
@LuisMendo Acabo de descubrir eso recientemente. Siempre pensé que era una intersección de múltiples conjuntos, pero aparentemente es una intersección normal.
Business Cat
9

Retina , 36 30 28 bytes

+`((^|\3)(^(1+?)|\3\4))+$
$3

Entrada 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:

(^1|11\1)+$

Como no queremos hacer coincidir cuadrados perfectos, sino números que son divisibles por un cuadrado, lo reemplazamos 1con una referencia misma:

(^(1+?)|\1\2\2)+$

Así que ahora el grupo externo 1se usará n veces donde n 2 es el cuadrado más grande que divide la entrada y el grupo 2almacena 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 por 1grupo 2, 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 \1que 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í:

((^|1\2)(^1|1\3))+$

Donde \2es n y \3es 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 ahorrar 1aquí:

((^|\3)(^1|1\3))+$

Ahora solo tenemos que volver a usar un factor inicial en lugar de 1hacer coincidir las entradas divididas por un cuadrado perfecto:

((^|\3)(^(1+?)|\3\4))+$

Ahora todo lo que tenemos que hacer es reemplazar todo esto $3al 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.

Martin Ender
fuente
8

Octava, 27 bytes

@(x)prod(unique(factor(x)))

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 prodde los uniquenúmeros primos factorde un número.

Stewie Griffin
fuente
Me ninja'd por ~ 30 segundos :)
Kritixi Lithos
7

Wolfram Language, 29 28 bytes

-1 Gracias a @Martin Ender ♦

Most[1##&@@FactorInteger@#]&

Explicación:

           FactorInteger@#    (*Get prime factorization as {{a,b},{c,d}}*)
     1##&@@                   (*Multiply list elements together, to get the product of the factors and the product of their exponents*)
Most[                     ]&  (*Take the first element*)
Scott Milner
fuente
2
Sólo se dio cuenta de que esto es básicamente el comentario de @ GregMartin sobre la respuesta Mathics, sólo menos Golfy ...
de Scott Milner
No se sienta mal, que tenía la respuesta aún menos de golfyTimes@@(#&@@@FactorInteger@#)&
Ian Miller
Mostlo deja como una lista Necesitas Firstobtener el valor.
Ian Miller
@IanMiller Me doy cuenta de eso, pero son menos bytes para devolver una lista con solo un elemento. Supuse que eso estaba bien, ya que todavía es un resultado razonable.
Scott Milner
7

Python , 37 bytes

f=lambda n,r=1:1>>r**n%n or-~f(n,r+1)

Pruébalo en línea!

El mayor divisor libre de cuadrados nes el número más pequeño rcon todos nlos factores primos de. Podemos verificar esto como r**n%n==0, ya que r**nhacer ncopias de cada factor primo de r, y es divisible por nsolo si cada uno den los factores primos está representado.

El 1>>r**n%nes equivalente a int(r**n%n==0). Si Truese puede usar la salida 1, es 2 bytes más corto para hacerlo.

f=lambda n,r=1:r**n%n<1or-~f(n,r+1)
xnor
fuente
6

Matemáticas , 40 bytes.

Times@@(Transpose@FactorInteger@#)[[1]]&

Pruébalo en línea!

Pavel
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).
Martin Ender
También puede usar en Threadlugar de Transpose. En Mathematica también hay un operador de 3 bytes Transpose, pero no sé si Mathics lo admite.
Martin Ender
66
#&@@(1##&@@FactorInteger@#)&evita la necesidad por Transposecompleto. ( 1##&@@solo está Times@@disfrazado, lo que funciona muy bien en los pares ordenados cedidos por FactorInteger; y '#&@@está First@disfrazado.)
Greg Martin
@GregMartin es básicamente su propia solución, siéntase libre de publicarla.
Pavel
Parece que Scott Milner lo consiguió de todos modos :)
Greg Martin
5

Alice , 4 bytes

iDo@

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 Ddefinició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).

Martin Ender
fuente
La parte triste es que, incluso con un incorporado, esta no es la respuesta más corta.
Rɪᴋᴇʀ
@Riker Bueno, eso se debe a que Alice no es un lenguaje de golf, por lo que necesita una E / S explícita y (dado que es un lenguaje 2D) la finalización del programa.
Martin Ender
Sí, todavía algo triste.
Rɪᴋᴇʀ
@ ConorO'Brien Acabamos de tener esta discusión en otra parte, y eso solo es válido si el operador independiente es una expresión que evalúa la función (que no es el caso aquí, ya que las funciones / operadores no son valores de primera clase) . codegolf.meta.stackexchange.com/a/7206/8478
Martin Ender
@ ConorO'Brien lo siento, fue un exclusivo "nosotros".
Martin Ender
2

PHP, 70 bytes

for($r=1,$i=2;1<$n=&$argn;)$n%$i?++$i:$n/=$i+!($r%$i?$r*=$i:1);echo$r;

Pruébalo en línea!

Jörg Hülsermann
fuente
1

Pyth, 8 6 bytes

*F+1{P

* -2 bytes gracias a @LeakyNun

Sería 3 si Pyth tuviera una función incorporada para productos de listas ...

¡Intentalo!

*F+1{P
      Q     # Implicit input
     P      # Prime factors of the input
    {       # Deduplicate
  +1        # Prepend 1 to the list (for the case Q==1)
*F          # Fold * over the list
KarlKastor
fuente
Puedes usar *F+1{Pen su lugar.
Leaky Nun
1

C, 65 50 bytes

Gracias a @ Ørjan Johansen por eliminar la necesidad de r. ¡Gracias a este y algunos otros trucos sucios pude exprimir 15 bytes!

d;f(n){for(d=1;d++<n;)n%(d*d)||(n/=d--);return n;}

whilese ha ido y reemplazado con un ||índice de giro. <=debería haber estado <todo el tiempo.

<=se gira <moviendo el incremento para obtener n%(++d*d)(debe estar bien definido debido a la precedencia del operador).


Código original:

d;r;f(n){for(r=d=1;d++<=n;)while(n%d<1)r*=r%d?d:1,n/=d;return r;}
algmyr
fuente
Creo que puedes acortarlo eliminando ry en su lugar usar while(n%(d*d)<1)n/=d;.
Ørjan Johansen
@ ØrjanJohansen Eso parece correcto. Estaba pensando en la construcción en lugar de la reducción. Tengo algunas mejoras adicionales para agregar, se actualizarán pronto.
algmyr
++d*dEs 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.
Ørjan Johansen
En realidad, ¿no debería d++<n, que está bien definido, seguir funcionando? Creo que la versión anterior fue completamente n+1inofensiva.
Ørjan Johansen
Probablemente tengas razón sobre el comportamiento indefinido. Por alguna razón, pensé que la precedencia del operador resolvería eso. La mayoría de los ejemplos que he visto de UB utilizan los mismos operadores prioritarios, pero, por supuesto, aquí también hay una carrera de datos. También tiene razón acerca de d++<nser correcto, por alguna razón no lo vi cuando reescribí el código.
algmyr
0

Axioma, 89 bytes

f(x:PI):PI==(x=1=>1;g:=factor x;reduce(*,[nthFactor(g,i) for i in 1..numberOfFactors g]))

prueba y resultados

(38) -> [[i, f(i)] for i in 1..30 ]
   (38)
   [[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]]

esta es la función de no usar factor ()

g(x:PI):PI==(w:=sqrt(x);r:=i:=1;repeat(i:=i+1;i>w or x<2=>break;x rem i=0=>(r:=r*i;repeat(x rem i=0=>(x:=x quo i);break)));r)

pero solo tiene 125 bytes

RosLuP
fuente
0

R, 52 bytes

`if`((n=scan())<2,1,prod(unique(c(1,gmp::factorize(n))))

lee nde stdin. Requiere gmpque 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 de 1, porque factorize(1)devuelve un vector de clase vacío bigz, que se bloquea unique, por desgracia.

Giuseppe
fuente
Esto genera 12 cuando ingreso 12.
Flounderer
@Flounderer tienes razón, he actualizado el código.
Giuseppe
0

Pyt , 3 bytes

←ϼΠ

Explicación:

←                  Get input
 ϼ                 Get list of unique prime factors
  Π                Compute product of list
                   Implicit print
mudkip201
fuente