Abstruser Zusammenhang < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:39 So 10.09.2006 | | Autor: | Brinki |
| Aufgabe | Für jedes x setze man
[mm]p(x) = \mbox{ kleinste Primzahl, die x nicht teilt,}[/mm]
[mm]
q(x) = \begin{cases}\mbox{ Produkt aller Primzahlen, die kleiner als } p(x)\mbox{ sind}, & \mbox{für } p(x)>2 \\ 1, & \mbox{für } p(x)=2 \end{cases}[/mm]
Man betrachte die auf folgende Weise definierte Folge:
[mm] x_0=1, \mbox{ } x_{n+1}=\bruch{x_n*p(x_n)}{q(x_n)} [/mm] |
Die eigentliche Aufgabenstellung lautete:
[mm] \mbox{Finde alle }[/mm] [mm]n\ge0[/mm] [mm] \mbox{ mit }[/mm] [mm]x_n=1995[/mm].
Ordnet man alle Primzahlen der Größe nach , so ist [mm]P_0=2; P_1=3; P_2=5; P_4=7; ... P_7=19; ...[/mm]
Stellt man das Folgenglied [mm] x_n [/mm] in seiner Primfaktorzerlegung dar, so ergiebt sich (für mich) ein unerklärlicher Zusamenhang zur Darstellung der Indexnummer [mm]n[/mm] im Zweiersystem.
Scheinbar gilt:
[mm] \mbox{Wenn } x_n = P_a*P_b*P_c* ... P_i \gdw n=2^a+2^b+2^c+ ... 2^i[/mm]
Wie man leicht nachrechnet stimmt dies auch, denn
[mm] \mbox{Für}[/mm] [mm]x_n=1995=3 * 5*7*19=P_1*P_2*P_3*P_7 [/mm] [mm] \mbox{ erhält man }[/mm] [mm]n=2^1+2^2+2^3+2^7=142.[/mm]
In der Anlage ![[a]](/images/paperclip.gif "Dateianhänge") Anlage findet ihr die Rechnungen bis n=12.
Warum stimmt dies immer? Gibt es hierfür einen Beweis diesen Zusammenhang zwischen Primfaktorzerlegung des Folgengliedes und der Dualdarstellung der Folgennummer?
Für eure Hilfe vielen Dank im voraus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Grüße
Brinki
Dateianhänge:
Anhang Nr. 1 (Typ: JPG) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:50 So 10.09.2006 | | Autor: | ullim |
Hallo Brinki,
ja, Deine Vermutung bzgl. des Zusammenhangs zwischen Primfaktorzerlegung des Folgengliedes und der Dualdarstellung der Folgennummer stimmt.
Man kann es mit vollständiger Induktion beweisen.
Induktionsanfang mit n = 1.
Hier gilt
n = [mm] 2^{0}
[/mm]
[mm] x_{1} [/mm] = [mm] \bruch{2}{1} [/mm] = 2
und [mm] p_{0} [/mm] = 2.
Also ist der Induktionsanfang in Ordnung.
Jetzt kommt der Schritt von n auf n+1
Hier wird die Fallunterscheidung n = Gerade und n = Ungerade gemacht.
1. n = Gerade
Wenn n = Gerade ist, bedeutet das, das in der Sume für n der Summand [mm] 2^{0} [/mm] nicht vorkommt aber als Summand von n+1.
Zu beweisen ist also, das [mm] p_{0} [/mm] = 2 als Faktor von [mm] x_{n+1} [/mm] vorkommt.
Entsprechend der Induktionsvoraussetzung kommt [mm] p_{0} [/mm] = 2 nicht als Faktor in [mm] x_{n} [/mm] vor. D.h. aber, das [mm] p(x_{n}) [/mm] = 2 und [mm] q(x_{n}) [/mm] = 1 gilt. [mm] \Rightarrow
[/mm]
[mm] x_{n+1} [/mm] = [mm] 2x_{n}
[/mm]
womit für Gerade n der Beweis erbracht währe.
1. n = Ungerade
Da ich jetzt keine Zeit mehr habe, liefere ich diesen Beweis etwas später. Vielleicht reichts ja auch so schon.
Und jetzt gehts weiter:
n besitzt eine Darstellung mit einem k [mm] \ge [/mm] 1
n = [mm] \summe_{i=0}^{k-1}2^{i}+2^{k}\alpha \Rightarrow
[/mm]
n + 1 = 1 + [mm] \summe_{i=0}^{k-1}2^{i} [/mm] + [mm] 2^{k}\alpha \Rightarrow
[/mm]
n + 1 = [mm] 2^{k}(1+\alpha)
[/mm]
D.h. es ist zu beweisen, dass [mm] p_{k} [/mm] Faktor von [mm] x_{n+1} [/mm] ist.
[mm] x_{n+1} [/mm] = [mm] x_{n} \bruch{p(x_{n})}{q(x_{n})}
[/mm]
[mm] x_{n} [/mm] = [mm] R\produkt_{i=1}^{k-1}p_{i}
[/mm]
[mm] p(x_{n}) [/mm] = [mm] p_{k}
[/mm]
[mm] q(x_{n}) [/mm] = [mm] \produkt_{i=1}^{k-1}p_{i} \Rightarrow
[/mm]
[mm] x_{n+1} [/mm] = [mm] R*p_{k}
[/mm]
also ist [mm] p_{k} [/mm] Faktor von [mm] x_{n+1} [/mm] und der Beweis ist erbracht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:30 So 10.09.2006 | | Autor: | Brinki |
Vielen Dank und Gratulation für die schöne Lösung.
Hätte nicht gedacht, dass das so leicht mit Induktion zu machen ist.
Grüße
Brinki
|
|
|
|
![[a]](uploads/forum/00176755/forum-i00176755-n001.JPG "Dateianhänge"){kind=small}
Anlage