Seite 2: Universelle Präfixe

Inhaltsverzeichnis

Friedman-Zahlen können also gemäß dieser Konstruktion mit jeder gewünschten Ziffernfolge beginnen. Außerdem können sie mit einer beliebig gewählten Ziffernfolge enden, wie Erich Friedman gezeigt hat, indem er für jedes k ein Präfix angab, das man einer beliebigen Ziffernfolge von k Ziffern voranstellen kann, um eine Friedman-Zahl zu erhalten. Es lautet 25·10^k. Beispiel gefällig? Aus der zweistelligen Zahl 42 wird durch Voranstellen von 25·10² = 2500 die Friedman-Zahl 250042: Sie errechnet sich als 500² + 42.

Michael Brand hat nun diese beiden Ideen kombiniert und Infixe konstruiert, die Friedman-Zahlen ergeben, wenn man eine beliebige Zahl voranstellt und eine beliebige Ziffernfolge fester Länge dahinter. Als Baustein dafür verwendete er einen Trick, um eine Ziffernfolge zu vervielfältigen, und dieser hat gewisse Ähnlichkeit mit der Technik, die man für Quines braucht, die eingangs erwähnten selbstreproduzierenden Programme.

Ein "Quine"-Programm

Ein Programm, das seinen eigenen Quelltext ausgeben soll, kann nicht einfach print "Quelltext" lauten, denn der Quelltext ist ja insgesamt länger als das, was zwischen den Anführungszeichen steht. Man braucht eine Methode, um Text zu duplizieren und mehrfach zu verwenden. Hier ein Quine in Python:

s = 's = %r\nprint(s%%s)'
print(s%s)

Der Trick ist hier der String-Formatierungsoperator %. Ein Ausdruck der Form formatstring % parameter fügt den Parameter in den Formatstring ein, in diesem Fall an der Stelle, die mit %r markiert ist. Die Format-Anweisung %r gibt den Parameter als in einfachen Anführungszeichen eingeschlossenen String aus – genau so, wie er gebraucht wird. So fügt der Ausdruck s%s den String s in sich selbst ein und fertig ist das Quine. Ähnliches lässt sich in C mit printf() bewerkstelligen.

Ziffernkopierer

Zu Brands mathematischem Trick zur Vervielfältigung von Ziffernfolgen zunächst ein Beispiel: Um viermal die drei Ziffern 314 zu erhalten, multipliziert man 314 mit 1.001.001.001, das ergibt 314.314.314.314. Die 1.001.001.001 erhält man wiederum als 999.999.999.999/999 oder kürzer (10¹² – 1)/(10³ – 1). Allgemein: Um von einer beliebigen Zahl s der Länge L(s) r Kopien zu erzeugen, multipliziert man sie mit (10^L(s)·r – 1)/(10^L(s) – 1).

Friedman-Infixe

Indem man r groß genug wählt, kann man eine große Menge Infixe produzieren, die aus r Kopien von s bestehen und sich zu Friedman-Zahlen ergänzen lassen. So vielen Friedman-Zahlen, dass sich am Ende die gewünschte Dichte von 1 ergibt. Der vollständige Beweis ist etliche Seiten lang und im unten verlinkten Artikel nachzulesen.

Abschließend noch eine Knobelaufgabe, die wir von Erich Friedman an Sie weitergeben möchten: 123456789 ist eine Friedman-Zahl, aber wie berechnet man sie aus ihren Ziffern? Lösung auf Friedmans Seite.

Quellen und weiterführende Lektüre:

• Erich Friedman: Math Magic August 2000 zu Friedman-Zahlen
• Michael Brand: On the density of Friedman numbers. Parabola Volume 53, Issue 1 (2017)
  

(bo)