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

Liczby Gnomiczne

Definicja

Liczby gnomiczne to liczby postaci 2n + 1, które dodane do kwadratu liczby n dają kwadrat następnej liczby, gdzie n należy do zbioru liczb naturalnych.

Przykład

Kilka pierwszych liczb gnomicznych razem z uzasadnieniem:

Lp.2n + 1n2(n+1)2
1314
2549
37916
491625
5112536

Implementacja

Funkcje wstępne

Napiszemy teraz funkcję, która jako argument dostanie liczbę n i zwróci dla niej liczbę gnomiczną:

  1. int getGnomicNumber(int n){
  2.   return 2*n + 1;
  3. }

Warto od razu też napisać drugą funkcję, która zwróci, którą z kolei jest liczba gnomiczna podana w argumencie:

  1. int whichGnomicNumber(int n){
  2.   return (n - 1) / 2;
  3. }

Czy gnomiczna?

Nasza funkcja whichGnomicNumber() ma wadę, która wynika z zaokrąglania liczb typu int. Przyjmijmy, że jako argument damy n = 4. Wtedy z wyniku dzielenie 3 przez 2 otrzymamy 1.5, ale zaokrąglenie wskaże, że zwrócimy 1, a przecież 4 nie jest liczbą gnomiczną.

Rozwiązaniem tego problemu jest sprawdzanie czy dana liczba jest liczbą gnomiczną:

  1. bool isGnomicNumber(int n){
  2.   double t = (double)(n - 1) / 2;
  3.   return (t - (int) t == 0);
  4. }

(2.) Wyliczamy wynik zamiany liczby gnomicznej na jej pozycję. (3.) Jeżeli wyliczona liczba t nie ma części ułamkowej to oznacza, że dana liczba nie jest gnomiczna.

Teraz możemy poprawić funkcję whichGnomicNumber(), która teraz zwróci -1 jeśli okaże się, że podana liczba nie jest gnomiczna czyli innymi słowy nie jesteśmy w stanie zwrócić jej pozycji na liście liczb gnomicznych:

  1. int whichGnomicNumber(int n){
  2.   if(!isGnomicNumber(n)) return -1;
  3.   return (n - 1) / 2;
  4. }

Kwadraty liczb naturalnych

Zauważmy, że (n+1)2 = n2 + 2n + 1 czyli 2n + 1 = (n + 1)2 - n2. Z tego wynika, że dodając do n-tej liczby naturalnej dodamy n-tą liczbę gnomiczną to otrzymamy kwadrat kolejnej liczby naturalnej:

Lp.n2L. Gnomiczna
113
245
397
4169
52511

Testowanie funkcji

Chcąc sprawdzić, które liczby są gnomiczne w danym zakresie możemy wykorzystać poniższy kod:

  1. int main () {
  2.   int from, to;
  3.   cin >> from >> to;
  4.   for(int i = from; i < to; i++)
  5.     if(isGnomicNumber(i))
  6.       cout << i << " " << endl;
  7.   system("pause");
  8.   return 0;

Zadania

Zadanie 1

Napisz program, który wczyta dwie liczby całkowite, które będą zakresem. Dla każdej liczby gnomicznej z zakresu podaj jej liczbę gnomiczną.