Finde die n-te perfekte Kraft!

16

Eine perfekte Kraft ist eine Reihe von Formen a**b, in denen a>0und b>1.

Zum Beispiel 125ist eine perfekte Kraft, weil es ausgedrückt werden kann als 5**3.

Tor

Ihre Aufgabe ist es, ein Programm / eine Funktion zu schreiben n, die bei einer positiven ganzen Zahl die -te perfekte Potenz findet n.

Technische Daten

  • Die erste vollkommene Kraft ist 1(welche ist 1**2).
  • Eingabe / Ausgabe in jedem vernünftigen Format.
  • Einbauten sind erlaubt .

Weitere Informationen

Wertung

Das ist . Kürzeste Lösung in Bytes gewinnt.

Testfälle

input  output
1      1
2      4
3      8
4      9
5      16
6      25
7      27
8      32
9      36
10     49
Undichte Nonne
quelle
1
Bis zu welcher Nummer soll das funktionieren? Unendlichkeit?
ghosts_in_the_code
Eine angemessene Menge.
Undichte Nonne
Was ist mit einer Sprache, die nur einen Datentyp von einem Bit verwendet?
ghosts_in_the_code
1
@ Agawa001 Ja, es ist eine Standard-Lücke, die nicht mehr lustig ist.
Fehler

Antworten:

8

Jelly , 11 Bytes

µÆE;¬g/’µ#Ṫ

Probieren Sie es online! .

Hintergrund

Jede positive ganze Zahl k kann eindeutig als das Produkt der Potenzen der ersten m Primzahlen faktorisiert werden , dh k = p 1 α 1 ≤ p m α m , wobei α m > 0 ist .

Wir haben a b ( b> 1 ) für eine positive ganze Zahl a genau dann, wenn b ein Teiler aller Exponenten α j ist .

Somit ist eine ganze Zahl k> 1 genau dann eine perfekte Potenz, wenn gcd (α 1 , ⋯, α m ) ≠ 1 ist .

Wie es funktioniert

µÆ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
quelle
Ich habe STDIN überhaupt nicht gesehen. Ich habe keine Ahnung, wie ich es überhaupt verwenden soll.
Undichte Nonne
Gute Verwendung der Definition der perfekten Potenz, die mit der Primfaktorisierung zu tun hat. Könnten Sie diesen Algorithmus in die Beschreibung aufnehmen?
Undichte Nonne
@KennyLau Fertig.
Dennis
Ich verstehe nicht, wie 21 ^ 2 die erste oder dritte Primzahl in ihre Faktorisierung einbezieht. Könnten Sie mir bitte helfen zu verstehen, was Sie unter "Jede positive ganze Zahl k kann eindeutig als das Produkt der Potenzen der ersten m Primzahlen faktorisiert werden ... wo [der Exponent] a_n > 0?" In der Faktorisierung für 21 ^ 2 scheinen mir die Exponenten für p = 2 und p = 5 Null zu sein.
Dienstag,
@ גלעדברקן Sorry, das hätte a_m> 0 sein sollen . Die vorherigen m-1- Exponenten können Nullen enthalten.
Dennis
6

Mathematica, 34 Bytes

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

Erzeugt ein n × n- Array A ij = i 1+ j , glättet es und gibt das n- te Element zurück.

LegionMammal978
quelle
3

CJam, 16 Bytes

ri_),_2f+ff#:|$=

Teste es hier.

Erläuterung

Dies basiert auf einer ähnlichen Idee wie die Mathematica-Antwort von 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
quelle
3

Oktave, 57 31 30 Bytes

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

Ich habe gerade wieder gemerkt, dass Octave nicht benötigt ndgrid(während Matlab tut) =)

fehlerhaft
quelle
3

Sage (Version 6.4, wahrscheinlich auch andere): 64 63

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

Erzeugt eine Lambda-Funktion, die die nperfekte Leistung zurückgibt . Wir verlassen uns auf die Tatsache, dass es in den ersten n^2ganzen Zahlen gefunden wird. (Das 1+n^2ist notwendig n=1,2. Das 0+kBit notwendig ist , zu konvertieren int(k)zu Integer(k).)

Byte off für xrange-> range, danke Dennis.

Nur eine lustige Tatsache: 0ist nach Sages Maßstäben eine perfekte Kraft, zum Glück, denn dann 1ist es das 1. Element der Liste, nicht das 0. :)

yo '
quelle
Das ist also Python mit Ausnahme des Teils mit der Hauptmacht?
CalculatorFeline
@CatsAreFluffy Undis_perfect_power()
yo '
2

Pyth - 12 11 Bytes

Offensichtlicher Ansatz, geht einfach durch und prüft alle Zahlen.

e.ffsI@ZTr2

Test Suite .

Maltysen
quelle
1

MATL, 9 Bytes

:tQ!^uSG)

Probieren Sie es online aus

Dies ist eine Portierung von Flawrs Octave-Lösung für MATL. Stellen Sie die Matrix der Potenzen auf n^(n+1)und holen Sie sich die n-te.

David
quelle
1

Julia, 64 32 Bytes

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

Dies ist eine anonyme Funktion, die eine Ganzzahl akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu.

Die Idee hier ist die gleiche wie in der Mathematica- Antwort von LegionMammal : Wir nehmen das äußere Produkt der ganzen Zahlen 1 bis n mit 2 bis n + 1, reduzieren die resultierende Matrix spaltenweise, nehmen eindeutige Elemente, sortieren und erhalten das n- te Element .

Probieren Sie es online! (beinhaltet alle Testfälle)

Alex A.
quelle
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

Weniger golfen

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];
}

Prüfung

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
quelle
1

Eigentlich 18 Bytes (nicht konkurrierend)

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

Probieren Sie es online!(funktioniert möglicherweise nicht, da ein Update erforderlich ist)

Diese Lösung ist nicht konkurrierend, da ich einen Fehler mit behoben habe E nachdem diese Herausforderung veröffentlicht wurde.

Erläuterung:

;;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
quelle
1

> <> 108 Bytes

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

Für dieses Programm muss die Eingabenummer auf dem Stapel vorhanden sein, bevor es ausgeführt wird.

Es hat ziemlich viel gedauert, um die Anzahl der verschwendeten Bytes auf 7 zu reduzieren!

Nach einer Überprüfung, ob es sich um eine Eingabe handelt 1, überprüft das Programm jede Zahl nvon 4 nacheinander, um festzustellen, ob es sich um eine perfekte Potenz handelt. Es tut dies, indem es mit beginnt a=b=2. Wenn a^b == nwir eine perfekte Kraft gefunden haben, verringern Sie die Anzahl der noch zu findenden perfekten Kräfte - wenn wir bereits die richtige Zahl gefunden haben, geben Sie sie aus.

Wenn a^b < n, bwird inkrementiert. Wenn a^b > n, awird inkrementiert. Wenn dann a == nhaben wir festgestellt , dass nnicht eine perfekte Leistung ist, so Schritt n, Zurücksetzen aund b.

Sok
quelle
0

J, 29 Bytes

Basierend auf der @ LegionMammal978- Methode .

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

Verwendung

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

Erläuterung

<:{[:/:~@~.[:,/[:(^/>:)~>:@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
Meilen
quelle
0

JavaScript (ES7), 104 Byte

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]

Berechnet alle Potenzen, die nicht größer als n² sind, sortiert die resultierende Liste und nimmt das n-te Element.

Neil
quelle
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;}}
Hoffentlich hilfreich
quelle
Wäre es kürzer, eine Rekursion zu verwenden?
Undichte Nonne
Gut, Idee, braucht aber viel Planung.
Hoffentlich hilfreich