|
Autor |
Aufgabe 2 |
|
Martin_Infinite
Senior  Dabei seit: 15.12.2002 Mitteilungen: 39133
Wohnort: Münster
 | Themenstart: 2013-11-10
|
$\textbf{Aufgabe 2.}$ (2 Punkte) Die Zahlenfolge $a$ sei rekursiv wie folgt definiert: Es ist $a(n)$ die kleinste natürliche Zahl, die nicht von der Form $a(m)$ für eine zu $n$ teilerfremde Zahl $m
|
Profil
|
Calculus
Senior  Dabei seit: 10.08.2012 Mitteilungen: 6086
 | Beitrag No.1, eingetragen 2013-11-10
|
Soll auch die Zahlenfolge bei 0 anfangen? Gilt also a(1) = 0 oder a(1) = 1?
|
Profil
|
Zetavonzwei
Senior  Dabei seit: 07.03.2012 Mitteilungen: 634
Wohnort: Bamberg, Deutschland
 | Beitrag No.2, eingetragen 2013-11-10
|
Ich schätze, es ist a(0)=0 und dementsprechend a(1)=1, da 0 und 1 teilerfremd sind (Die natürlichen Zahlen fangen ja hier bei 0 an, also insbesondere auch die Indizes)
Gruß
Zvz
|
Profil
|
Martin_Infinite
Senior  Dabei seit: 15.12.2002 Mitteilungen: 39133
Wohnort: Münster
 | Beitrag No.3, vom Themenstarter, eingetragen 2013-11-10
|
Um solche Nachfragen zu vermeiden, habe ich extra bei "Allgemeines" noch einmal $\mathds{N} = \{0,1,2,\dotsc\}$ wiederholt ;-)
Ja, es gilt $a(0)=0$ und $a(1)=1$.
|
Profil
|
chryso
Senior  Dabei seit: 07.02.2009 Mitteilungen: 10529
Wohnort: Österreich
 | Beitrag No.4, eingetragen 2013-11-11
|
Da ich bei Untersuchungen zur Teilerfremdheit mich nicht erinnern kann, eine Null dabei gehabt zu haben, zwei Fragen zur Definition:
1) Sind zwei natürliche Zahlen a und b genau dann teilerfremd, wenn gilt ggT(a,b)=1 ?
2) Wenn a>1, gilt wahrscheinlich: a und 0 sind nicht teilerfremd. ?
=> Null ist nur zu 1 teilerfremd ?
LG chryso
|
Profil
|
Gockel
Senior  Dabei seit: 22.12.2003 Mitteilungen: 25548
Wohnort: Jena
 | Beitrag No.5, eingetragen 2013-11-11
|
Ja, beides ist korrekt. Es gilt ganz allgemein ggT(0,m)=m.
mfg Gockel.
|
Profil
|
Calculus
Senior  Dabei seit: 10.08.2012 Mitteilungen: 6086
 | Beitrag No.6, eingetragen 2013-11-12
|
Sei pi die [versetzte] Folge der Primzahlen, d.h. p1 = 2, p2 = 3 etc.. Für n > 0 gelten dann folgende Gleichungen:
a(2n) = 0
a(2n + 1) = min{i | pi | (2n + 1)}
Den Beweis kann man schnell mit Induktion führen, er ist nur wegen der Fallunterscheidung etwas umständlich. Deswegen habe ich in #1 auch nochmal nachgefragt; Wäre a(1) = 0, dann wäre a(n) = min{i | pi | n} für alle n > 1.
|
Profil
|
weird
Senior  Dabei seit: 16.10.2009 Mitteilungen: 5301
 | Beitrag No.7, eingetragen 2013-11-12
