Strona główna » Algorytmy » Artykuły » Liczby Ulama
 

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.

C++
C#
  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:

C++
C#
  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. }
Zadania
Zadanie 1
Napisz program, który dla każdej pary policzy ich różnicę, a następnie w formie tabelki zostanie przedstawiony procentowo wystąpienia danej różnicy wśród wszystkich. Dane powinny być posortowane i wypisana w sposób następujący:
Różnica Procent1 60%
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1