Erkennen, ob eine Zahl eine Potenz ist

20.12.2010, 14:25

PeterH

Erkennen, ob eine Zahl eine Potenz ist

Meine Frage:
Hallo alle miteinander,
Ich habe eine Frage bezüglich des Themas Potenzen. Diese lautet: Gibt es ein Verfahren, dass mir für eine beliebige natürliche Zahl n sagt, ob es sich dabei um eine bliebige natürliche Potenz einer bliebigen natürlichen Zahl handelt? Es gibt ja Verfahren, mit denen man einigermaßen sagen kann, ob eine Zahl eine Primzahl ist. Gibt es soetwas auch für Potenzen? Wenn ja, würde ich mich sehr über eine Antwort freuen.
Mit freundlichen Grüßen,
PeterH

Meine Ideen:

20.12.2010, 15:23

Eyvan

Auf diesen Beitrag antworten »

eine jede natürliche Zahl kann die Potenz einer natürlichen Zahl sein.
Es kommt sogar immer eine natürliche Zahl raus.

$\begin{eqnarray*} a^n = a*a*a... \end{eqnarray*}$ das ganze n-mal.

Vielleicht verstehts du nicht ganz was Potenzen sind? Dann würd ich mal den wiki-eintrag dazu lesen.

20.12.2010, 15:35

system-agent

Auf diesen Beitrag antworten »

Zitat:

Original von Eyvan
eine jede natürliche Zahl kann die Potenz einer natürlichen Zahl sein.

Und die Frage war ja genau wie man erkennen kann ob es eine solche Potenz ist Augenzwinkern

.

Du kannst jedenfalls sehr einfach testen, ob eine gegebene natürliche Zahl $\begin{eqnarray*} b \end{eqnarray*}$ eine Potenz einer anderen gegebenen natürlichen Zahl $\begin{eqnarray*} b \end{eqnarray*}$ ist: Falls dem so ist, dann muss erstmal $\begin{eqnarray*} a|b \end{eqnarray*}$ gelten und ab da kannst du die Potenz durch probieren finden bzw wiederholtes teilen durch $\begin{eqnarray*} a \end{eqnarray*}$ .

20.12.2010, 15:40

Eyvan

Auf diesen Beitrag antworten »

jupp,wenn die Frage so gemeint war, hast du Recht system-agent.

20.12.2010, 15:55

PeterH

Auf diesen Beitrag antworten »

Hallo Eyvan und system-agent,
Meine Frage bezieht sich aber eher darauf, wie ich auch ohne Kennen der Basis sondern nur anhand der Zahl n sehen kann, ob es eine Potenz ist. D.h. vielleicht so etwas wie einen Algorithmus, der mir sagt: "Ja, die Zahl 243 ist eine Potenz." (dabei ist auch egal welche Basis hoch was genommen wurde) oder "Nein, diese Zahl lässt sich nicht als Potenz darstellen."
Mfg PeterH

20.12.2010, 16:21

Eyvan

Auf diesen Beitrag antworten »

Formell dürftest du dann nicht sagen 243 ist eine Potenz sondern lässt sich als eine Potenz mit natürlicher Basis und natürlichen Exponenten darstellen oder auch nicht.

Ein allgemein Verbindliches Verfahren ist mir nicht bekannt, da hilft meines Erachtens nur ausprobieren...

20.12.2010, 16:27

René Gruber

Auf diesen Beitrag antworten »

@PeterH

Zunächst mal geht es dir wohl nur um Potenzen mit Exponenten >2, denn einige der Anspielungen oben beziehen sich auch auf die Möglichkeit Exponent =1, und das wäre ja trivial.

Dann schätze ich mal, dass es dir um sehr große Zahlen $\begin{eqnarray*} n \end{eqnarray*}$ geht, also solche, deren Primfaktorzerlegung nicht mehr sonderlich effizient zu bewerkstelligen ist.

Aber folgender Algorithmus fällt mir spontan ein:

Berechne die reellen Wurzeln $\begin{eqnarray*} x_k := \sqrt[k]{n} \end{eqnarray*}$ für $\begin{eqnarray*} k=2,3,\ldots \end{eqnarray*}$ .

Findest du ein $\begin{eqnarray*} k \end{eqnarray*}$ mit $\begin{eqnarray*} x_k\in\mathbb{N} \end{eqnarray*}$ , bist du fertig. Ansonsten brauchst du noch ein geeignetes Abbruchkriterium:

Die Zahlen $\begin{eqnarray*} x_2,x_3,\ldots \end{eqnarray*}$ sind streng monoton fallend, sie fallen demnach irgendwann unter eine selbstgewählte, nicht allzu groß gewählte Schranke $\begin{eqnarray*} L>1 \end{eqnarray*}$ . Hat man nun bis dahin keinen Erfolg mit den Wurzeln als natürliche Zahlen gehabt, prüft man anschließend noch die Teilbarkeit von $\begin{eqnarray*} n \end{eqnarray*}$ durch die Primzahlen $\begin{eqnarray*} <L \end{eqnarray*}$ ... wie's weitergeht, kannst du dir jetzt sicher zusammenreimen.

EDIT: Es reicht übrigens, wenn man sich in obigem Test auf Primzahlen $\begin{eqnarray*} k \end{eqnarray*}$ als Indizes beschränkt, so kommt man ein wenig schneller voran.

Neue Frage »

Antworten »

Erkennen, ob eine Zahl eine Potenz ist

Verwandte Themen