|
Ok, auch für diese Aufgabe ein Lösungsvorschlag meinerseits. Ich behaupte zunächst, dass die Folge a(n) genau für gerade Werte von n den Wert 0 liefert, den Wert 1 genau für n=1 annimmt und schließlich einen Wert k>1 genau dann, wenn n>1 ungerade ist und der kleinste Primfaktor p von n in der (aufsteigenden) Folge aller Primzahlen $p_1,p_2,p_3,...$ genau an der k-ten Position auftaucht, d.h., $p=p_k$ ist. Der Beweis geht natürlich mit Induktion.
Zunächst wurde ja schon gesagt, dass a(0)=0 und a(1)=1 ist. Für ein gerades n>0 sind dann alle m1, für welches $p=p_k$ der kleinste Primfaktor ist, kommen unter den zu n teilerfremden m[Die Antwort wurde nach Beitrag No.5 begonnen.]
|
Profil
|
Gockel
Senior  Dabei seit: 22.12.2003 Mitteilungen: 25548
Wohnort: Jena
 | Beitrag No.8, eingetragen 2013-11-12
|
Ja, der Beweis geht mit Induktion. Ich hab da mal etwas vorbereitet ;-)
Es sei $p_s$ die $s$-te Primzahl, d.h. $p_0=2, p_1=3, ...$.
Satz: Es gilt
$a(0)=0$, $a(1)=1$, $a(2)=0$,
$a(p_s)=s+1$ für $s>0$
$a(m) = \min\{a(p) : p|m\}$ für $m\geq 2$.
Beweis:
Die Definition schreibt sich als
$a(m) := \min \mathbb{N}\setminus\{a(n) : n1$ ist jedoch $ggT(0,m)=m\neq 1$, sodass $a(2)=\min \mathbb{N}\setminus\{a(1)\}=0$ gilt.
Wir nehmen nun an, dass die Behauptung des Satzes für alle $n0$ und $a(p)>0$ für alle ungeraden Primzahlen kleiner $m$ nach Induktionsvoraussetzung gilt. Also $a(m)=0$ und die Behauptung stimmt.
Wenn $m$ hingegen ungerade ist, dann ist $a(2)=0$ in dieser Menge, ebenso wie $a(1)=1$. Nach Voraussetzung sind alle Primzahlen $p_s$ mit $sKorollar:
$a(5^{2013})=a(5) = 3$.
mfg Gockel.
|
Profil
|
Zetavonzwei
Senior  Dabei seit: 07.03.2012 Mitteilungen: 634
Wohnort: Bamberg, Deutschland
 | Beitrag No.9, eingetragen 2013-11-12
|
Kleine Korrektur: a(0)=0, a(1)=1, a(2)=2, a(3)=3 und entsprechend a(5)=4.
Gruß Zvz
|
Profil
|
Gockel
Senior  Dabei seit: 22.12.2003 Mitteilungen: 25548
Wohnort: Jena
 | Beitrag No.10, eingetragen 2013-11-12
|
Nein, a(2)=0. Beachte, dass 0 nicht teilerfremd zu 2 ist. Die einzige Zahl, die kleiner als 2 und teilerfremd zu 2 ist, ist 1.
mfg Gockel.
|
Profil
|
chryso
Senior  Dabei seit: 07.02.2009 Mitteilungen: 10529
Wohnort: Österreich
 | Beitrag No.11, eingetragen 2013-11-12
|
Ich gebe Gockel vollkommen recht. Mein Ergebnis ist gleich wie seines. Ich komme leider erst heute dazu, mich hier einzubringen, da ich drei Tage wo anders war.
1) Auch ich hatte das Ergebnis, dass für alle geraden Zahlen k der Wert von a(k)=0 ist.
Den Beweis dafür haben etliche schon gebracht.
2) ggT(m,1)=1, deshalb kann a(m) nicht =a(1)=1 sein, wenn m>1.
3) a(2)=0
Wenn p>2 eine Primzahl ist, dann gilt
ggT(p,2)=1 => a(p) ungleich 0 und ungleich 1
Sei q eine Primzahl < p => a(q) a(x)ungleich a(q) =>
a(x) ungleich a(z), wobei z eine Primzahl 2 die n-te Primzahl ist.
a(3)=2, a(5)=3, a(7)=4, a(11)=5 a(13)=6 ...
6) a(pk) =a(p) (Folgt aus 5) ).
=> Ergebnis von Gockel: a(52013)=3
Meine Überlegungen sind leider nicht mathematisch exakt aufgeschrieben und eigentlich haben das alles Calculus, weird und Gockel schon gesagt. Ich wollte sie aber dennoch hier veröffentlichen, denn ich komme leider erst heute dazu, das auf einem Schmierzettel Geschriebene hier einzutippen.
LG chryso
|
Profil
|
Zetavonzwei
Senior  Dabei seit: 07.03.2012 Mitteilungen: 634
Wohnort: Bamberg, Deutschland
 | Beitrag No.12, eingetragen 2013-11-12
