Liczby Ulama

Cel

Liczby Ulama zostały opisane przez polskiego matematyka Stanisława Ulama. Ciąg tych liczb zaczyna się od 1, 2, 3, a każdy kolejny to unikalna suma dwóch, różnych poprzednich elementów.

Przykłady

Liczbą Ulama jest liczba 3 = 1 + 2 oraz 4 = 1 + 3. Jednak liczba 5 nie jest liczbą Ulama, ponieważ może być sumą dwóch różnych par liczb 5 = 4 + 1 = 3 + 2. Okazuje się, że następną liczbą Ulama jest 6 = 4 + 2. Tak samo jak w przypadku wartości 5 liczba 7 może być przedstawiona jako suma 7 = 6 + 1 = 4 + 3, więc nie jest liczbą Ulama.

Ciąg Liczb

Ustawiając liczby Ulama w ciąg otrzymamy: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, ...

Ciekawostka

Wśród pierwszych 28 miliardów liczb Ulama liczby 1, 2, 3 oraz 47 są jedynymi liczbami takimi, że x oraz x + 1 są liczbami Ulama (źródło).

Implementacja

Strategia

W celu wyznaczenia najmniejszej sumy elementów na podstawie k elementów należy wyliczyć sumę każdej pary różnych liczb, a potem sprawdzić, która suma jest najmniejsza i wystąpiła dokładnie tylko jeden raz.

Zauważmy, że minimalna możliwa suma to pierwszy element (zawsze 1) oraz ostatni element z dotychczas wyznaczonych liczb. Z kolei maksymalna to suma ostatniego i przedostatniego elementu z listy. Dodatkowo wiadomo, że szukamy tylko takiej sumy, która jest większa od ostatniego elementu. Na podstawie tych wiadomości wiadomo, że sumy, które będziemy zliczać należą do przedziału [ostatni element + 1, ostatni element + przedostatni element], a to w celu zaoszczędzenia pamięci można uprościć do [0, przedostatni element - 1].

Rozwiązanie

Funkcja tablicaUlama() przyjmuje jeden argument n. Wynikiem działania funkcji jest tablica długości n, gdzie i-ta wartość to i+1 liczba Ulama.

1. static int[] tablicaUlama(int n) {
2.   int[] tab = new int[n];
3.   for (int i = 0; i < 3 && i < n; i++)
4.     tab[i] = i + 1;
5.   for (int k = 3; k < n; k++) {
6.     int i = 0;
7.     int min = tab[k - 1];
8.     int max = tab[k - 2] + tab[k - 1];
9.     int ile = max - min;
10.     int[] temp = new int[ile];
11.     for (i = 0; i < k; i++) {
12.       for (int j = i + 1; j < k; j++) {
13.         int w = tab[i] + tab[j];
14.         if (w > min)
15.           temp[w - min - 1]++;
16.       }
17.     }
18.     i = 0;
19.     while (temp[i] != 1)
20.       i++;
21.     tab[k] = min + 1 + i;
22.   }
23.   return tab;
24. }

Na początek (2.) deklarujemy tablicę na wyniki i (3. - 4.) wypełniamy pierwsze znane wyrazy. Nastepnie (5.) rozpoczynamy wyznaczanie pozostałych: (7. - 9.) wyznacz minimum i maksimum dla aktualnej tablicy i utwórz tablicę pomocniczą o odpowiedniej liczbie elementów. Tablica jest wyzerowana, więc dalsza część polega na (11. - 17.) wyznaczaniu kolejnych sum i zapamiętywaniu wyniku (14.) tylko, gdy należy do poszukiwanego zakresu. Po zakończeniu wybierania par można przejść do (18. - 20.) znalezienia sumy, która wystąpiła dokładnie raz i (21.) przepisania jej. Na koniec (23.) zwracamy tablicę wyników.

Testowanie funkcji

W celu przetestowania działania kodu można posłużyć się następującym kodem, który wczyta od użytkownika ile liczb Ulama ma zostać obliczonych:

1. static void Main(string[] args) {
2.   Console.Write("Ile liczb Ulama wypisać?\n n = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   Console.WriteLine("Pierwsze {0} liczb to:", n);
5.   int[] tab = tablicaUlama(n);
6.   for (int i = 0; i < n; i++)
7.     Console.WriteLine(tab[i]);
8.   Console.ReadKey();
9. }

• Kod źródłowy Implementacja