Liczby Cykliczne

Definicja

Liczba Cykliczna to taka liczba naturalna, której kolejne wielokrotności są pewną permutacją cyfr liczby pierwotnej. Liczba cykliczna nie może składać się z zer na początku, a każda wielokrotność musi być tej samej długości co liczba wyjściowa.

Jeśli jednak tylko pewne wielokrotności liczby są permutacją jej cyfry to można powiedzieć, że taka liczba jest pseudocykliczna.

Przykład

Najmniejszą liczbą cykliczną jest 125874, ponieważ jej druga wielokrotność to 251748. Zdecydowanie ciekawszym przykładem jest liczba 142857, której 6 kolejnych wielokrotności jest przestawieniem jej cyfr.

Z kolei przykładem najmniejszej liczby pseudocyklicznej jest 1035, której jeszcze trzecia wielokrotność to 3105. Nie jest to jednak liczba cykliczna, ponieważ dwukrotność 2070 też powinna składać się z tych samych cyfr co 1035.

Implementacja

Założenia

Poniżej zostanie przedstawiony kod funkcji czyCykliczna(), która dla danej liczby a określi jej przynależność tj. czy liczby jest cykliczna, pseudocykliczna czy nie należy do żadnej z tych grup. W celu wypisania tylko konkretnej grupy będzie można przekazać maskę, która pozwoli określić czy funkcja ma wypisywać liczby przynależące do danej grupy. Maska składa się z trzech bitów: najmniej znaczący określa czy mają się wypisywać liczby cykliczne, kolejny czy liczby pseudocykliczne, a ostatni czy mają być wypisane liczby nie należące do tych grup. Dzięki temu istnieje możliwość filtrowania danych. Domyślną wartością jest 3 co znaczy, że program wypisze tylko liczby cykliczne oraz pseudocykliczne.

Funkcje pomocnicze

Liczby w systemie dziesiętnym składają się z dziesięciu różnych cyfr. W celu policzenia ile jest których cyfr można skorzystać z funkcji tablicacyfr(), która zapisuje ile jest każdej cyfry w przekazanej wartości liczba do tablicy tablica.

1. void tablicacyfr(long liczba, int* tablica) {
2.   for (int i = 0; i < 10; i++)
3.     tablica[i] = 0;
4.   do {
5.     tablica[liczba % 10]++;
6.     liczba /= 10;
7.   } while (liczba != 0);
8. }

Ze względu na fakt, że ilość poszczególnych cyfr będzie wykonywana na tablicach nie liczbach to przy pomocy funkcji identycznetablice() można sprawdzić

1. bool identycznetablice(int* tab1, int* tab2) {
2.   for (int i = 0; i < 10; i++)
3.     if (tab1[i] != tab2[i])
4.       return false;
5.   return true;
6. }

Rodzaj liczby

Warto zauważyć, że niezależnie od wartości liczby a co najwyżej jej 10 wielokrotność zawsze będzie dłuższa niż pierwotna liczba a. Z tego powodu można założyć, że zostanie spisanych maksymalnie 9 wielokrotności, które są permutacją cyfr liczby a.

1. void czyCykliczna(long a, int stopien = 3) {
2.   int* mnozniki = new int[10];
3.   for (long i = 0; i < 10; i++)
4.     mnozniki[i] = 0;
5.   int* a_cyfry = new int[10];
6.   int* b_cyfry = new int[10];
7.   tablicacyfr(a, a_cyfry);
8.   int i = 1, j = 0;

(2.) Przygotuj listę pod kolejne wielokrotności i ją (3. - 4.) wyzeruj. Przygotuj również listy pod zapis cyfr (5.) liczby a i (6.) sprawdzanej wielokrotności. (7.) W tablicy a_cyfry zapisz ilość każdej cyfry z liczby pierwotnej. (8.) Zadeklaruj dwa indeksy: i do przechodzenia po kolejnych wielokrotnościach oraz j - do zapamiętywania kolejnej wielokrotności spełniającej kryteria.

9.   while ((long)(log10(a * i)) == (long)(log10(a))) {
10.     tablicacyfr(a * i, b_cyfry);
11.     if (identycznetablice(a_cyfry, b_cyfry))
12.       mnozniki[j++] = i;
13.     i++;
14.   }
15.   delete a_cyfry, b_cyfry;

(9.) Dopóki jest szansa na znalezienie wielokrotności spełniającej kryteria to: (10.) oblicz ile jest każdej z cyfr i (11.) jeśli jest to permutacja liczby a to (12.) zapamiętaj, która to jest wielokrotność. (13.) Na koniec każdej iteracji przejdź do nastepnej wielokrotności. (15.) Po zakończeniu szukania wielokrotności usuń tablice a_cyfry oraz b_cyfry.

16.   if (j == 1) {
17.     if (stopien & 4)
18.       cout << a << " nie jest cykliczna\n";
19.     delete mnozniki;
20.     return;
21.   }
22.   for (int k = 1; k < j; k++) {
23.     if (mnozniki[k] != mnozniki[k - 1] + 1) {
24.       if (stopien & 2)
25.         cout << a << " jest pseudo cykliczna\n";
26.       delete mnozniki;
27.       return;
28.     }
29.   }
30.   if(stopien & 1)
31.     cout << a << " jest cykliczna\n";
32.   delete mnozniki;
33.   return;
34. }

Ostatni etap polega na zinterpretowaniu wyliczonych danych. W przypadku, gdy (16.) j = 1 to znaczy, że tylko jedna wielokrotność a = 1·a spełnia wymagania, więc nie jest to liczba cykliczna. (18.) Taki komunikat wypisujemy tylko, gdy (17.) maska stopien wskazuje, że taka informacja ma zostać wypisana.

Testowanie funkcji

Poniższa funkcja wypisze wszystkie liczby cykliczne z przedziału [1, 10000).

1. int main () {
2.   for (long i = 1; i < 10000; i++) {
3.     czyCykliczna(i, 3);
4.   }
5.   system("pause");
6.   return 0;
7. }

• Kod źródłowy Implementacja