|
oh, ja, ich hatte vergessen, dass 2 teilerfremd zu 0 ist...
Gruß
Zvz
|
Profil
|
weird
Senior  Dabei seit: 16.10.2009 Mitteilungen: 5301
 | Beitrag No.13, eingetragen 2013-11-13
|
\quoteon(2013-11-12 22:57 - Zetavonzwei in Beitrag No. 12)
oh, ja, ich hatte vergessen, dass 2 teilerfremd zu 0 ist...
\quoteoff
Das kannst du auch guten Gewissens vergessen, da es nicht stimmt. :-D
|
Profil
|
Zetavonzwei
Senior  Dabei seit: 07.03.2012 Mitteilungen: 634
Wohnort: Bamberg, Deutschland
 | Beitrag No.14, eingetragen 2013-11-14
|
ohje... Zweimal Unsinn. Ich sollte aufhören, nicht genau hinzusehen.
Gruß
Zvz
|
Profil
|
Martin_Infinite
Senior  Dabei seit: 15.12.2002 Mitteilungen: 39133
Wohnort: Münster
 | Beitrag No.15, vom Themenstarter, eingetragen 2013-11-24
|
2 Punkte fürs Team.
Auflösung.
Behauptung: Wenn $n$ gerade ist, gilt $a(n)=0$. Es gilt $a(1)=1$. Wenn $n>1$ ungerade und $p_k$ der kleinste Primteiler von $n$ ist, so gilt $a(n) = k$.
Beweis: Sei $M_n=\{a_m : m$a(n)=\mathrm{mex}(M_n)$. Offenbar ist $a(0)=0,a(1)=1,a(2)=0$. Wir zeigen zunächst per Induktion nach $n$, dass $a(n)=0$ für gerade $n$ und $a(n)>0$ für ungerade $n$: Wenn $n$ ungerade ist, ist $0=a(n-1) \in M_n$ und daher $a(n) > 0$. Wenn $n$ gerade ist, gilt für alle $m0$. Es folgt $a(n)=0$.
Nun sei $n>1$ ungerade und $p_k$ der kleinste Primteiler von $n$. Wir zeigen per Induktion nach $n$, dass $a(n)=k$. Für $m1$ würde $a(m)=k$ bedeuten, dass $p_k$ ein gemeinsamer Teiler von $m,n$ ist. Für jedes $2 \leq i < k$ ist $p_iBemerkungen. Es handelt sich bei $a(n)$ um die Sprague-Grundy-Funktion des folgenden kombinatorischen Spiels, welches ich mir ausgedacht habe: Man hat einen Stapel von $n$ Spielsteinen. Zwei Spieler heben abwechselnd Steine ab (mindestens aber einen), deren Anzahl zu $n$ teilerfremd ist. Derjenige, der nicht mehr ziehen kann, hat verloren. Die Äquivalenz zwischen $a(n)>0$ und $n$ ungerade besagt gerade, dass der erste Spieler mit einem Stapel von $n$ Steinen genau dann gewinnen kann, wenn $n$ ungerade ist (der Gewinnzug hebt einfach genau einen Stein ab). Das ist zwar einfach einzusehen, aber die Sprague-Grundy-Funktion braucht man, um das Spiel auch dann zu entscheiden, wenn man mit mehreren Stapeln gleichzeitig spielt. Wenn man etwa zwei Stapel hat, mit Sprague-Grundy-Funktionen $a,b$, so gewinnt der erste Spieler Stapeln mit $n$ bzw. $m$ Steinen genau dann, wenn die Nim-Summe $a(n) \oplus b(m) > 0$ erfüllt.
|
Profil
|
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen. Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|