kgV der ersten n Zahlen abschätzen

25.06.2021, 20:53

ichbinneu

kgV der ersten n Zahlen abschätzen

Guten Abend,

ich möchte zeigen, dass für $\begin{eqnarray*} n\geq 7: kgV(1,2, ..., n) \geq 2^n \end{eqnarray*}$
Meine Idee ist, das mittels vollständiger Induktion zu zeigen.
Dabei dachte ich, wenn $\begin{eqnarray*} n+1 \end{eqnarray*}$ eine Primzahl ist, dann ist $\begin{eqnarray*} kgV(1,..., n+1) = (n+1)\cdot kgV(1,...,n) > 2\cdot kgv(1,..., n) \geq 2^{n+1} \end{eqnarray*}$ nach IA.

Aber was ist, wenn n+1 keine Primzahl ist.
Meine Idee dafür ist, dass ich n+1 dann darstelle in seiner Primfaktorzerlegung, also $\begin{eqnarray*} n + 1 = p_1^{\alpha_1} \cdot ... p_k^{\alpha_k} \end{eqnarray*}$ .
Aber wie komme ich damit nun vernünftig an das kgV? verwirrt

Vielen Dank an jeden Helfer!

27.06.2021, 20:31

IfindU

Auf diesen Beitrag antworten »

RE: kgV der ersten n Zahlen abschätzen
Ich denke mit Induktion wirst du hier keinen Beweis produzieren können.

Von $\begin{eqnarray*} n = 9 \to n = 10 \end{eqnarray*}$ bleibt der kgV gleich, d.h. $\begin{eqnarray*} kgV(1,2,\ldots, 9) = kgV(1,2,\ldots, 10) \end{eqnarray*}$ . Du wirst also nicht zeigen können, dass der kgV jedesmal wächst. Die Formel kann aber immer noch richtig sein, weil man sich in den Schritten davor genug "Puffer" angesammelt hat, um Stagnation zu kompensieren.

Andererseits denke ich Primzahlen sind zu "spärlich" verteilt, damit diese schon alleine genug Puffer herbeischaffen.

Meine einzige Idee wäre ich genug "Zahlen" $\begin{eqnarray*} q \leq n \end{eqnarray*}$ zu konstruieren, so dass der $\begin{eqnarray*} kgV \end{eqnarray*}$ von denen groß ist. D.h. $\begin{eqnarray*} q_2 = 2^{\alpha_2} \end{eqnarray*}$ und $\begin{eqnarray*} q_3 =3^{\alpha_3} \end{eqnarray*}$ mit $\begin{eqnarray*} \alpha \end{eqnarray*}$ maximal so dass $\begin{eqnarray*} q\leq n \end{eqnarray*}$ bleiben. Dann ist $\begin{eqnarray*} kgV(1,2,\ldots, n) \geq \prod_{q \leq n} q = 2^{\alpha_2} 3^{\alpha_3} \cdot ... p^{\alpha_p} \end{eqnarray*}$ , und das ist hoffentlich genügend groß ist. Ob das zielführend ist, kann ich dir nicht sagen.

