Die Hintertreppe des Josephus

23/12/2008 - 12:22 von Rainer Rosenthal | Report spam
Bitte betrachtet mit mir die folgende Treppenfunktion T:

:
: n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
: -
: T(n) 1 1 1 1 1 2 2 3 4 4 4 5 5 5 ...
:

Sie ist für eine Weile konstant mit Wert 1 und bei k=5
erfüllt sie erstmals die Bedingung

T(k) < T(k+1)

Ihr weiterer Verlauf ist eindeutig bestimmt durch diese
Bedingung:

T(n) = T(n-1) + 1, wenn T(n-1) Teiler von n ist
T(n) = T(n-1) , sonst

Ich möchte diese Treppenfunktion vorstellen, weil sie mir
im Zusammenhang mit Aufgabe Matx#344 in de.rec.denksport
ins Auge gefallen war und zu interessanten Fragen Anlass
gibt.

Definition /Nicht-Teil-Bedingung/:
eine Funktion f auf den natürlichen Zahlen
mit Werten in den natürlichen Zahlen erfüllt
die /Nicht-Teil-Bedingung/, wenn für alle n gilt:
f(n) ist 1 oder kein Teiler von n.

Die oben gezeigte Treppenfunktion T erfüllt diese Bedingung.

###################
#
# Erstens: Josephus
#
###################


Betrachtet man T genauer, so sieht man, dass sich eine gewisse
konstante "Stufenbreite" einstellt, weil nach einer Werterhöhung
der Wert von T immer für genau 3 Schritte konstant bleibt.
Experimente haben gezeigt, dass auch für andere kritische Parameter
k als den des Eingangsbeispiels sich feste Stufenbreiten
einstellen. Wenn man aufschreibt, bei welchem kritischen Parameter k
man erstmals eine neue Stufenbreite bekommt, dann erhàlt man die
folgende Tabelle:

Stufenbreite 3 4 5 6 7 8 9 10 11 12 ...

kritisches k 3 7 13 19 27 39 49 63 79 91 ...

Unser Beispiel mit k=5 hat also ebenso die Stufenbreite wie die
entsprechenden Treppenfunktionen mit k=3 bis hin zu k=6. Erst
bei k=7 hat man breitere Treppenstufen.

Und hier kommt endlich die Begründung für den Titel des Postings.
Die Folge der kritischen k scheint gleich der Josephus-Folge zu
sein: http://www.research.att.com/~njas/sequences/A000960

Diese Beobachtung möchte ich als OEIS-Fan gerne mitteilen. Natürlich
würde ich auch gerne einen entsprechenden Kommentar im OEIS abgeben,
aber vorher möchte ich erst mal abklàren, ob es wirklich wahr ist,
was ich da zu sehen glaube.


####################
#
# Zweitens: Matx#344
#
####################

Ich hatte Treppenfunktionen wie die eingangs gezeigte Funktion T
ersonnen, um die Aufgabe Matx#344 in d.r.d. zu lösen. Damit meine
Beweisidee funktioniert, benötige ich folgenden Satz:

Satz vom Treppenvergleich
Ist f eine Funktion, die der /Nicht-Teil-Bedingung/ genügt,
dann gilt f(n) <= T(n) für alle n und alle Treppenfunktionen
der eingangs gezeigten Bauweise.

Gruss,
Rainer Rosenthal
r.rosenthal@web.de
 

Lesen sie die antworten

#1 Rainer Rosenthal
23/12/2008 - 14:50 | Warnen spam
Rainer Rosenthal schrieb:

Satz vom Treppenvergleich
> Ist f eine Funktion, die der /Nicht-Teil-Bedingung/ genügt,
dann gilt f(n) <= T(n) für alle n und alle Treppenfunktionen


^^^^^^^^^^^^
f(n) >= T(n) sollte es heissen

der eingangs gezeigten Bauweise.



Bitte um Entschuldigung für den Schreibfehler.

Gruss,
RR

Ähnliche fragen