¡Encuentra la enésima potencia perfecta!

16

Un poder perfecto es un número de la forma a**b, dónde a>0y b>1.

Por ejemplo, 125es un poder perfecto porque se puede expresar como 5**3.

Objetivo

Su tarea es escribir un programa / función que encuentre la nenésima potencia perfecta, dado un entero positivo n.

Especificaciones

  • El primer poder perfecto es 1(que es 1**2).
  • Entrada / salida en cualquier formato razonable.
  • Se permiten empotrados .

Más información

Puntuación

Este es el . La solución más corta en bytes gana.

Casos de prueba

input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
Monja permeable
fuente
1
¿Hasta qué número debería funcionar esto? ¿Infinito?
ghosts_in_the_code
Una cantidad razonable.
Leaky Nun
¿Qué pasa con un lenguaje que usa solo un tipo de datos de un bit?
ghosts_in_the_code
1
@ Agawa001 Sí, es una escapatoria estándar que ya no es divertida.
falla

Respuestas:

8

Jalea , 11 bytes

µÆE;¬g/’µ#Ṫ

Pruébalo en línea! .

Antecedentes

Cada entero positivo k se puede factorizar únicamente como el producto de las potencias de los primeros m primos, es decir, k = p 1 α 1 ⋯ p m α m , donde α m > 0 .

Tenemos que a b ( b> 1 ) para algún entero positivo a si y solo si b es un divisor de todos los exponentes α j .

Por lo tanto, un entero k> 1 es una potencia perfecta si y solo si mcd (α 1 , ⋯, α m ) ≠ 1 .

Cómo funciona

µÆE;¬g/’µ#Ṫ  Main link. No arguments.

µ            Make the chain monadic, setting the left argument to 0.
        µ#   Find the first n integers k, greater or equal to 0, for which the
             preceding chain returns a truthy value.
             In the absence of CLAs, n is read implicitly from STDIN.
 ÆE          Compute the exponents of the prime factorization of k.
   ;¬        Append the logical NOT of k, i.e., 0 if k > 0 and 1 otherwise.
             This maps 1 -> [0] and [0] -> [1].
     g/      Reduce the list of exponents by GCD.
             In particular, we achieved that 1 -> 0 and 0 -> 1.
       ’     Decrement; subtract 1 from the GCD.
             This maps 1 to 0 (falsy) and all other integers to a truthy value.
          Ṫ  Tail; extract the last k.
Dennis
fuente
No he visto STDIN en absoluto. No tengo idea de cómo usarlo.
Leaky Nun
Buen uso de la definición de potencia perfecta que tiene que ver con la factorización prima. ¿Podría incluir este algoritmo en la descripción?
Leaky Nun
@KennyLau Hecho.
Dennis
No entiendo cómo 21 ^ 2 incluye el primer o tercer primo en su factorización. ¿Podría por favor ayudarme a entender lo que quiere decir con "cada entero positivo k puede factorizarse de manera única como el producto de las potencias de los primeros m primos ... donde [el exponente] a_n > 0?" Me parece que en la factorización para 21 ^ 2 los exponentes para p = 2 y p = 5 son cero.
עדלעד ברקן
@ גלעדברקן Lo siento, debería haber sido a_m> 0 . Los exponentes m-1 anteriores pueden incluir ceros.
Dennis
6

Mathematica, 34 bytes

(Union@@Array[#^#2#&,{#,#}])[[#]]&

Genera un n × n matriz A ij = i 1+ j , la aplana, y devuelve el n -ésimo elemento.

LegionMammal978
fuente
3

CJam, 16 bytes

ri_),_2f+ff#:|$=

Pruébalo aquí.

Explicación

Utiliza una idea similar a la respuesta de Mationica de LegionMammal.

ri    e# Read input and convert to integer N.
_),   e# Duplicate, increment and turn into range [0 1 ... N].
_2f+  e# Duplicate and add two to each element to get [2 3 ... N+2].
ff#   e# Compute the outer product between both lists over exponentiation.
      e# This gives a bunch of perfect powers a^b for a ≥ 0, b > 1.
:|    e# Fold set union over the list, getting all unique powers generated this way.
$     e# Sort them.
=     e# Retrieve the N+1'th power (because input is 1-based, but CJam's array access
      e# is 0-based, which is why we included 0 in the list of perfect powers.
Martin Ender
fuente
3

Octava, 57 31 30 bytes

@(n)unique((1:n)'.^(2:n+1))(n)

Acabo de notar nuevamente que Octave no necesita ndgrid(mientras que Matlab sí) =)

falla
fuente
3

Sage (versión 6.4, probablemente también otras): 64 63

lambda n:[k for k in range(1+n^2)if(0+k).is_perfect_power()][n]

Crea una función lambda que devuelve nel poder perfecto. Confiamos en el hecho de que se encuentra dentro de los primeros n^2enteros. (El 1+n^2es necesario para n=1,2. El 0+kbit es necesario convertir int(k)a Integer(k).)

Byte apagado para xrange-> range, gracias Dennis.

Solo un hecho divertido: 0es un poder perfecto para los estándares de Sage, afortunadamente, porque entonces 1es el primer elemento de la lista, no el 0º :)