Edit: Maximal ist $\begin{eqnarray*} \alpha_p =\left \lfloor \frac { \ln n }{ \ln p} \right \rfloor \geq \frac {\ln n} {\ln p} - 1 \end{eqnarray*}$ . Also $\begin{eqnarray*} p^{\alpha_p} \geq \frac 1 p n \end{eqnarray*}$ und damit $\begin{eqnarray*} kgV(1,2,\ldots, n) \geq \prod_{ p \leq n} q_p^{\alpha_p} \geq \prod_{ p \leq n} \frac n p = n^{\# \{p \leq n \}} \prod_{p \leq n} \frac 1 p \end{eqnarray*}$ .

Die einzige "echte" Abschätzung hier war die Abrundungsfunktion "etwas" zu verkleinern. Ggf. kann man hier aufsetzen.

28.06.2021, 13:13

HAL 9000

Auf diesen Beitrag antworten »

Rekursiv gilt für $\begin{eqnarray*} a_n = \operatorname{kgV}\left(1,\ldots,n\right) \end{eqnarray*}$ ja

$\begin{eqnarray*} a_n = \begin{cases} p\cdot a_{n-1} &\;\mbox{falls}\; n=p^k\\ a_{n-1} &\;\mbox{sonst}\end{cases} \end{eqnarray*}$

d.h., nur bei Primfaktorpotenzen $\begin{eqnarray*} n=p^k \end{eqnarray*}$ "wächst" $\begin{eqnarray*} a_n \end{eqnarray*}$ , ansonsten bleibt es gleich. Auf die Weise kann ein bloßer Induktionsschritt $\begin{eqnarray*} n-1\to n \end{eqnarray*}$ schwerlich klappen, da stimme ich mit IfindU überein.

Zum Beweis: Womöglich reicht es schon, wenn man $\begin{eqnarray*} \prod_{p\leq n} p \geq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ nachweisen könnte, mit passend gewähltem $\begin{eqnarray*} n_0 \end{eqnarray*}$ , die kleineren $\begin{eqnarray*} n \end{eqnarray*}$ dann per Einzelfallprüfung. Vielleicht kann da der Primzahlsatz $\begin{eqnarray*} \#\{p:\;p\leq n\}\sim \frac{n}{\ln(n)} \end{eqnarray*}$ irgendwie helfen. verwirrt

28.06.2021, 13:56

Huggy

Auf diesen Beitrag antworten »

Zitat:

Das scheint für $\begin{eqnarray*} n_0=29 \end{eqnarray*}$ zu stimmen.

30.06.2021, 16:03

ichbinneu

Auf diesen Beitrag antworten »

Hallo ihr Lieben,

vielen Dank für eure Antworten. Puh, das geht ja ganz schön weit.
Ich würde mich aber gerne weiter mit der Aufgabe beschäftigen und mich dann nochmal in diesem Thread zurückmelden smile

Vielen Dank nochmal!

30.06.2021, 16:49

ichbinneu

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Zum Beweis: Womöglich reicht es schon, wenn man $\begin{eqnarray*} \prod_{p\leq n} p \geq 2^n \end{eqnarray*}$ für $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ nachweisen könnte, mit passend gewähltem $\begin{eqnarray*} n_0 \end{eqnarray*}$ , die kleineren $\begin{eqnarray*} n \end{eqnarray*}$ dann per Einzelfallprüfung. Vielleicht kann da der Primzahlsatz $\begin{eqnarray*} \#\{p:\;p\leq n\}\sim \frac{n}{\ln(n)} \end{eqnarray*}$ irgendwie helfen. verwirrt

Wie ich sogerade gelernt habe nennt sich das >>Primorial<<.
Leider gibt es nur eine Abschätzung nach oben. Eine untere Schranke konnte ich bisher leider nicht funden unglücklich

30.06.2021, 16:53

ichbinneu

Auf diesen Beitrag antworten »

Entschuldigugn bitte für das Zugebombe. Ich sollte mich wohl doch mal anmelden.

Bei Wikipedia steht noch das hier:
[attach]53246[/attach]

Würde mir das nicht schon reichen?
Denn wenn das k-te Primorial genau 2^k Teiler hat, ist es ja auch mindestens 2^k groß.

Oder sehe ich das falsch?

30.06.2021, 16:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von ichbinneu
Wie ich sogerade gelernt habe nennt sich das >>Primorial<<.

Damit meinst du: Das Produkt $\begin{eqnarray*} \prod_{p\leq n} p \end{eqnarray*}$ nennt man so.

So seltsam wie du oben zitiert hast könnte man meinen, den Primzahlsatz nennt man Primorial - das hat mich schon ein wenig gewundert... Augenzwinkern

Zitat:

Original von ichbinneu
Denn wenn das k-te Primorial genau 2^k Teiler hat, ist es ja auch mindestens 2^k groß.

Verwechsle nicht $\begin{eqnarray*} k \end{eqnarray*}$ mit der Anzahl der Primzahlen $\begin{eqnarray*} \leq k \end{eqnarray*}$ .

30.06.2021, 17:06

ichbbinneu

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von ichbinneu
Denn wenn das k-te Primorial genau 2^k Teiler hat, ist es ja auch mindestens 2^k groß.

Verwechsle nicht $\begin{eqnarray*} k \end{eqnarray*}$ mit der Anzahl der Primzahlen $\begin{eqnarray*} \leq k \end{eqnarray*}$ .

Oh, achja

Also das k-te Primorial ist ja das Produkt aller Primzahlen bis einschließlich k.
Die Anzahl der Teiler ist damit also genau 2^pi(k), wobei pi(k) die Anzahl der Primzahlen bis einschließlich k bezeichnet.
Hm, wie könnte man die von dir genannte Ungleichung denn sonst mal zeigen? verwirrt

30.06.2021, 17:29

HAL 9000

Auf diesen Beitrag antworten »

Ich weiß es (noch) nicht - mir schwebt irgendwie sowas vor:

Sei $\begin{eqnarray*} 0<r<1 \end{eqnarray*}$ . Zwischen $\begin{eqnarray*} rn \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ gibt es gemäß Primzahlsatz ca. $\begin{eqnarray*} \frac{n}{\ln(n)} - \frac{rn}{\ln(rn)} \end{eqnarray*}$ Primzahlen, die alle $\begin{eqnarray*} \geq rn \end{eqnarray*}$ sind. Wenn man nun

$\begin{eqnarray*} \left(rn\right)^{\frac{n}{\ln(n)} - \frac{rn}{\ln(rn)}} > 2^n\qquad (*) \end{eqnarray*}$

für genügend große $\begin{eqnarray*} n \end{eqnarray*}$ beweisen könnte, wäre man durch. Logarithmiert man (*), bekommt man nach äquivalenter Umformung

$\begin{eqnarray*} \ln(rn)\cdot \left[ \frac{n}{\ln(n)} - \frac{rn}{\ln(rn)} \right] > n\ln(2) \end{eqnarray*}$

$\begin{eqnarray*} 1+\frac{\ln(r)}{\ln(n)} > r+\ln(2) \end{eqnarray*}$

Im Grenzwert $\begin{eqnarray*} n\to\infty \end{eqnarray*}$ strebt die linke Seite gegen 1, d.h., wenn man $\begin{eqnarray*} r < 1-\ln(2) \end{eqnarray*}$ wählt, ist diese Ungleichung tatsächlich für $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ mit einem passend gewählten $\begin{eqnarray*} n_0 \end{eqnarray*}$ erfüllt.

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

Das war jetzt erstmal heuristisch hingeworfen. Die Anzahl $\begin{eqnarray*} \frac{n}{\ln(n)} - \frac{rn}{\ln(rn)} \end{eqnarray*}$ gilt aber nur ungefähr, daher müsste ein "sauberer" Beweis an der Stelle mit einer belastbaren Abschätzung der genauen Anzahl nach unten arbeiten.

30.06.2021, 17:35

ichbinneu

Auf diesen Beitrag antworten »

Ich habe kein Wort verstanden da ich erst am Anfang meines Studiums stehe (mehr oder weniger), aber ich bin immer wieder fasziniert von deinen Beiträgen, auch in anderen Themen.
Ich fürchte also, dass geht über das was ich leisten könnte, viel zu weit hinaus. Falls dir aber noch eine Idee dazu kommt würde ich mich freuen, wenn du es mich wissen lässt smile

30.06.2021, 21:02

IfindU

Auf diesen Beitrag antworten »

RE: kgV der ersten n Zahlen abschätzen
Ich war neugierig, ob mein Ansatz (etwas verfeinert) funktioniert. Kuzfassung nein, man muss noch vorsichtiger sein.

Es ist $\begin{eqnarray*} kgV(1,2,\ldots,n) = \prod_{p \leq n} p^{\alpha_p} \end{eqnarray*}$ mit $\begin{eqnarray*} \alpha_q = \max \{ \alpha \in \mathbb N | q^{\alpha} \leq n \} \end{eqnarray*}$ . Für $\begin{eqnarray*} q \leq n \end{eqnarray*}$ ist $\begin{eqnarray*} \alpha_q = \lfloor\log_q n\rfloor \end{eqnarray*}$ . Insb. $\begin{eqnarray*} 1 \leq a_q \end{eqnarray*}$ sowie $\begin{eqnarray*} -1+\log_q n\leq \alpha_q \end{eqnarray*}$ .

Damit bekommt man insb. auch die Abschätzung
$\begin{eqnarray*} a_q \geq \begin{cases} \log_qn -1 &\text{ falls } q^2 \leq n \\ 1 & \text{ falls } q^2 > n\end{cases} \end{eqnarray*}$ .

Damit also $\begin{eqnarray*} \prod_{p \leq n, p^2 \leq n} p^{\alpha_p} \geq \prod_{p \leq n, p^2 \leq n} \frac n p \geq \prod_{p \leq n, p^2 \leq n} \sqrt n \end{eqnarray*}$ und $\begin{eqnarray*} \prod_{p \leq n, p^2 > n} p^{\alpha_p} \geq \prod_{p \leq n, p^2 > n} p \geq \prod_{p \leq n, p^2 > n} \sqrt n \end{eqnarray*}$

Damit also
$\begin{eqnarray*} kgV(1,2,\ldots,n) = \prod_{p \leq n} p^{\alpha_p} = \prod_{p \leq n, p^2 \leq n} p^{\alpha_p} \prod_{p \leq n, p^2 > n} p^{\alpha_p} \geq \prod_{p \leq n, p^2 \leq n} \sqrt n \prod_{p \leq n, p^2 > n} \sqrt n = \sqrt n^{\# \{ p | p \leq n \} } \end{eqnarray*}$

Mit $\begin{eqnarray*} {\# \{ p | p \leq n \} } \approx \frac n {\log n} \end{eqnarray*}$ dann $\begin{eqnarray*} kgV(1,2,\ldots,n) \geq \sqrt n^{\# \{ p | p \leq n \} } \approx e^{\frac n 2} \end{eqnarray*}$ . Hier sieht man dass es doch nicht gereicht hat, da $\begin{eqnarray*} 4 > e \end{eqnarray*}$ impliziert, dass $\begin{eqnarray*} 2^n > e^{\frac n 2} \end{eqnarray*}$ und damit die Abschätzung zu schwach ist. Durch die Nutzung der Verteilung von Primzahlen hata man hier auch wieder ein "Irgendwann gilt die Aussage/Abschätzung sogar" drin, was die ganze Sache unhübsch macht.

@ichbinneu: Mit HAL und Huggy hast du hier zwei Topkaliber des Forums. Selbst bei HALs bereits anspruchsvollen Lösung ist man noch nicht fertig. Auch wenn man die Rechnung von HAL sauber macht, hat man immer noch das Problem, dass es erst "irgendwann" gilt und man noch endlich, potentiell aber sehr viele Werte von $\begin{eqnarray*} n \end{eqnarray*}$ , per Einzelprüfung nachweisen muss.
Das scheint mir alles eine Nummer oder zwei zu hoch für einen Studienanfänger.

30.06.2021, 21:56

ichbinneu

Auf diesen Beitrag antworten »

Ich bin wahrhaft sprachlos. Es überrascht mich sehr, wieviel in dieser so unscheinbaren Aussage steckt, selbst für euch Profis. Andererseits ist das wahrscheinlich gerade das Wesen der Mathematik Big Laugh

Ich danke euch vielmals für eure Hilfe. Leider, wie IfindU (wen findest du eigentlich? ?) Augenzwinkern

) schon sagt, für mich zu hoch. Interessieren würde es mich trotzdem, aber ich glaube, soviele Fragen wie ich dann hätte, könnte ich hier nicht stellen Big Laugh

Einen Gedanken hätte ich noch, aber ich weiß nicht, wie ich ihn sauber formuliere. IfindU hat ja schon gesagt, dass man, wenn es "stagniert", man vorher schon genug Puffer angesammelt hat.
Nun, wenn es denn wächst, dann mindestens um das Doppelte, das sehe ich ein.
Dann bleibt doch die Frage, ob ich nicht abschätzen kann, wann es das nächste mal wächst oder anders gesagt (und mit HAL's rekuursiver Definiton): wann kommt wieder eine Primpotenz.
Ist das nicht die Frage, auf die das hinausläuft?

30.06.2021, 22:24

IfindU

Auf diesen Beitrag antworten »

Ich habe noch ein wenig gegooglet. Der kgV-Ausdruck ist die zweite Chebyshev Funktion, bzw. das Exponential der Funktion: Wikipedia.

D.h. das Problem hat sich darauf reduziert im Internet zu finden, warum $\begin{eqnarray*} \psi(n) \geq n \ln 2 \end{eqnarray*}$ ist. Big Laugh

Edit: Gem. dem Prime number Theorem ist $\begin{eqnarray*} \frac {\psi(n)} n \to 1 > \ln 2 \end{eqnarray*}$ und damit folgt die Aussage für groß-genügende $\begin{eqnarray*} n \end{eqnarray*}$ .

01.07.2021, 08:49

HAL 9000

Auf diesen Beitrag antworten »

Ja, das ist das Problem: Man kriegt (auf verschiedenen) Wegen einen Beweis hin, der für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ gilt, bisweilen aber für sehr große $\begin{eqnarray*} n_0 \end{eqnarray*}$ . Es ist sogar schon ein Fortschritt, wenn man überhaupt ein konkretes (und auch noch erträglich großes) $\begin{eqnarray*} n_0 \end{eqnarray*}$ benennen kann, so dass man die kleineren $\begin{eqnarray*} n \end{eqnarray*}$ per Brute Force erledigen kann. Augenzwinkern

Neue Frage »

Antworten »

kgV der ersten n Zahlen abschätzen

Verwandte Themen