Liczby Carola

Definicja

Liczby Carola to takie liczby całkowite, które są postaci a_n = 4ⁿ - 2^{n + 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: a₃ = 4³ - 2^{3 + 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ę 101111₂ = 47₁₀.

Wyjaśnienie drugiej metody

W celu zrozumienia zasady drugiej metody warto się przyjrzeć wzorowi wyjściowemu. Po pierwsze 4ⁿ = 2²ⁿ 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 2^{n + 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 a_n = (2²ⁿ - 1)² - 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.

Zwróconą wartość przez program jest a = 01101111₂ = 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. }

• Kod źródłowy Wyliczanie ze wzoru
• Kod źródłowy Zapisu binarnego

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.

• Kod źródłowy Zadanie 1