| |
| Autor |
 Python Potenzprobe |
|
Bekell
Aktiv 
Dabei seit: 05.09.2008
Mitteilungen: 3227
 |  Themenstart: 2023-06-10
|
Hallo,
wie kann ich testen, ob eine Zahl x ein ganzzahlige Potenz einer ganzen Zahl ist
\sourceon Python
\numberson
for x in range(3,100,2):
if isprime(x):
primes.append(x)
else:
for y in range(2,5,1):
if isinstance (pow(x,1/y),int):
pot.append(x)
print(nr,x,primes,pot)
\sourceoff
Das funktioniert irgendwie nicht ....
|
 Profil
|
Ixx
Aktiv 
Dabei seit: 05.04.2020
Mitteilungen: 364
| Beitrag No.1, eingetragen 2023-06-10
|
Moin,
bei einem so eng umrissenen Suchbereich würde ich mir einfach alle echten Potenzen in diesem Bereich vorher erzeugen und in einer sortierten Liste speichern. Dann kann man jeweils in dieser Liste suchen, ob die aktuell betrachtete Zahl darunter ist, oder nicht.
|
Profil
|
Bekell
Aktiv
Dabei seit: 05.09.2008
Mitteilungen: 3227
| Beitrag No.2, vom Themenstarter, eingetragen 2023-06-10
|
\quoteon(2023-06-10 18:19 - Ixx in Beitrag No. 1)
Moin,
bei einem so eng umrissenen Suchbereich würde ich mir einfach alle echten Potenzen in diesem Bereich vorher erzeugen und in einer sortierten Liste speichern. Dann kann man jeweils in dieser Liste suchen, ob die aktuell betrachtete Zahl darunter ist, oder nicht.
\quoteoff
der enge Bereich ist jetzt für den Test!
ich hab jetzt das
\sourceon Python
\numberson
def is_power_of_y(x, y):
if x <= 2 or y <= 2:
return False
return math.log(x, y).is_integer()
for y in range(3,11,2):
if is_power_of_y(x, y):
pot.append(x)
\sourceoff
Das funktioniert, hat bloss folgende zwei unerwünschte Eigenschaften, hoch 1 will ich nicht haben, das kommt, interessanterweise, obwohl ich den range für y mit 3 starten lasse, und auch wenn ich in der funktion die Nullen hochsetzt, ist der Ausdruck immer derselbe, nämlich: alle Potenzen [3, 5, 7, 9, 9, 25, 27, 49, 81, 81, 343] Die 9 ist zweimal drin, einmal für 3 Quadrat und eine andermal für 9 hoch 1, d81 für 9 WQuadrat und für 3 hoch 4. Wie kriegt man das weg? Einfach nur Primzahlen zulassen als Basis, aber wo?
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
 | Beitrag No.3, eingetragen 2023-06-10
|
Hallo Bekell
\quoteon(2023-06-10 17:38 - Bekell im Themenstart)
wie kann ich testen, ob eine Zahl x ein ganzzahlige Potenz einer ganzen Zahl ist
\quoteoff
Es gibt viele Möglichkeiten, um das zu prüfen. Siehe: https://en.wikipedia.org/wiki/Perfect_power#Detecting_perfect_powers
Alternativ auf Deutsch, aber nicht so gut erklärt, und beschreibt auch nur einen sehr naiven Ansatz: https://de.wikipedia.org/wiki/Perfekte_Potenz#Erkennen_von_perfekten_Potenzen
Da du auch eine Funktion "isprime" zu haben scheinst, würde ich vielleicht den Weg über die Primfaktorzerlegung gehen? Also konkret:
Sei $n\in\IN$. Sei die Primfaktorzerlegung $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ dann ist $n$ eine ganzzahlige Potenz einer ganzen Zahl genau dann, wenn $\gcd(a_1,\,a_2,\,...,\,a_k) > 1$.
Mit $\gcd$ ist der größte gemeinsame Teiler gemeint.
Aber letztendlich musst du schauen, ob dir für deinen Anwendungsfall ggf. bereits einer der naiven Ansätze genügt.
\quoteon(2023-06-10 18:26 - Bekell in Beitrag No. 2)
[3, 5, 7, 9, 9, 25, 27, 49, 81, 81, 343] Die 9 ist zweimal drin, einmal für 3 Quadrat und eine andermal für 9 hoch 1, d81 für 9 WQuadrat und für 3 hoch 4. Wie kriegt man das weg?
\quoteoff
Simpel und naiv wäre, dass du ein Set (Menge) nutzt, statt einer Liste.
Siehe: https://docs.python.org/3/tutorial/datastructures.html#sets
Liebe Grüße
|
Profil
|
Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 364
| Beitrag No.4, eingetragen 2023-06-10
|
Eine Liste aller Quadrate, Kuben, fünften Potenzen, ... im Bereich zu erzeugen und gegen diese dann zu prüfen, dürfte deutlich effizienter sein (solang diese Liste nicht übermäßig groß wird), als jede einzelne Testzahl wieder kompliziert darauf zu prüfen, ob sie eine glatte Potenz ist.
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.5, eingetragen 2023-06-10
|
\quoteon(2023-06-10 19:11 - Ixx in Beitrag No. 4)
im Bereich zu erzeugen und gegen diese dann zu prüfen, dürfte deutlich effizienter sein (solang diese Liste nicht übermäßig groß wird)
\quoteoff
Dadurch, dass Bekell dazu keine explizite Angabe gemacht hat, habe ich Lösungswege aufgezeigt, die allgemeingültig funktionieren, und nicht von impliziten Annahmen über ggf. oder ggf. nicht vorhandene Bereiche abhängig sind.
Anders formuliert: Ggf. existiert überhaupt kein Bereich, für den man etwas "vorberechnen" könnte.
|
Profil
|
Ixx
Aktiv
Dabei seit: 05.04.2020
Mitteilungen: 364
| Beitrag No.6, eingetragen 2023-06-10
|
Das ist natürlich richtig. Beachte aber die üblichen Spielereien, die Bekell so betreibt.
|
Profil
|
DerEinfaeltige
Senior
Dabei seit: 11.02.2015
Mitteilungen: 3291
 | Beitrag No.7, eingetragen 2023-06-10
