Anzahl quadratfreier Zahlen

21.02.2017, 10:35

MathematicalGates

Anzahl quadratfreier Zahlen

Meine Frage:
Hallo!

Ich bräuchte einen Tipp für die angehängte Aufgabe, da ich leider keine Ahnung habe, wie ich anfangen könnte.

Meine Ideen:
Ich habe leider keinerlei hilfreiche Ideen, weil ich bisher keine Erfahrungen in der Zahlentheorie habe.
Hab erstmal nur gedacht einfach zu zählen, das löst mir das Problem aber nicht.

21.02.2017, 10:38

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von MathematicalGates
Hab erstmal nur gedacht einfach zu zählen, das löst mir das Problem aber nicht.

Doch, eigentlich schon.

21.02.2017, 10:44

MathematicalGates

Auf diesen Beitrag antworten »

Wirklich?
Na gut, ich dachte es würde eine Formel geben, die mir helfen könnte, aber wenn es keine gibt, dann zähle ich ab.

Danke für die schnelle Antwort und deine Hilfe.

21.02.2017, 10:47

IfindU

Auf diesen Beitrag antworten »

Wenn durchzaehlen wirklich das beste ist, dann wuerde ich eine Modifikation des Sieb des Eratosthenes vorschlagen.

21.02.2017, 10:47

HAL 9000

Auf diesen Beitrag antworten »

Man kann natürlich die Sache etwas vereinfachen, indem man zunächst die Zahlen zählt, die nicht quadratfrei sind - das sind alle Vielfachen von Primzahlquadraten. Bezeichnen wir mit

$\begin{align*} A_p \end{align*}$ ... Menge der Zahlen aus $\begin{align*} \left\{1,\ldots,100\right\} \end{align*}$ , die Vielfache von $\begin{align*} p^2 \end{align*}$ sind

dann suchen wir $\begin{align*} |A_2\cup A_3\cup A_5\cup A_7| \end{align*}$ , berechenbar per Siebformel. Nun ist

$\begin{align*} |A_p| = \left\lfloor \frac{100}{p^2}\right\rfloor \end{align*}$

$\begin{align*} |A_p\cap A_q| = \left\lfloor \frac{100}{p^2q^2}\right\rfloor \end{align*}$ für $\begin{align*} p\neq q \end{align*}$ usw.

21.02.2017, 10:56

MathematicalGates

Auf diesen Beitrag antworten »

Jop, hab auch an den Sieb des Erastothenes gedacht.

Die Lösung von Hal9000 gefällt mir auch, erscheint mir etwas eleganter.

21.02.2017, 11:09

HAL 9000

Auf diesen Beitrag antworten »

Na dann zähl mal schön durch, und nenn uns das Resultat. Augenzwinkern

------------------------------------------

Allgemein kann man die Anzahl $\begin{align*} q_n \end{align*}$ nicht quadratfreier Zahlen aus $\begin{align*} \{1,\ldots,n\} \end{align*}$ so bestimmen:

Sei $\begin{align*} P_n \end{align*}$ die Menge aller Primzahlen $\begin{align*} \leq\sqrt{n} \end{align*}$ . Dann ist

$\begin{align*} q_n = \sum_{\emptyset\neq I\subseteq P_n} (-1)^{|I|-1} \left\lfloor \frac{n}{\displaystyle \left(\prod I\right)^2} \right\rfloor \end{align*}$ ,

es wird dabei über alle nichtleeren Teilmengen $\begin{align*} I \end{align*}$ von $\begin{align*} P_n \end{align*}$ summiert. Symbolik $\begin{align*} \prod I \end{align*}$ ist vielleicht für den einen oder anderen unverständlich, das ist definitionsgemäß dasselbe wie $\begin{align*} \prod_{p\in I} p \end{align*}$ . Augenzwinkern

Selbstverständlich muss man nur die Teilmengen $\begin{align*} I \end{align*}$ betrachten, für die $\begin{align*} \prod I \leq \sqrt{n} \end{align*}$ gilt, denn für $\begin{align*} \prod I > \sqrt{n} \end{align*}$ trägt ja Summand $\begin{align*} \left\lfloor \frac{n}{\displaystyle \left(\prod I\right)^2} \right\rfloor = 0 \end{align*}$ nix zur Summe bei. Bei größeren $\begin{align*} n \end{align*}$ sowie "großen" $\begin{align*} |I| \end{align*}$ ist letzteres der Normalfall.

Für $\begin{align*} n\to \infty \end{align*}$ bedeutet das übrigens

$\begin{align*} 1-\frac{q_n}{n} \to \prod_{p\in P} \left(1-\frac{1}{p^2}\right) = \frac{1}{\zeta(2)} = \frac{6}{\pi^2} \end{align*}$ ,

dabei ist mit $\begin{align*} P \end{align*}$ die Menge aller Prinzahlen, und mit $\begin{align*} \zeta \end{align*}$ die Riemannsche Zetafunktion gemeint.

Neue Frage »

Antworten »

Anzahl quadratfreier Zahlen

Verwandte Themen