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:

${\displaystyle a_{1}=u\,}$

${\displaystyle a_{2}=v\,}$

${\displaystyle a_{n}\,}$ ist die kleinste natürliche Zahl, die größer als ${\displaystyle a_{n-1}}$ ist und sich eindeutig als Summe zweier Zahlen aus ${\displaystyle \lbrace a_{1},a_{2},\ldots ,a_{n-1}\rbrace }$ darstellen lässt.

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

${\displaystyle a_{1}=1,\ a_{2}=2,\ a_{3}=3=1+2,\ a_{4}=4=1+3}$.

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

${\displaystyle 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 }$.

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

Realisierung der (1,2)-Ulam-Folge in C++[Bearbeiten | Quelltext bearbeiten]

#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; } 

Auf diese Art lässt sich jede beliebige Ulam-Folge (u,v) realisieren, indem man im Code

ulam[0] = u; ulam[1] = v; 

einsetzt.

Literatur[Bearbeiten | Quelltext bearbeiten]

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

Weblinks[Bearbeiten | Quelltext bearbeiten]

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