Matroids Matheplanet Forum Index
Moderiert von Martin_Infinite reneeeee
Matroids Matheplanet Forum Index » 9. Matheplanet Challenge » Aufgabe 2
MPC9-Navigation: Allg P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 Regeln
Autor
Universität/Hochschule Aufgabe 2
Martin_Infinite
Senior Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: im letzten Monat
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: im letzten Monat
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: im letzten Monat
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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 Letzter Besuch: vor mehr als 3 Monaten
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
Martin_Infinite hat die Antworten auf ihre/seine Frage gesehen.
 MPC9-Navigation: Allg P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 Regeln

Wechsel in ein anderes Forum:
 Suchen    
 
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]