|
Ohne auf die Bekell'schen "Probleme" eingehen zu wollen:
Ein Algorithmus, der Teiler oder gar die Primfaktorzerlegung benötigt erscheint recht aufwendig.
Da wäre die Suche nach Ganzzahlwurzeln sicherlich leichter zu implementieren und ich vermute sogar, dass sie in realistischen Bereichen (einige Millionen Stellen) effizienter ist.
1. Bestimme 2er-Logarithmus der größten Prüfzahl
2. Siebe Primzahlen bis zu dieser Grenze
3. Iteriere über die Primzahlen
a) suche (bspw. per Newton mit gutem Startwert) die entsprechende Ganzzahlwurzel
b) teste, ob sie "perfekt" ist
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.8, eingetragen 2023-06-10
|
Hallo zusammen.
Ich stimme zu, natürlich kann man effizienter programmieren, als über Primfaktorzerlegung und ggT zu gehen.
Ich finde, dass man die Frage, was "effizient genug" ist, jedoch nicht beantworten kann, ohne konkrete Anforderungen zu kennen.
In so einem Fall bin ich vor allem ein Freund davon, schnell zu einer Lösung zu kommen, die funktioniert, und dabei noch simpel umzusetzen ist.
Wenn wir in der Python Welt unterwegs sind, bin ich immer geneigt, Bibliotheken zu nutzen, um das Rad nicht neu zu erfinden.
Da nicht klar ist, ob Bekell daran interessiert ist, einfach nur eine Funktion zu bekommen, die funktioniert, oder ob er die Algorithmik selbst entwickeln will, kann man auch hier nicht sinnvoll antworten.
Eine sehr kurze Lösung ist nun die Folgende:
\sourceon python
from sympy import factorint, gcd
def is_perfect_power(n):
return gcd(list(factorint(n).values())) > 1
\sourceoff
Ob das "effizient genug" ist - wer weiß das schon, jedenfalls habe ich ein bisschen Benchmarking betrieben, dann kann man selbst entscheiden, ob das passt oder nicht.
\sourceon python
import random
import time
import matplotlib.pyplot as plt
from sympy import factorint, gcd
def is_perfect_power(n):
return gcd(list(factorint(n).values())) > 1
class Timer:
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
self.end = time.time()
self.interval = self.end - self.start
if __name__ == "__main__":
random.seed(1337)
test_values = [random.randint(10 ** (i - 1), 10 ** i) for i in range(1, 21) for _ in range(100)]
run_times = []
for n in test_values:
with Timer() as t:
is_perfect_power(n)
run_times.append(t.interval)
plt.figure(figsize=(10, 6))
plt.scatter(test_values, run_times, s=1)
plt.xscale('log')
plt.yscale('log')
plt.xlabel('n')
plt.ylabel('Laufzeit (Sekunden)')
plt.title('Laufzeit von is_perfect_power in Abhängigkeit von n')
plt.grid(True)
plt.show()
\sourceoff
https://matheplanet.com/matheplanet/nuke/html/uploads/c/56201_myplot.png
Liebe Grüße
|
Profil
|
Scynja
Senior 
Dabei seit: 23.02.2011
Mitteilungen: 590
Wohnort: Deutschland
| Beitrag No.9, eingetragen 2023-06-10
|
\quoteon(2023-06-10 20:10 - DerEinfaeltige in Beitrag No. 7)
Ohne auf die Bekell'schen "Probleme" eingehen zu wollen:
Ein Algorithmus, der Teiler oder gar die Primfaktorzerlegung benötigt erscheint recht aufwendig.
Da wäre die Suche nach Ganzzahlwurzeln sicherlich leichter zu implementieren und ich vermute sogar, dass sie in realistischen Bereichen (einige Millionen Stellen) effizienter ist.
1. Bestimme 2er-Logarithmus der größten Prüfzahl
2. Siebe Primzahlen bis zu dieser Grenze
3. Iteriere über die Primzahlen
a) suche (bspw. per Newton mit gutem Startwert) die entsprechende Ganzzahlwurzel
b) teste, ob sie "perfekt" ist
\quoteoff
Hallo DerEinfaeltige,
könntest du deinen Algorithmus bitte etwas näher erläutern? Mir ist nicht klar wozu der 2er-Logarithmus benötigt wird und warum Primzahlen gesiebt werden.
Ist die größte Prüfzahl $\sqrt{x}$ ?
Gerne auch an einem Beispiel wie 216.
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.10, eingetragen 2023-06-10
|
\quoteon(2023-06-10 23:01 - Scynja in Beitrag No. 9)
Mir ist nicht klar wozu der 2er-Logarithmus benötigt wird und warum Primzahlen gesiebt werden.
\quoteoff
Siehe: https://en.wikipedia.org/wiki/Perfect_power#Detecting_perfect_powers
|
Profil
|
Scynja
Senior
Dabei seit: 23.02.2011
Mitteilungen: 590
Wohnort: Deutschland
| Beitrag No.11, eingetragen 2023-06-10
|
\quoteon(2023-06-10 23:05 - polygamma in Beitrag No. 10)
@Scynja, siehe: https://en.wikipedia.org/wiki/Perfect_power#Detecting_perfect_powers
\quoteoff
Hallo polygamma,
ich habe den Beitrag so verstanden, dass DerEinfaeltige eine Zahl nimmt und dann per Newton $x^{1/2} ... x^{1/n}$ ausrechnet und prüft, ob die Zahl ungefähr ganzzahlig ist. Wenn die Ergebnismenge allerdings klein genug ist, kann man sicherlich auf den verlinkten Algorithmus umschwenken und durchprobieren.
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.12, eingetragen 2023-06-10
|
Hallo Scynja,
das, was DerEinfaeltige in seinem Algorithmus nutzt, steht alles in dem Wikipedia Artikel an der verlinkten Stelle, deswegen hatte ich es dir verlinkt.
Er hat es jedoch "umgebaut", sodass man es sinnvoll nutzen kann, wenn man weiß, dass man mehrere Zahlen hat, von denen man wissen will, ob sie perfect powers sind.
Die "größte Prüfzahl" ist die größte Zahl, von der man wissen will, ob sie eine perfect power ist.
Sei $n$ eine Zahl, von der man wissen will, ob sie eine perfect power ist.
Wie bei Wikipedia soll gelten $n=m^k$ mit $m,k>1$.
Als $k$ müssen nur Primzahlen $\leq\log_2n$ in Betracht gezogen werden.
Ist nun die größte Zahl, von der man wissen will, ob sie eine perfect power ist, z. B. $1000$, so berechnet man alle Primzahlen $\leq\log_{2}1000$.
Jetzt habe ich also ein $n\leq 1000$, von dem ich wissen will, ob es eine perfect power ist.
Ich iteriere über alle Primzahlen $p\leq\log_2n$, die ich ja alle berechnet habe, und prüfe ob $\sqrt[p]{n}$ eine ganze Zahl ist.
Falls es ein solches $p$ gibt, sodass wir eine ganze Zahl erhalten, ist $n$ eine perfect power.
Falls es kein solches $p$ gibt, ist $n$ keine perfect power.
Ich habe den Algorithmus von DerEinfaeltige Quick & Dirty implementiert und wieder Benchmarking betrieben, im Vergleich zu meiner "One-Liner" Lösung aus https://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=262676&post_id=1908781
\sourceon python
import random
import time
from math import floor, log2, log10
from matplotlib import pyplot as plt
from sympy import factorint, gcd, sieve
def is_perfect_power_gcd(n):
return gcd(list(factorint(n).values())) > 1
def is_perfect_power_primes(n, primes):
log2_n = log2(n)
for prime in primes:
if prime > log2_n:
break
elif n == round(n ** (1 / prime)) ** prime:
return True
return False
class Timer:
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
self.end = time.time()
self.interval = self.end - self.start
if __name__ == "__main__":
max_n = 10 ** 22
primes = list(sieve.primerange(floor(log2(max_n)) + 1))
random.seed(1337)
test_values = [
random.randint(10 ** (i - 1), 10 ** i) for i in range(1, floor(log10(max_n)) + 1) for _ in range(100)
]
run_times_gcd = []
run_times_primes = []
for n in test_values:
with Timer() as t:
gcd_result = is_perfect_power_gcd(n)
run_times_gcd.append(t.interval)
with Timer() as t:
primes_result = is_perfect_power_primes(n, primes)
run_times_primes.append(t.interval)
assert gcd_result == primes_result
plt.figure(figsize=(10, 6))
plt.scatter(test_values, run_times_gcd, label='is_perfect_power_gcd', s=1)
plt.scatter(test_values, run_times_primes, label='is_perfect_power_primes', s=1)
plt.xscale('log')
plt.yscale('log')
plt.xlabel('n')
plt.ylabel('Laufzeit (Sekunden)')
plt.title('Laufzeit in Abhängigkeit von n')
plt.legend()
plt.grid(True)
plt.show()
\sourceoff
https://matheplanet.com/matheplanet/nuke/html/uploads/c/56201_myplot2.png
Wie zu erwarten, ist der Algorithmus von DerEinfaeltige deutlich schneller :)
Liebe Grüße
|
Profil
|
Bekell
Aktiv
Dabei seit: 05.09.2008
Mitteilungen: 3227
| Beitrag No.13, vom Themenstarter, eingetragen 2023-06-11
|
Ich bin selber des Einfältigen Weg gegangen. Das die perfekten Potenzen sehr wenige Zahlen sind und immer dünner werden, kann man rechentechnisch, die sehr schnell bilden und einfach einen Vergleich machen.
|
Profil
|
Klaus-Peter
Neu 
Dabei seit: 05.03.2022
Mitteilungen: 4
| Beitrag No.14, eingetragen 2023-06-11
|
Guten Abend,
bin Python-Anfänger. Habe gestern anhand des verlinkten Wiki-Artikels mal etwas probiert. Die Print-Ausgaben können natürlich reduziert werden.
\sourceon Python
import math
import sys
#Liste für Teiler von der zu prüfenden Zahl
liste=[]
zahl = 117649
i = math.floor(zahl/2)
while(i>1):
if(zahl%i==0):
print(i)
liste.append(i)
i-=1
print(liste)
grenze=(int(math.log2(117649)))
print()
print('Obergrenze Potenz: ',grenze)
print()
#ermitteln der Primzahlen bis zur Obergrenze
def isprim(wert):
x = 2
if wert == 0 or wert == 1:
return False
elif wert == 2:
return True
else:
while x < wert:
if wert % x == 0:
return False
x = x + 1
return True
Liste_Primzahlen=[]
y = 0
while y <= grenze:
if isprim(y):
Liste_Primzahlen.append(y)
y = y + 1
else:
y = y + 1
print('Liste der Primzahlen bis ',grenze,': ',Liste_Primzahlen)
print()
print('Anzahl Teiler: ',len(liste))
liste.sort()
print('erstes Element: ',liste[0])
print()
a=int(liste[0])
b=int(Liste_Primzahlen[0])
q=0
print(int(liste[q+1]))
x=liste[0]
y=0
for i in liste:
for j in Liste_Primzahlen:
print(i,' hoch ',j,i**j)
if i**j==zahl:
print(i**j,'ist eine ganzzahlige Potenz')
sys.exit()
else:
print(zahl,'ist keine ganzzahlige Potenz')
y+=1
x+=1
\sourceoff
Wie gasagt, bin Anfänger. Geht sicherlich auch anders zu machen.
Schönen Abend!
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.15, eingetragen 2023-06-11
|
Hallo, Klaus-Peter!
Sehr schön :)
Da du Anfänger bist, und angesprochen hast, dass es bestimmt auch anders geht, habe ich mal deine Algorithmik genommen, und es nur "umgeschrieben".
Algorithmisch optimiert habe ich nichts, sondern nur komprimiert, was du bereits getan hast.
Vielleicht bringt es dir was, einfach mal zu sehen, wie deine eigenen Gedanken in anderer Form aufgeschrieben aussehen könnten :)
\sourceon python
from math import floor, log2
def find_divisors(n):
"""Findet alle nicht-trivialen Teiler der gegebenen Zahl."""
return [i for i in range(2, n // 2 + 1) if n % i == 0]
def is_prime(n):
"""Prüft, ob eine gegebene Zahl eine Primzahl ist."""
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def find_primes_until(n):
"""Findet alle Primzahlen bis zur gegebenen Zahl."""
return [i for i in range(n + 1) if is_prime(i)]
def check_integer_power(n):
"""Prüft, ob die gegebene Zahl eine perfect power ist."""
divisors = find_divisors(n)
primes = find_primes_until(floor(log2(n)))
for divisor in divisors:
for prime in primes:
if divisor ** prime == n:
return True
return False
if __name__ == "__main__":
max_n = 10 ** 2
for n in range(1, max_n + 1):
if check_integer_power(n):
print(f"{n} ist eine perfect power")
\sourceoff
\sourceon
4 ist eine perfect power
8 ist eine perfect power
9 ist eine perfect power
16 ist eine perfect power
25 ist eine perfect power
27 ist eine perfect power
32 ist eine perfect power
36 ist eine perfect power
49 ist eine perfect power
64 ist eine perfect power
81 ist eine perfect power
100 ist eine perfect power
\sourceoff
Liebe Grüße
|
Profil
|
Klaus-Peter
Neu
Dabei seit: 05.03.2022
Mitteilungen: 4
| Beitrag No.16, eingetragen 2023-06-11
|
Hallo polygamma,
schwere Kost. Schaue ich mir gern mal an. Wird dauern....
Vielen Dank!
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.17, eingetragen 2023-06-11
|
Hallo Klaus-Peter!
\quoteon(2023-06-11 21:37 - Klaus-Peter in Beitrag No. 16)
schwere Kost.
\quoteoff
Hier noch einmal der gleiche Code, jedoch leichter verdaulich (hoffe ich ;D)
\sourceon python
from math import floor, log2
def find_divisors(n):
"""Findet alle nicht-trivialen Teiler der gegebenen Zahl."""
divisors = []
for i in range(2, floor(n / 2) + 1):
if n % i == 0:
divisors.append(i)
return divisors
def is_prime(n):
"""Prüft, ob eine gegebene Zahl eine Primzahl ist."""
if n < 2:
return False
for i in range(2, n):
if n % i == 0:
return False
return True
def find_primes_until(n):
"""Findet alle Primzahlen bis zur gegebenen Zahl."""
primes = []
for i in range(n + 1):
if is_prime(i):
primes.append(i)
return primes
def check_integer_power(n):
"""Prüft, ob die gegebene Zahl eine perfect power ist."""
divisors = find_divisors(n)
primes = find_primes_until(floor(log2(n)))
for divisor in divisors:
for prime in primes:
if divisor ** prime == n:
return True
return False
if __name__ == "__main__":
max_n = 10 ** 2
for n in range(1, max_n + 1):
if check_integer_power(n):
print(str(n) + " ist eine perfect power")
\sourceoff
Das Hauptkonzept, das den Code wahrscheinlich "schwer verdaulich" gemacht hat: List Comprehensions
Das ist letztendlich eine andere Schreibweise dafür, wie man Listen befüllen kann.
Sonst war da noch der // Operator.
// ist eine Kurzschreibweise für Division gefolgt von Abrunden.
Und das print war genutzt in Kombination mit Fancier Output Formatting (konkret Formatted String Literals).
Liebe Grüße
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.18, eingetragen 2023-06-12
|
Hallo Bekell!
\quoteon(2023-06-11 16:12 - Bekell in Beitrag No. 13)
Das die perfekten Potenzen sehr wenige Zahlen sind und immer dünner werden, kann man rechentechnisch, die sehr schnell bilden und einfach einen Vergleich machen.
\quoteoff
Ich bin mir nicht ganz sicher, was du damit sagen möchtest, aber es klingt so, als würdest du die Verteilung von perfekten Potenzen untersuchen.
In dem Fall empfehle ich dir etwas Anderes, nämlich, dass du perfekte Potenzen generierst, statt sie zu suchen.
Anders formuliert: Es ist effizienter, perfekte Potenzen für einen gegebenen Bereich zu generieren, statt den Bereich Zahl für Zahl durchzugehen, und zu prüfen, welche Zahlen perfekte Potenzen sind.
Sei $n\in\IN$ eine perfekte Potenz genau dann, wenn $\exists m,k\in\IN_{>1}:n=m^k$.
Lemma $1$:
Sei $n\in\IN$ eine perfekte Potenz und sei $\mathbb{P}$ die Menge der Primzahlen.
Es gilt: $$\exists m\in\IN_{>1},\,p\in\mathbb{P}:n=m^p$$
Beweis:
Seien $m,k\in\IN_{>1}$ mit $n=m^k$.
Es existieren $q\in\IN_{\geq1}$ sowie $p\in\mathbb{P}$ mit $k=qp$.
Es folgt $n=m^k=m^{qp}=\left(m^q\right)^p$.
Wir definieren $\hat{m}:=m^q$.
Es folgt $n=\hat{m}^p$ mit $\hat{m}\in\IN_{>1}\,\square$
Lemma $2$:
Sei $n\in\IN_{\geq 1}$ und sei $\mathbb{P}$ die Menge der Primzahlen.
Die Anzahl der perfekten Potenzen $\leq n$ bezeichnen wir mit $N$.
Es gilt: $$N\leq\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)$$
Beweis:
Seien $m,k\in\IN_{>1}$ und gelte $m^k\leq n$.
Um $k$ zu maximieren, muss $m$ minimiert werden, also $2^k\leq n\Longleftrightarrow k\leq\left\lfloor\log_2n\right\rfloor$.
Aus Lemma $1$ folgt, dass es genügt $k\in\mathbb{P}$ zu betrachten, um alle perfekten Potenzen $\leq n$ zu generieren.
Weiterhin gilt $m^k\leq n \Longleftrightarrow m\leq\left\lfloor\sqrt[k]{n}\right\rfloor$ und per Definition $m\geq2$ und wegen $n\geq 1$ auch $\left\lfloor\sqrt[k]{n}\right\rfloor\geq 1$.
Iteration über $k$ liefert die gesuchte Abschätzung. $\square$
\sourceon python
import time
from gmpy2 import floor, log2, mpz, mpq, get_context
from sympy import sieve, mobius
def perfect_power_generator(N):
for p in sieve.primerange(mpz(floor(log2(mpz(N)))) + 1):
for m in range(2, mpz(floor(mpz(N) ** mpq(1, p))) + 1):
yield m ** p
def perfect_power_count_mobius(N):
return sum(
-mobius(mpz(k)) * (mpz(floor(mpz(N) ** mpq(1, k))) - 1) for k in range(2, mpz(floor(log2(mpz(N)))) + 1)
)
class Timer:
def __enter__(self):
self.start = time.time()
return self
def __exit__(self, *args):
self.end = time.time()
self.interval = self.end - self.start
if __name__ == "__main__":
get_context().precision = 2 ** 12
to_assert = True
to_print = True
min_N = 10 ** 15
max_N = min_N
for N in range(min_N, max_N + 1):
perfect_power_set = set()
perfect_power_mobius = perfect_power_count_mobius(N)
perfect_power_counter = 0
with Timer() as t:
for perfect_power in perfect_power_generator(N):
perfect_power_counter += 1
perfect_power_set.add(perfect_power)
perfect_power_generated = len(perfect_power_set)
if to_assert:
assert perfect_power_counter >= perfect_power_generated == perfect_power_mobius
if to_print:
print(
f'Time needed to generate perfect powers up to {N}: {t.interval:.3f}s\n'
f'We generated {perfect_power_counter} perfect powers and the actual number is {perfect_power_generated}\n'
f'So we generated {perfect_power_counter - perfect_power_generated} too many\n'
f'Mobius tells us that there are {perfect_power_mobius} perfect powers\n'
f'Mobius and we got the same results: {perfect_power_mobius == perfect_power_generated}'
)
\sourceoff
\sourceon
Time needed to generate perfect powers up to 1000000000000000: 9.235s
We generated 31723967 perfect powers and the actual number is 31723591
So we generated 376 too many
Mobius tells us that there are 31723591 perfect powers
Mobius and we got the same results: True
\sourceoff
Die Generierung aller perfekten Potenzen bis $10^{15}$ hat also keine $10$ Sekunden gedauert (z. B. in C++ ginge das viel, viel schneller), und es wurden auch nur $376$ zu viel generiert, die Abschätzung passt also ganz gut :)
Liebe Grüße
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.19, eingetragen 2023-06-12
|
Hallo zusammen!
\quoteon(2023-06-12 04:49 - polygamma in Beitrag No. 18)
Sei $n\in\IN_{\geq 1}$ und sei $\mathbb{P}$ die Menge der Primzahlen.
Die Anzahl der perfekten Potenzen $\leq n$ bezeichnen wir mit $N$.
Es gilt: $$N\leq\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)$$
\quoteoff
Eine Abschätzung $N\leq\,...$ ist zwar ganz nett, aber eigentlich hätte ich gerne $N=\,...$ (ohne Verwendung der Möbiusfunktion) das wäre doch ein bisschen cooler ;D
Ganz angekommen bin ich noch nicht, aber ich konnte die Abschätzung nochmal verschärfen :)
Sei $n\in\IN_{\geq 1}$ und sei $\mathbb{P}$ die Menge der Primzahlen.
Die Anzahl der perfekten Potenzen $\leq n$ bezeichnen wir mit $N$.
Es gilt: $$N\leq\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\left\lfloor\sqrt[6]{n}\right\rfloor+1$$
Für $n=10^{15}$ wird nur noch $61$ statt $376$ überschätzt :)
Liebe Grüße
|
Profil
|
Klaus-Peter
Neu
Dabei seit: 05.03.2022
Mitteilungen: 4
| Beitrag No.20, eingetragen 2023-06-12
|
Hallo pollygamma,
herzlichen Dank für Deine Erläuterungen.
Ich schaue mir das in Ruhe mal an.
Diese List Comprehensions sind schon der Hammer. Mal sehen ob mein Hirn dafür noch Platz hat. Nochmals Danke für die Mühe und einen schönen Abend.
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.21, eingetragen 2023-06-13
|
Hallo zusammen!
\quoteon(2023-06-12 18:41 - polygamma in Beitrag No. 19)
Eine Abschätzung $N\leq\,...$ ist zwar ganz nett, aber eigentlich hätte ich gerne $N=\,...$ (ohne Verwendung der Möbiusfunktion) das wäre doch ein bisschen cooler ;D
Ganz angekommen bin ich noch nicht
\quoteoff
Ich denke (hoffe ;D), dass ich nun angekommen bin :)
Sei $n\in\IN_{\geq1}$ und sei $\mathbb{P}$ die Menge der Primzahlen.
$n$ ist eine perfekte Potenz genau dann, wenn $\exists m,k\in\IN_{>1}:n=m^k$.
Wir bezeichnen die Anzahl der perfekten Potenzen $\leq n$ mit $N$.
Wir definieren $$\mathbb{P}_n:=\left\{p\in\mathbb{P}: p\leq\left\lfloor\log_4n\right\rfloor\right\}$$
Es folgt: $$N=\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\sum_{k=2}^{|\mathbb{P}_n|}(-1)^{k}\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
Für $\mathbb{P}_n=\left\{2,\,3\right\}$ erhält man jedenfalls meine Abschätzung aus dem vorigen Beitrag:
\quoteon(2023-06-12 18:41 - polygamma in Beitrag No. 19)
$$N\leq\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\left\lfloor\sqrt[6]{n}\right\rfloor+1$$
\quoteoff
Liebe Grüße
|
Profil
|
polygamma
Aktiv
Dabei seit: 18.02.2023
Mitteilungen: 316
Wohnort: Kiel
| Beitrag No.22, eingetragen 2023-06-14
|
Hallo zusammen!
Ich möchte das Folgende etwas erklären...
\quoteon(2023-06-13 14:52 - polygamma in Beitrag No. 21)
Sei $n\in\IN_{\geq1}$ und sei $\mathbb{P}$ die Menge der Primzahlen.
$n$ ist eine perfekte Potenz genau dann, wenn $\exists m,k\in\IN_{>1}:n=m^k$.
Wir bezeichnen die Anzahl der perfekten Potenzen $\leq n$ mit $N$.
Wir definieren $$\mathbb{P}_n:=\left\{p\in\mathbb{P}: p\leq\left\lfloor\log_4n\right\rfloor\right\}$$
Es folgt: $$N=\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\sum_{k=2}^{|\mathbb{P}_n|}(-1)^{k}\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
\quoteoff
Beginnen wir mit der ersten Summe:
\quoteon(2023-06-13 14:52 - polygamma in Beitrag No. 21)
$$\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)$$
\quoteoff
Eingeführt wurde sie in: https://matheplanet.com/matheplanet/nuke/html/viewtopic.php?topic=262676&post_id=1908892
Sie "zählt" wie viele perfekte Potenzen $\leq n$ generiert werden können, indem man die Wertebereiche für $m$ und $k$ jeweils maximal ausreizt und mit $k\in\mathbb{P}$ über alle Möglichkeiten iteriert.
Dadurch, dass $m^k=\hat{m}^\hat{k}$ für $m\neq\hat{m}$ und $k\neq\hat{k}$ gelten kann, zählen wir manche perfekten Potenzen mehr als einmal.
Die Frage ist also: Wie viel "überzählen" wir?
Runterbrechen lässt sich das auf eine Sache, die schon am Anfang im Thread angesprochen wurde:
\quoteon(2023-06-10 18:32 - polygamma in Beitrag No. 3)
Sei $n\in\IN$. Sei die Primfaktorzerlegung $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$ dann ist $n$ eine ganzzahlige Potenz einer ganzen Zahl genau dann, wenn $\gcd(a_1,\,a_2,\,...,\,a_k) > 1$
Mit $\gcd$ ist der größte gemeinsame Teiler gemeint.
\quoteoff
Die Beobachtung ist nun die Folgende:
Wenn wir die Primfaktorzerlegung des $\gcd$ betrachten, verraten uns die Primteiler, ob die entsprechende perfekte Potenz mehrfach gezählt wurde oder nicht.
Sei $M$ die "Anzahl der Zählungen" von einer perfekten Potenz $n$ mit der Primfaktorzerlegung $n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$
Es folgt mit der prime omega function: $M=\omega(\gcd(a_1,\,a_2,\,...,\,a_k))$
Gilt $M>1$ so haben wir überzählt.
Wir kommen zur dritten Summe:
\quoteon(2023-06-13 14:52 - polygamma in Beitrag No. 21)
$$\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
\quoteoff
Der Knackpunkt sind die $\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor$
Wegen $n\geq 1$ sind sie immer $\geq 1$, den Wert $2$ erreichen sie bei $n=2^{\prod_{p\in P}p}$, den Wert $3$ bei $n=3^{\prod_{p\in P}p}$ usw.
Sie werden somit jeweils "getriggert", wenn ein $n$ erreicht wird, das zu Überzählung geführt hat :)
Man beachte, dass $|X|\geq 2$ gilt, da die zweite Summe mit $k=2$ beginnt, sodass wir tatsächlich nur für $M>1$ triggern, und nicht für $M=1$
Nun zum Summationsbereich: $$\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}$$
Sieht wild aus, ist aber eigentlich ganz einfach.
Wir iterieren über alle $k$-elementigen Teilmengen von $\mathbb{P}_n$ für $k\geq 2$
$\prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor$ ist eine "Abbruchbedingung" der Iteration, um nicht $\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor$ aufzusummieren, die sowieso nur $=1$ sind, womit $\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1=0$ folgen würde.
In der Definition von $\mathbb{P}_n$ befindet sich auch eine Abbruchbedingung mit $p\leq\left\lfloor\log_4n\right\rfloor$
Die kleinste Primzahl ist $2$, und das kleinste $k$ ist ebenfalls $2$
Es geht also um $\left\lfloor\sqrt[2p]{n}\right\rfloor>1$ mit $p\in\mathbb{P}_{>2}$
Bleibt noch:
\quoteon(2023-06-13 14:52 - polygamma in Beitrag No. 21)
$$\sum_{k=2}^{|\mathbb{P}_n|}(-1)^{k}$$
\quoteoff
Hier ist nun das $(-1)^{k}$ interessant, das festlegt, was rausgerechnet wird, denn wir haben zwar bereits über Trigger gesprochen, jedoch nur darüber, dass sie getriggert werden, und nicht darüber, was damit rausgerechnet wird ;)
Die Grundidee ist die Folgende:
Wenn ein Trigger getriggert wird, sagt das $k$, wie viel überzählt wurde, nämlich $k-1$
Es muss die Anzahl der Trigger betrachtet werden, die jeweils gleichzeitig getriggert werden.
Wenn z. B. die Menge $\mathbb{P}_n=\{2,\,3,\,5\}$ und $k=3$ vorliegt, werden natürlich auch die $k=2$ Trigger mitgetriggert, und diese rechnen bereits Überzählung raus.
Über Binomialkoeffizienten landet man jedoch final einfach nur bei $(-1)^{k}$ als "Faktor der Rausrechnung" :)
Daraus folgt die Erkenntnis, dass mithilfe der Möbiusfunktion das Folgende ausgedrückt werden kann:
$$N=\left(\sum_{\substack{p\in\mathbb{P}\\ p\leq \left\lfloor\log_2n\right\rfloor}}\left(\left\lfloor\sqrt[p]{n}\right\rfloor-1\right)\right)-\sum_{k=2}^{|\mathbb{P}_n|}\sum_{\substack{P\in\left\{X\subseteq\mathbb{P}_n:|X|=k\right\}\\ \prod_{p\in P}p\leq\left\lfloor\log_2n\right\rfloor}}\mu\left(\prod_{p\in P}p\right)\left(\left\lfloor\sqrt[\prod_{p\in P}p]{n}\right\rfloor-1\right)$$
Das ist jedoch nicht einfacher, sondern schwerer zu berechnen, also lassen wir das lieber ;D
Liebe Grüße
|
Profil
|
| Bekell hat die Antworten auf ihre/seine Frage gesehen. | | Bekell wird per Mail über neue Antworten informiert. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
2023-09-22 22:09 U ?
Wie unterstütze ich den Matheplaneten mit Geld?
