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

Liczby Rzadkie

https://mattomatti.com/a0127

Definicja

Liczby Rzadkie to taka liczba n, że istnieje dla niej liczba zapisana wspak r taka, że n - r oraz r - n są kwadratami liczb. Dodatkowym warunkiem jest to, że n nie może być palindromem! Pierwszy opisał te liczby Shyam Sunder Gupta.

Przykład

Przykładem liczby Rzadkiej jest n = 65. Wtedy r = 56, a to z kolei rozwija się w n - r = 65 - 56 = 9 = 32 oraz n + r = 65 + 56 = 121 = 112. Jak można zauważyć wynik obu wyrażeń jest kwadratem pewnych liczb.

Jednak co z liczbą n = 2? Otóż wtedy r = 2, więc n - r = 2 - 2 = 0 = 02 oraz n + r = 2 + 2 = 4 = 22 co wskazywałoby na to, że to jest najmniejsza liczba Rzadka. W tym przypadku nie jest spełniony warunek, że n nie może być palindromem. Podobnie jest w przypadku n = 18.

Ciąg liczb

Liczby Rzadkie można ustawić w następujący ciąg: 65, 621770, 281089082, 2022652202, 2042832002, 868591084757, 872546974178, 872568754178, 6979302951885, 20313693904202, 20313839704202, ..

W większości języków standardowym typem do przechowywania liczb jest integer, który pozwoli znaleźć jedynie dwie pierwsze liczby Rzadkie. Podczas implmentacji warto mieć to na uwadze.

Implementacja

Liczb wspak

Do odwracania liczby wspak służy funkcja odwroc(), która przyjmuje tylko jeden argument a. Wynikiem działania funkcji jest liczba a zapisana wspak.

  1. static long odwroc(long a) {
  2.   long w = 0;
  3.   while (a > 0) {
  4.     w = w * 10 + a % 10;
  5.     a /= 10;
  6.   }
  7.   return w;
  8. }

Warto pamiętać, że liczba 3210 zapisana wspak to 123.

Czy kwadrat?

Kolejnym etapem do napisania jest funkcja sprawdzająca czy dana liczba jest kwadratem jakieś liczby. Najprostszym i najskuteczniejszym sposobem jest obliczyć pierwiastek kwadratowy danej liczby n, a następnie obciąć część ułamkową i sprawdzić czy po podniesieniu do kwadratu otrzymamy n.

Rozumowanie to implementuje funkcja czyKwadrat(), która dla pewnej liczby n sprawdzi czy jest ona kwadratem jakieś liczby.

  1. static bool czyKwadrat(long n) {
  2.   long a = (long) Math.Sqrt(n);
  3.   return a * a == n;
  4. }

Czy Rzadka?

Mają napisane funkcje pomocnicze napisanie funkcji czyRzadka(), która sprawdzi czy podana liczba n jest Rzadka nie powinno stanowić problemu. Oto rozwiązanie:

  1. static bool czyRzadka(long n) {
  2.   long r = odwroc(n);
  3.   return n != r && czyKwadrat(n - r) && czyKwadrat(n + r);
  4. }

Po obliczeniu liczby zapisanej wspak pozostaje sprawdzić trzy warunki: czy liczba nie jest palindromiczna tj. jej zapis wspak nie jest równy danej liczbie oraz czy kwadratami są wyniki równań n-r i r-n.

Testowanie funkcji

Napisana funkcja może posłużyć do sprawdzenia czy wprowadzona przez użytkownika liczba jest Rzadka. Oto przykładowy kod:

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj liczbę do sprawdzenia\n n = ");
  3.   long n = Convert.ToInt64(Console.ReadLine()) ;
  4.   bool w = czyRzadka(n);
  5.   Console.WriteLine("{0} {1}jest Rzadka", n, w ? "" : "nie ");
  6.   Console.ReadKey();
  7. }

Zadania

Zadanie 1

Napisz program, który dla pewnego zakresu liczb sprawdzi czy więcej jest liczb Rzadkich, które mają więcej cyfr parzystych czy nieparzystych. Zakładmy, że jeśli liczba ma tyle samo cyfr parzystych i nieparzystych to nie wpływa ona na wynik.

Przykładowo dla zakresu [1, 999999] są tylko dwie liczby Rzadkie: 65, 621770, które mają po tyle samo cyfr parzystych i nieparzystych, więc wynik jest nieokreślony.