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. 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 min = tab[k - 1];
7.     int max = tab[k - 2] + tab[k - 1];
8.     int ile = max - min;
9.     int* temp = new int[ile];
10.     for (int i = 0; i < ile; i++)
11.       temp[i] = 0;
12.     for (int i = 0; i < k; i++) {
13.       for (int j = i + 1; j < k; j++) {
14.         int w = tab[i] + tab[j];
15.         if (w > min)
16.           temp[w - min - 1]++;
17.       }
18.     }
19.     int i = 0;
20.     while (temp[i] != 1)
21.       i++;
22.     tab[k] = min + 1 + i;
23.     delete temp;
24.   }
25.   return tab;
26. }

Na początek (2.) deklarujemy tablicę na wyniki i (3. - 4.) wypełniamy pierwsze znane wyrazy. Nastepnie (5.) rozpoczynamy wyznaczanie pozostałych: (6. - 9.) wyznacz minimum i maksimum dla aktualnej tablicy i utwórz tablicę pomocniczą o odpowiedniej liczbie elementów. Następnie (10. - 11.) należy ją wyzerować. Dalsza część polega na (12. - 18.) wyznaczaniu kolejnych sum i zapamiętywaniu wyniku (15.) tylko, gdy należy do poszukiwanego zakresu. Po zakończeniu wybierania par można przejść do (19. - 21.) znalezienia sumy, która wystąpiła dokładnie raz i (22.) przepisania jej. Na koniec (25.) 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. int main() {
2.   int n;
3.   cout << "Ile liczb Ulama wypisac?\n n = ";
4.   cin >> n;
5.   cout << "Pierwsze " << n << " liczb to:\n";
6.   int* tab = tablicaUlama(n);
7.   for (int i = 0; i < n; i++)
8.     cout << tab[i] << endl;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja