TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 196

Wieviele natürliche Zahlen n mit $1\leq n\leq 10^{6}$ gibt es, die weder Quadrat, noch dritte, vierte oder fünfte Potenz einer natürlichen Zahl sind?

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösungsvorschlag von Soymilk-Drinker

Variablen

$G$ ... Grundmenge ($1\leq n\leq 10^{6}$, daher Intervall [1, 1000.000])

$P_{X}$ ... Menge aller Zahlen aus der Grundmenge die eine x-te Potenz einer Natürlichen Zahl sind (Bsp. $P_{2}$ alle quadratischen Zahlen, $P_{3}$ alle Zahlen die eine dritte Potenz sind, $P_{2,3}=P_{2}\cap P_{3}$ alle Zahlen die sowohl quadratisch als auch dritte Potenz sind)

Es gibt bei diesen P Mengen noch eine Besonderheit, nämlich die Mengen $P_{2}$ und $P_{4}$, denn $P_{4}\subset P_{2}$

(Ergänzung von --Mnemetz 08:16, 7. Dez 2005 (CET))

Wieso das gilt kann man sehr leicht sehen wenn man sich die Menge $P_{4}$ ansieht. Sie enthält alle Zahlen welche die vierte Potenz einer natürlichen Zahl (x) sind. Schreibt man dies nun auf kann man leicht umformen:

$x^{4}\qquad =x*x*x*x\qquad =x^{2}*x^{2}\qquad =(x^{2})^{2}$

Man sieht also dass alle Zahlen aus $P_{4}$ auch automatisch in $P_{2}$ enthalten sind. Das hat den Vorteil wenn man sich die P Mengen ansieht welche gleichzeitig Zahlen enthalten die quadratisch und von der vierten Potenz sind. Nehmen wir als Beispiel die Menge $P_{2,4}$ her, anderst geschrieben lautet diese ja $P_{2}\cap P_{4}$, da aber $P_{4}$ eine Teilmenge von $P_{2}$ ist kann man das ganze auch vereinfachen.

z.B $P_{2,4}\qquad =P_{2}\cap P_{4}\qquad =P_{4}$ (nur wenn $P_{4}\subset P_{2}$)

z.B $P_{2,3,4}\qquad =P_{2}\cap P_{3}\cap P_{4}\qquad =P_{3}\cap P_{2}\cap P_{4}\qquad =P_{3}\cap P_{4}\qquad =P_{3,4}$ (nur wenn $P_{4}\subset P_{2}$)

Einfach gesagt, man kann bei allen P Mengen bei denen im Index sowohl 2 als auch 4 steht, die 2 einfach weglassen.

Formel

Gesucht ist die Anzahl der Zahlen welche aus G sind, aber weder Quadrat, noch dritte, vierte oder fünfte Potenz einer natürlichen Zahl. Wir müssen also von G die einzelnen P Mengen entfernen und schon haben wir diese Zahlen. Berechnet wird dies einfach mit der Siebformel:

$|G|\qquad -|P_{2}|-|P_{3}|-|P_{4}|-|P_{5}|\qquad +|P_{2,3}|+|P_{2,4}|+|P_{2,5}|+|P_{3,4}|+|P_{3,5}|+|P_{4,5}|\qquad -|P_{2,3,4}|-|P_{2,3,5}|-|P_{2,4,5}|-|P_{3,4,5}|\qquad +|P_{2,3,4,5}|$

Wie ich schon beim Punkt Variablen geschrieben habe kann man Vereinfachen wenn P Mengen gleichzeitig quadratische und Zahlen der vierten Potenz enthalten. Wenn ich das jetzt mache ergibt

$|G|\qquad -|P_{2}|-|P_{3}|-|P_{4}|-|P_{5}|\qquad +|P_{2,3}|+|P_{4}|+|P_{2,5}|+|P_{3,4}|+|P_{3,5}|+|P_{4,5}|\qquad -|P_{3,4}|-|P_{2,3,5}|-|P_{4,5}|-|P_{3,4,5}|\qquad +|P_{3,4,5}|$

Damit fallen jetzt einige Werte weg da sie in positiver und negativer Ausführung da sind und sich somit auslöschen. Damit wird das ganze noch mal vereinfacht

$|G|\qquad -|P_{2}|-|P_{3}|-|P_{5}|\qquad +|P_{2,3}|+|P_{2,5}|+|P_{3,5}|\qquad -|P_{2,3,5}|$

