TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 191

Aus VoWi
Wechseln zu: Navigation, Suche

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?

Lösungsvorschlag von Soymilk-Drinker[Bearbeiten]

Variablen[Bearbeiten]

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

Bsp153 1.png

(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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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