Ulam-Folge

Als (u,v)-Ulam-Folge wird eine von dem polnischen Mathematiker Stanisław Marcin Ulam definierte Zahlenfolge bezeichnet. Dabei sind u und v natürliche Zahlen. Die Folge ist definiert durch:

<math>a_n\,</math> ist die kleinste natürliche Zahl, die größer als <math>a_{n-1}</math> ist und sich eindeutig als Summe zweier Zahlen aus <math>\lbrace a_1,a_2,\ldots,a_{n-1} \rbrace</math> darstellen lässt.

Beispiel: Die (1,2)-Ulam-Folge hat die Glieder

<math>a_1=1,\ a_2=2,\ a_3=3=1+2,\ a_4=4=1+3</math>.

5 gehört nicht zur Folge, da 5 = 2+3 = 4+1 sich nicht eindeutig darstellen lässt. Die weiteren Folgeglieder sind

<math>6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102, 106, 114 \ldots</math>.

Die Glieder einer Ulam-Folge werden auch als (u,v)-Ulam-Zahlen bezeichnet.

Realisierung der (1,2)-Ulam-Folge in C++

include <iostream>
define N 100 // beliebige Obergrenze der Folge

using namespace std;

int main(){ int ulam[N]={}; // Ulamfolge als Array ulam[0] = 1; // Deklaration des 1. ulam[1] = 2; // und 2. Elements

for(int i=2; i< N; i++){ int x = ulam[i-1]; // potentiell nächsthöherer Listeneintrag int c; // Zähler der möglichen Kombinationen

do { c = 0; x++; // Durchexerzieren aller möglichen // Kombinationen bisherigen Listenelemente for(int k=0; k<i; k++){ for(int n=0; n<k; n++){

// Zähler Inkrementation bei Gültiger Kombination: if(ulam[n] + ulam[k] == x){ c++; }

} } } while(c!=1); // Abbruchbedingung für den Fall einer einzigen(!) // möglichen Kombination

ulam[i] = x; // Zuweisen des Wertes mit gültiger kombination cout << x << endl; // Ausgabe

} return 0; } </syntaxhighlight>Auf diese Art lässt sich jede beliebige Ulam-Folge (u,v) realisieren, indem man im Code <syntaxhighlight lang="c++"> ulam[0] = u; ulam[1] = v; </syntaxhighlight>einsetzt.

Literatur

Richard Guy: Unsolved Problems in Number Theory. 3. Aufl. Springer, New York u. a. 2004, ISBN 0-387-20860-7. S. 166–167

Weblinks

Eric W. Weisstein: Ulam Sequence. In: MathWorld (englisch).
(1,2)-Ulam-Folge A002858 in OEIS