Sieht man sich diese neue Formel an, wird man gleich sehen dass die ja eigentlich der Siebformel entspricht wenn man von G nur die Zahlen möchte die weder Quadrat, noch dritte oder fünfte Potenz einer natürlichen Zahl sind (die Zahlen der vierten Potenz würden somit wegfallen, sind aber sowieso in $P_{2}$ enthalten)

Anzahl der Elemente in den Mengen

Um das Beispiel mit der Formel nun Lösen zu können brauchen wir nur noch für die einzelnen Mengen die Anzahl der Elemente.

Für G ist dies 1.000.000 (eben weil G sämltiche Zahlen im Intervall [1,1.000.000] enthält)

Bei den einzelnen P Mengen muss man sich schon mehr überlegen. Ich nehme zur Erklärung mal die Menge $P_{2}$ her. Wie viele quadratische Zahlen gibt es nun zwischen 1 und 1.000.000.

Alle Zahlen abzählen wäre natürlich möglich, aber das dauert lange, besser ist es wenn man Wurzeln zieht. 1 ist die erste quadratische Zahl, zieht man daraus die Wurzel (man braucht nur die positiven Werte, die negativen sind ja in der Grundmenge schon mal gar nicht enthalten) so erhält man wieder die 1. Die nächste Zahl wäre die 4, hier die Wurzel gezogen ergibt 2. Dann kommt die 9, daraus die Wurzel ist die 3.

Das kann man jetzt immer so weiter führen, aber schon jetzt zeigt sich dass das Ergebnis des Wurzelziehens ja eigentlich ist die wie vielte Zahl es ist. Macht man das nun bei 1.000.000 so erhält man 1.000 als Ergebnis und kann sagen dass 1.000.000 die 1.000ste quadratische Zahl ist. Die nächste quadratische Zahl wäre schon außerhalb des Intervalls, also kann man sagen dass es im Intervall [1,1.000.000] genau 1.000 quadratische Zahlen gibt.

Diese Methode kann man jetzt auch auf die anderen P Mengen umlegen, man muss einfach die jeweilige Wurzel von 1.000.000 ziehen und die Nachkommastellen wegfallen lassen (die wirklich letzte Zahl von der man schön die Wurzel ziehen könnte wäre in einigen Fällen kleiner als 1.000.000, man erspart es sich aber diese zu suchen da man durch das Wurzelziehen und wegfallen lassen der Nachkomma stellen das selbe Ergebnis hat wie als wenn man direkt die richtige Zahl verwendet hätte).

Es bleibt nur noch eine Frage übrig, und zwar wie man zB auf die Anzahl der Elemten in $P_{2,3}$ kommt. Die Menge beinhaltet sowohl Zahlen der dritten Potenz als auch quadratische, wie viele gibt es davon?

Man sehe sich einfach folgende Rechenregeln beim Potenzieren an:

$Y\qquad =(X^{A})^{B}\qquad =X^{A*B}\qquad =X^{B*A}\qquad =(X^{B})^{A}$

Man kann daraus lesen dass jede Zahl Y sowohl eine A-te Potzen als auch eine B-te Potenz ist wenn es ein X gibt für das gilt $Y=X^{A*B}$

Wie ist das jetzt für uns zu gebrauchen? Nun ganz einfach, wir suchen ja zB die Zahlen die sowohl Quadratisch (Potenz 2) als auch von der Potenz 3 sind. Wendet man jetzt den vorherigen Satz an so kann man sagen wir suchen eigentlich alle Zahlen die von der Potenz 6 sind (daher $P_{2,3}=P_{6}$). Und damit können wir jetzt leicht rechnen, denn wie wir die Anzahl der Zahlen die von eine bestimmte Potenz sind, wissen wir ja (Wurzel ziehen).

Lösung

Unsere Formel zur Berechnung der Zahlen lautete ja:

$|G|\qquad -|P_{2}|-|P_{3}|-|P_{5}|\qquad +|P_{2,3}|+|P_{2,5}|+|P_{3,5}|\qquad -|P_{2,3,5}|$

Nach dem letzen Absatz kann man das jetzt auch umschreiben:

$|G|\qquad -|P_{2}|-|P_{3}|-|P_{5}|\qquad +|P_{6}|+|P_{10}|+|P_{15}|\qquad -|P_{30}|$

Und nun brauchen wir nur noch die einzelnen Werte auszurechnen und zusammenzählen:

$1.000.000\qquad -1.000-100-15\qquad +10+3+2\qquad -1\qquad =998.899$

Es gibt also insgesamt 998.899 Zahlen im Intervall [1,1.000.000] welche weder Quadrat, noch dritte, vierte oder fünfte Potenz einer natürlichen Zahl sind.

Links zu anderen Lösungen der gleichen (erweiterten) Aufgabe

TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 167