Strona główna » Algorytmy » Teoria Liczb » Liczby Carola
 

Liczby Carola

Definicja

Liczby Carola to takie liczby całkowite, które są postaci an = 4n - 2n + 1 - 1.

Tego typu ciąg można również otrzymać w inny sposób. W celu otrzymania n - tej liczby Carola wystarczy zapisać kolejno n - 2 cyfr jeden, następnie cyfrę 0, a potem n + 1 liczb 1. Następnie tak przygotowaną liczbę można przeliczyć na dowolny system liczbowy.

Ciąg liczb

Liczby Carola tworzą następujący ciąg: -1, 7, 47, 223, 959, 3967, ..

Przykład

Rozpatrzmy dwa przypadki wyliczania trzeciej liczby Carola 47. Pierwszy z nich polega na skorzystaniu ze wzoru na n-ty wyraz ciągu: a3 = 43 - 23 + 1 - 1 = 64 - 16 - 1 = 47. Ciekawszym jednak sposobem wyznaczenie jest druga metoda. Zapiszmy kolejno 3 - 2 cyfry 1, cyfrę 0 i 3 + 1 cyfr 1. W ten sposób otrzymuje się 1011112 = 4710.

Wyjaśnienie drugiej metody

W celu zrozumienia zasady drugiej metody warto się przyjrzeć wzorowi wyjściowemu. Po pierwsze 4n = 22n co w zapisie binarnym daje cyfrę 1 oraz 2n - 1 cyfr 0. Odejmując od tej postaci 1 liczba teraz będzie się składać z 2n - 1 cyfr 1. Ostatni składnik 2n + 1 to w zapisie binarnym cyfra 1 i n cyfr 0. Oznacza to, że usuwa cyfrę 1 na pozycji n + 2 od prawej. Oznacz to, że po lewej stronie pozostaje (2n - 1) - (n + 1) cyfr 1 czyli n - 2. Dokładnie tyle ile zostało podane w przepisie.

Implementacja

Wyliczanie ze wzoru

Potęgowanie to kosztowna informacja nawet jeśli zastosuje się technikę szybkiego potęgowania. Z tego względu warto je ograniczyć do minimum. Wzór na n-ty wyraz warto zapisać jako an = (22n - 1)2 - 1. Wtedy kod można zapisać jako funkcję nCarol(), która dla podanego n zwróci n-ty wyraz ciągu:

  1. int nCarol(int n) {
  2.   int a = pow(2, n) - 1;
  3.   return a * a - 2;
  4. }

Zapis binarny

Drugą metodę wyznaczania liczb Carola można osiągnąć korzystając z operacji binarnych. Pomijając pierwszy przypadek -1. Można zapisać funkcję, która utworzy liczbę złożoną z 2n - 1 cyfr 1 pomijając pozycję n + 2 od prawej.

  1. int nCarol(int n) {
  2.   if (n == 1)
  3.     return -1;
  4.   int a = 0;
  5.   for (int i = 0; i < 2 * n; i++) {
  6.     a <<= 1;
  7.     if (i != n - 2)
  8.       a += 1;
  9.   }
  10.   return a;
  11. }

(2. - 3.) Wyszczególnij nieobsługiwany przypadek. (4.) Utwórz nową liczbę o samych cyfrach 0. (5. - 9.) Wykonaj 2n - 1 operacji polegających na przesunięciu obecnej wartości o 1 pozycję w lewo i ustaleniu pozycji najmniej znaczącej (tj. pierwszej cyfry od prawej).

Działanie pętli można prześledzić na podstawie poniższej tabelki. W poniższym rozwiązaniu przyjęto, że n = 4, a typ zmiennej przechowuje 8 bitów (1 bajt). Na szaro wyszczególniono jeszcze nie ustalone bity.

iaOperacja
000000000przesuń, 0 != 2: dodaj 1
100000001przesuń, 1 != 2: dodaj 1
200000011przesuń, 2 != 2: pomiń dodawanie
300000110przesuń, 3 != 2: dodaj 1
400001101przesuń, dodaj 1
500011011przesuń, dodaj 1
600110111przesuń, dodaj 1
701101111przesuń, dodaj 1
-11011111/* wynik końowy */

Zwróconą wartość przez program jest a = 011011112 = 223.

Testowanie funkcji

W celu przetestowania obu implementacji można skorzystać z przedstawionej funkcji main() wypisującj pierwsze dziesięć wyrazów w kolejnych liniach.

  1. int main () {
  2.   for (int i = 1; i <= 10; i++) {
  3.     cout << nCarol(i) << endl;
  4.   }
  5.   system("pause");
  6.   return 0;
  7. }

Zadania

Zadanie 1

Napisz program, który zsumuje kolejne k liczb Carola począwszy od wyrazu m. Przykładowo funkcja sumakwyrazowCarola() dla m = 1, k = 3 powinna zwrócić 276. Postaraj się znaleźć wzór na sumę, aby ograniczyć wykonywane obliczenia.