Zahlenbäume < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo ihr Zahlenfreaks,
damit ihr die Hintergründe dieses Threads ver-
steht, solltet ihr zunächst einmal da vorbei-
schauen:
1.) Integrierbarkeit: https://matheraum.de/read?i=534182
2.) Grafiken: https://matheraum.de/read?i=534299
3.) Zahlenbaum: https://matheraum.de/read?t=534844
Über die verschiedenen Binärbäume, deren Knoten
rationalen Zahlen entsprechen, könnt ihr euch
z.B. da informieren:
1.) Stern-Brocot-Baum("S-B-Baum"):
http://de.wikipedia.org/wiki/Stern-Brocot-Baum
2.) Calkin-Wilf-Baum ("C-W-Baum"):
http://www.mathlesstraveled.com/custom/images/cw-small.png
(es gäbe auch bessere Quellen ...)
Mir scheint es nun, eine interessante Beziehung
zwischen dem S-B-Baum und dem C-W-Baum entdeckt
zu haben. Zwar habe ich Schriften gesehen, die
sich auch mit dem Zusammenhang der verschiedenen
Binärbäume rationaler Zahlen befassen, aber die
folgende interessante Beobachtung scheint mir
neu:
Die Position einer (gekürzten, positiven) ratio-
nalen Zahl [mm] \bruch{z}{n} [/mm] in einem solchen S-B- oder C-W-Baum
lässt sich eindeutig charakterisieren durch eine
Folge von Nullen und Einsen, die jeweils angeben,
ob man sich im Binärbaum nach links unten oder
nach rechts unten bewegt. Die Folge dieser Nullen
und Einsen, zu einer Binärzahl aneinandergefügt,
ergibt den S-B-Code bzw. den C-W-Code des Bruches $\ z/n$.
Nun sind im S-B-Baum und im C-W-Baum - welche
beide an der Spitze (bzw. "Wurzel") den Bruch $\ 1/1$
haben, die Zahlen aber durchaus recht unterschied-
lich angeordnet.
Zwar findet man auf einer Stufe (neudeutsch auf
einem bestimmten Level) in beiden Bäumen ins-
gesamt exakt dieselben Brüche vor, aber je nach
Level wieder in einer ganz anderen Anordnung).
"Verwandtschaftsbeziehungen" wie "Elternschaft"
werden dabei keineswegs generell respektiert.
Der S-B-Code und der C-W-Code einer gegebenen
gekürzten rationalen Zahl können sich deshalb
also erheblich voneinander unterscheiden.
Und nun kommt aber die grosse Überraschung:
Zeichnet euch mal auf zwei grossen Blättern je
einen S-B-Baum und einen C-W-Baum auf. Be-
rechnet (nach den Formeln, die ihr dafür findet,
oder mit selbstgebauten Formeln) einige Gene-
rationen von Brüchen und schreibt auch deren
S-B- oder C-W-Codes auf den beiden Blättern an.
Insgesamt könnte das ein gewisses Durcheinander
verursachen. Es heisst also vorsichtig zu arbeiten.
Vergleicht dann für viele verschiedene Brüche,
also etwa
[mm] $\bruch{1}{3}\ [/mm] ,\ [mm] \bruch{3}{5}\ [/mm] ,\ [mm] \bruch{3}{2}\ [/mm] ,\ [mm] \bruch{5}{2}\ [/mm] ,\ [mm] \bruch{5}{7}\ [/mm] ,\ [mm] \bruch{8}{3}\ [/mm] ,\ [mm] \bruch{8}{11}\,\ [/mm] ,\ ...\ \ etc. $
den jeweiligen S-B-Code mit dem C-W-Code.
Dann werdet ihr dieselbe erstaunliche Entdeckung
machen, die mich heute (ach ja, es war halt schon
wieder gestern) beinahe vom Hocker in eine plane-
tare Umlaufbahn katapultiert hätte ... Für mich fühlte
es sich jedenfalls an wie ein Stück Zauberei - bei
Harry Potter findet man kaum Besseres !
LG Al-Chwarizmi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:27 Di 14.04.2009 | | Autor: | felixf |
Hallo Al,
> Dann werdet ihr dieselbe erstaunliche Entdeckung
> machen, die mich heute (ach ja, es war halt schon
> wieder gestern) beinahe vom Hocker in eine plane-
> tare Umlaufbahn katapultiert hätte ...
Meinst du, dass der S-B-Code gerade der C-W-Code rueckwaerts ist? Das ist in der Tat recht interessant. Ist das bisher nur eine Vermutung oder hast du einen Beweis dafuer?
Eventuell koennte man hier auch etwas mit Kettenbruechen machen, allerdings bin ich gerade zu faul die Details zwischen C-W-Baeumen und Kettenbruechen herauszusuchen. Also falls jemand langeweile hat... 
LG Felix
|
|
|
| |
|
> Hallo Al,
>
> > Dann werdet ihr dieselbe erstaunliche Entdeckung
> > machen, die mich heute (ach ja, es war halt schon
> > wieder gestern) beinahe vom Hocker in eine plane-
> > tare Umlaufbahn katapultiert hätte ...
>
> Meinst du, dass der S-B-Code gerade der C-W-Code
> rueckwaerts ist? Das ist in der Tat recht interessant.
Genau so scheint es zu sein - und das hat mich wirklich
vom Hocker gehauen.
> Ist das bisher nur eine Vermutung oder hast du einen
> Beweis dafuer?
Wenn du willst, "erst" eine Vermutung - allerdings eine
von der Sorte, die sich nachher irgendwann als wahr
herausstellen. Es kann kein Zufall sein, dass sie
bisher bei allen ausprobierten Beispielen mit aufs Gerate-
wohl hingeschriebenen bis zu zehnstelligen Zählern
und Nennern (die Brüche werden im Programm zuerst,
falls nötig, mittels euklidischem Algorithmus gekürzt)
bestätigt wurde.
LG Al
|
|
|
| |
|
Liebe Zahlenfreunde,
nachdem ich mich von der Überraschung einer unerwar-
teten Entdeckung etwas erholt habe, bin ich nun dran
gegangen, einen Beweis für die Vermutung zu suchen,
dass der SB-Code und der CW-Code eines beliebigen
Bruches [mm] $\bruch{z}{n}\ (\,n\,,z\in \IN$ [/mm] , teilerfremd ) spiegelbildlich
zueinander sind. Und da sieht es doch jetzt ganz gut aus.
Durch eine Methode der simultanen Reduktion wird die
eigenartige Verquickung der beiden Bäume, also SB-Baum
und CW-Baum, durchschaubar.
Betrachten wir dazu ein einfaches Beispiel, etwa mit
dem Bruch [mm] $\bruch{z}{n}\ [/mm] =\ [mm] \bruch{11}{7}$ [/mm] . Pfad und Code zu diesem Bruch ist
im SB-Baum:
[mm] \bruch{1}{1}\to\bruch{2}{1}\to\bruch{3}{2}\to\bruch{5}{3}\to\bruch{8}{5}\to\bruch{11}{7} [/mm] 10100
und im CW-Baum:
[mm] \bruch{1}{1}\to\bruch{1}{2}\to\bruch{1}{3}\to\bruch{4}{3}\to\bruch{4}{7}\to\bruch{11}{7} [/mm] 00101
Da z>n ist, ist das hinterste Element des CW-Codes eine
Eins, und nach der CW-Reduktionsregel wird der Vorgänger
von [mm] \bruch{z}{n} [/mm] in diesem Fall (eben z>n) berechnet als [mm] \bruch{z-n}{n} [/mm] .
So kommt der zweitunterste Bruch [mm] \bruch{4}{7} [/mm] im CW-Pfad zustande.
Wegen z>n und damit [mm] \bruch{z}{n}>1 [/mm] ist auch offensichtlich,
dass im SB-Baum die Zahl [mm] \bruch{z}{n} [/mm] rechts von der Eins,
also in der rechten Baumhälfte sein muss. Dies bedeutet,
dass das erste Element im SB-Code ebenfalls eine Eins
sein muss, nämlich gleich dem letzten Element des
CW-Codes. Im umgekehrten Fall, also z<n, wären diese
beiden Bits gleich Null und der Vorgänger (im CW-Baum)
würde als [mm] \bruch{z}{n-z} [/mm] berechnet.
Nun kommt der erste Reduktionsschritt. Der CW-Baum
wird einfach knapp über dem Knoten [mm] \bruch{11}{7} [/mm] horizontal
abrasiert (unterer Teil entfernt) und vom CW-Code das
letzte Bit gestrichen. Im Prinzip kann man diesen Baum
noch viel radikaler beschneiden: Was von ihm noch in-
teressiert, ist einzig derjenige Pfad, der zum betrachteten
Knoten [mm] \bruch{11}{7} [/mm] bzw. neu [mm] \bruch{4}{7} [/mm] führt. Alles andere kann
weggeschnitten werden.
Beim SB-Baum ist es etwas komplizierter, denn hier
müssen wir quasi an der Wurzel schneiden. Dem Baum
wird radikal die ganze linke Hälfte weggeschnitten
(denn Zahlen kleiner oder gleich Eins kommen wegen z>n
gar nicht mehr in Frage. Was übrigbleibt, ist der rechte
Halbbaum, an dessen Spitze der Bruch [mm] \bruch{2}{1} [/mm] steht.
Nun ist aber dieser "halbe" Baum topologisch isomorph
zum ursprünglichen "ganzen" Baum. Wenn wir die
entsprechende (ordnungserhaltende !) Isomorphie-
Abbildung durchführen, welche den Bruch [mm] \bruch{2}{1} [/mm] auf [mm] \bruch{1}{1} [/mm]
abbildet, müssen wir nur die an den Knoten sitzenden
Brüche umbenennen. Der Bruch [mm] \bruch{2}{1} [/mm] rückt an die Spitze
und wird zur neuen Eins $\ [mm] (\,=\, \bruch{1}{1}\,)$ [/mm] des Baumes.
Nun schauen wir, was bei dieser Abbildung (ich
würde sie z.B. "Chwarizmi-Shift" nennen - ein bisschen
Eitelkeit darf doch auch sein ) aus dem
ursprünglichen Pfad wird, dem jetzt sein vorher erstes
Stück fehlt und der neu bei Eins beginnt. Wenn man
die Zeichnung des SB-Baumes vor sich hat, wird klar:
Zum verbleibenden Code-Rest 0100 gehört im
neuen "ganzen" SB-Baum der Pfad
[mm] \bruch{1}{1}\to \bruch{1}{2}\to \bruch{2}{3}\to \bruch{3}{5}\to \blue{\bruch{4}{7}}
[/mm]
Und siehe da, das letzte Element in diesem Pfad ist
genau die Zahl [mm] \blue{\bruch{4}{7}} [/mm] , die auch im
"gestutzten" CW-Pfad
[mm] \bruch{1}{1}\to \bruch{1}{2}\to \bruch{1}{3}\to \bruch{4}{3}\to \blue{\bruch{4}{7}}
[/mm]
an letzter Stelle steht. Diese doch noch etwas rätselhaft
erscheinende Eigenschaft wäre nun durch vollstän-
dige Induktion zu beweisen, indem man die genauen
rechnerischen Regeln benützt, nach welchen die
beiden Bäume aufgebaut sind. Durch die schrittweise
simultane Reduktion beider Pfade kommt man am
Schluss sowohl bei SB als auch bei CW beim "trivialen"
Baum an, der nur noch aus dem einen Knoten [mm] \bruch{1}{1}
[/mm]
besteht. Darin besteht die "Verankerung" oder hier
besser "Verwurzelung" des Beweises. Dass durch die
schrittweise Identifikation "letztes Bit des Rest-CW-Codes =
erstes Bit des Rest-SB-Codes" schliesslich die Behauptung
"CW-Code = Spiegelbild(SB-Code)" hervorgeht, ist
wohl klar.
Durch die "Brücke", die zwischen den beiden Bäumen
besteht, wird es möglich, die Vorteile beider Bäume
synergetisch zu nutzen: die wichtige Eigenschaft des
Stern-Brocot-Baumes, dass er die natürliche Ordnung
der rationalen Zahlen beibehält und die rechnerischen
Vorzüge des CW-Baumes (Calkin und Wilf haben ihre
Arbeit übrigens erst im Jahr 1999 verfasst und im Jahr
2000 öffentlich publiziert), bei dem es sehr leicht ist,
von einem Knoten aus abwärts und aufwärts zu rechnen.
Auch über den Zusammenhang SB-CW habe ich im Netz
schon etwas gefunden. Gesehen - aber noch nicht im
Detail studiert - habe ich eine (undatierte) Schrift
![[]](/images/popup.gif) "Functional Pearl"
von Gibbons/Lester/Bird sowie die 2008 veröffentlichte Arbeit
"Recounting the Rationals: Twice !"
von Backhouse/Ferreira.
Bei meinen Überlegungen habe ich mich eigentlich
nur auf das einfache "Rezept" zur Berechnung des
CW-Baumes gestützt, wie ich es in dem kurzen Paper
"Recounting the Rationals" von Calkin/Wilf gefunden habe:
> The tree of fractions
> For the moment, lets forget about enumeration, and
> just imagine that fractions grow on the tree that is
> completely described, inductively, by the following
> two rules:
> 1.) [mm] \bruch{1}{1} [/mm] is at the top of the tree, and
> 2.) Each vertex [mm] \bruch{i}{j} [/mm] has two children:
> its left child is [mm] \bruch{i}{i+j} [/mm] and its right child is [mm] \bruch{i+j}{j}
[/mm]
Diese einfache Regel lässt sich leicht umkehren,
um zu jedem Knoten $\ [mm] (\,\not= \bruch{1}{1}\,)$ [/mm] seinen eindeutig
bestimmten Vorgänger zu berechnen.
Die Rechenregeln für den SB-Baum habe ich mir
selber erarbeitet, vor wenigen Tagen, als ich noch
keine Ahnung hatte, dass es so etwas wie einen
"Arbre de Stern-Brocot" oder einen "Calkin-Wilf-Tree"
überhaupt gibt. Im SB-Baum brauche ich aber zum
Starten jeweils einen Knoten und seinen Vorgänger,
um die beiden "Kinder" zu berechnen. Das Weiter-
rechnen nach unten ist dann nicht schwer, die
Berechnung des Ahnen-Baums jedoch schon - aber
das lässt sich nun dank der "Brücke" zum CW-Baum
doch recht leicht schaffen !
Beim Schnuppern in den Arbeiten zu diesem Thema
habe ich festgestellt, dass es manchen Autoren offen-
bar insbesondere um effiziente Algorithmen für eine
Aufzählung der rationalen Zahlen geht. Wozu dies
genau dienen soll, ist mir nicht unmittelbar einsichtig.
Nach meinen ersten eigenen Versuchen in dieser
Materie in den letzten paar Tagen denke ich jedoch,
dass sich in diesem Bereich vielleicht noch ganz andere
zahlentheoretische Erkenntnisse ergeben könnten,
wenn man nur seine Scheuklappen etwas lockert !
LG Al-Chwarizmi 14.4.2009
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:39 Mi 15.04.2009 | | Autor: | felixf |
Hallo Al,
ich hab noch ein wenig gesucht und folgendes gefunden: den Artikel Enumerating the Rationals.
Im Abschnitt 4 wird (insb. siehe zweiter Absatz) genau die von dir entdecke Eigenschaft genannt. Dabei wird auch auf zwei Quellen verwiesen.
LG Felix
|
|
|
| |
|
> Hallo Al,
>
> ich hab noch ein wenig gesucht und folgendes gefunden: den
> Artikel
> Enumerating the Rationals.
>
> Im Abschnitt 4 wird (insb. siehe zweiter Absatz) genau die
> von dir entdecke Eigenschaft genannt. Dabei wird auch auf
> zwei Quellen verwiesen.
>
> LG Felix
>
Dies scheint die veröffentlichte Version des Artikels zu sein,
den ich als undatierte Schrift schon genannt habe. Ich finde
dort den Begriff "bit reversal permutation", der zwar dort
in etwas anderer Art vorkommt, nämlich bezogen auf die
Anordnung der Elemente, die in den Zeilen der beiden Bäume
stehen, wogegen ich die Pfade von der Wurzel zu einem
Knoten vergleiche.
Man kann aber wohl die beiden Betrachtungsweisen mitein-
ander in Verbindung bringen. Ich schaue mir das Papier mal
genauer an. Was mich an den dort genannten "Quellen"
erstaunt, ist, dass die meisten doch relativ neueren Datums
sind im Gegensatz zu den "historischen" Resultaten von Stern
und Brocot. Das muss damit zu tun haben, dass die Untersu-
chung von solchen Bäumen, obwohl man sie durchaus auch
"von Hand" (und mit ziemlich viel Notizpapier) durchführen
kann, doch erst im Zeitalter der allgemein verfügbaren Com-
puter so richtig praktikabel wurde.
Gruß Al
|
|
|
| |
|
Hallo,
ich habe nun die Berechnung des Vorgänger-Bruches
eines gegebenen gekürzten Bruches z/n im Stern-Brocot-
Baum (dies war ja das Problem, das mich dazu ange-
stachelt hat, etwas weiter zu suchen) in ein kleines
Programm gesteckt. Es gibt dafür zwar keine einfache
Formel, aber doch einen recht einfachen Algorithmus.
Darin wird ausgehend vom Bruch z/n zuerst der Pfad
zurück zur Wurzel 1/1 im CW-Baum und der von hinten
gelesene CW-Code, der genau dem vorwärts gelesenen
SB-Code entspricht, bestimmt. Dann wird von 1/1 aus
im SB-Baum der Pfad bis zum Vorgänger von z/n berech-
net. Ausgegeben wird dann nur dieser Vorgängerbruch.
Allerdings könnte man die entsprechenden CW-und SB-
Pfade auch vollständig ausgeben lassen, da sie ja beim
Lauf des Programms ohnehin berechnet werden.
LG Al-Chwarizmi
Für Interessierte hier der Programmtext (TopPASCAL):
PROGRAM SBVorgaenger;
var z,n,zv,nv,zk,nk,zn,nn,k,len: longint;
code: string;
BEGIN
cleartext;
write('Zähler z = ');readln(z);
writeln;
write('Nenner n = ');readln(n);
writeln;writeln;
writeln('Bruch = ',z:1,'/',n:1);
code:='';len:=0;
while z*n>1 do
begin
len:=len+1;
if z>n then begin
code:=concat(code,'1');
z:=z-n
end
else begin
code:=concat(code,'0');
n:=n-z
end;
end;
zv:=1;nv:=1;zk:=1;nk:=1;
if code[1]='1' then zk:=2 else nk:=2;
for k:=2 to len-1 do
begin
if code[k]=code[k-1] then begin
zn:=2*zk-zv;
nn:=2*nk-nv;
end
else begin
zn:=zv+zk;
nn:=nv+nk;
end;
zv:=zk;nv:=nk;
zk:=zn;nk:=nn;
end;
writeln;writeln;
writeln('Vorgänger = ',zk:1,'/',nk:1)
END.
und hier noch eine Version, die auch die "Kinder" angibt:
PROGRAM SBFamily;
var z,n,zv,nv,zk,nk,zn,nn,k,len,
z0,z1,z2,z3,n0,n1,n2,n3: longint;
code: string;
BEGIN
cleartext;
write('Zähler z = ');readln(z);
writeln;
write('Nenner n = ');readln(n);
writeln;writeln;
code:='';len:=0;z0:=z;n0:=n;
while z*n>1 do
begin
len:=len+1;
if z>n then begin
code:=concat(code,'1');
z:=z-n
end
else begin
code:=concat(code,'0');
n:=n-z
end;
end;
zv:=1;nv:=1;zk:=1;nk:=1;
if code[1]='1' then zk:=2 else nk:=2;
for k:=2 to len do
begin
if code[k]=code[k-1] then begin
zn:=2*zk-zv;
nn:=2*nk-nv;
end
else begin
zn:=zv+zk;
nn:=nv+nk;
end;
zv:=zk;nv:=nk;
zk:=zn;nk:=nn;
end;
writeln;writeln;
writeln('Vorgänger: ',zv:1,'/',nv:1);
writeln;writeln;
writeln('Bruch: ',z0:1,'/',n0:1);
z1:=2*zk-zv;n1:=2*nk-nv;
z2:=zk+zv;n2:=nk+nv;
if z2/n2<z1/n1 then begin z3:=z1;z1:=z2;z2:=z3;
n3:=n1;n1:=n2;n2:=n3;
end;
writeln;writeln;
writeln('Kinder: ',z1:1,'/',n1:1,'':6,z2:1,'/',n2:1)
END.
|
|
|
|