yo'
fuente
Entonces, ¿esto es Python excepto por la parte de potencia principal?
CalculatorFeline
@CatsAreFluffy Andis_perfect_power()
yo '
2

Pyth - 12 11 bytes

Enfoque obvio, solo pasa y verifica todos los números.

e.ffsI@ZTr2

Test Suite .

Maltysen
fuente
1

MATL, 9 bytes

:tQ!^uSG)

Pruébalo en línea

Este es un puerto de la solución Octave de Flawr para MATL, crea la matriz de potencias n^(n+1)y obtén la nenésima.

David
fuente
1

Julia 64 32 bytes

n->sort(∪([1:n]'.^[2:n+1]))[n]

Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.

La idea aquí es la misma que en la respuesta Mathematica de LegionMammal : Tomamos el producto externo de los enteros 1 a n con 2 a n + 1, colapsamos la matriz resultante en forma de columna, tomamos elementos únicos, ordenamos y obtenemos el n º elemento .

Pruébalo en línea! (incluye todos los casos de prueba)

Alex A.
fuente
1

JavaScript (ES6), 87

n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

Menos golf

f=n=>{
  for(b=2, l=[0,1]; b < n*n; ++b)
    for(v = b; v < n*n;)
      l[v*=b] = v;
  i = 0;
  l.some(x => n == i++ ? v=x : 0);
  return v;
  // shorter alternative, but too much memory used even for small inputs
  // return l.filter(x=>x) [n-1];
}

Prueba

f=n=>(b=>{for(l=[i=0,1];b<n*n;++b)for(v=b;v<n*n;)l[v*=b]=v;l.some(x=>n==i++?v=x:0)})(2)|v

function test(){
  var v=+I.value
  O.textContent=f(v)
}
  
test()
<input type=number id=I value=10><button onclick='test()'>-></button>
<span id=O></span>

edc65
fuente
1

En realidad, 18 bytes (no competitivos)

;;u@ⁿr;`;√≈²=`M@░E

Pruébalo en línea! (puede no funcionar debido a la necesidad de una actualización)

Esta solución no es competitiva porque solucioné un error Edespués de publicar este desafío.

Explicación:

;;u@ⁿr;`;√≈²=`M@░E
;;u@ⁿr              push range(n**(n+1))
      ;`;√≈²=`M@░   filter: take if
        ;√≈²=         int(sqrt(x))**2 == x
                 E  get nth element
Mego
fuente
1

> <>, 108 bytes

:1)?v  >n;
$:@@\&31+2>2$:@@:@
:1=?\@$:@*@@1-
:~$~<.1b+1v!?(}:{:~~v?(}:{:v?=}:{
1-:&1=?v~~>~61.     >~1+b1.>&

Este programa requiere que el número de entrada esté presente en la pila antes de ejecutarse.

¡Se necesitó mucho para reducir el número de bytes desperdiciados a 7!

Después de una verificación para ver si la entrada es 1, el programa verifica cada número n, desde 4 por turno para ver si es una potencia perfecta. Hace esto comenzando con a=b=2. Si a^b == n, hemos encontrado un poder perfecto, entonces disminuya el número de poderes perfectos que quedan por encontrar; si ya hemos encontrado el número correcto, salida.

Si a^b < n, bse incrementa. Si a^b > n, ase incrementa. Entonces, si a == n, hemos descubierto que nno es una potencia perfecta, así que incremente n, reinicie ay b.

Sok
fuente
0

J, 29 bytes

Basado en el método de @ LegionMammal978 .

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.

Uso

   f =: <:{[:/:~@~.[:,/[:(^/>:)~>:@i.
   f " 0 (1 2 3 4 5 6 7 8 9 10)
1 4 8 9 16 25 27 32 36 49

Explicación

<:{[:/:~@~.[:,/[:(^/>:)~>:@i.
                           i.  Create range from 0 to n-1
                        >:     Increments each in that range, now is 1 to n
               [:              Cap, Ignores input n
                    >:         New range, increment from previous range to be 2 to n+1 now
                  ^/           Forms table using exponentation between 1..n and 2..n+1
             ,/                Flattens table to a list
         ~.                    Takes only distinct items
     /:~                       Sorts the list
<:                             Decrements the input n (since list is zero-based index)
  {                            Selects value from resulting list at index n-1
millas
fuente
0

JavaScript (ES7), 104 bytes

n=>(a=[...Array(n)]).map(_=>a.every(_=>(p=i**++j)>n*n?0:r[p]=p,i+=j=1),r=[i=1])&&r.sort((a,b)=>a-b)[n-1]

Funciona calculando todas las potencias no mayores que n², ordenando la lista resultante y tomando el enésimo elemento.

Neil
fuente
0

Java, 126

r->{int n,i,k;if(r==1)return r;for(n=i=2,r--;;){for(k=i*i;k<=n;k*=i)if(k==n){i=--r>0?++n:n;if(r<1)return n;}if(--i<2)i=++n;}}
Con suerte
fuente
¿Sería más corto usar recursividad?
Leaky Nun
Buena idea, sin embargo, necesita mucha planificación.
HopefulHelpful