Zapiszmy liczbę rozkładaną n jako
a*p+b = n
gdzie a jest bliskie b, zaś p jest parzyste. W przypadku a=b mamy rozkład:
n = a*p+a = a*(p+1)
Potraktuję to wyrażenie jako zapis w systemie o podstawie p, co pozwala używać konwersji i przeniesień. Wtedy heurystyka rozkładu sprowadza się do zastosowania następujących przekształceń:
n = a*2+b = a*2+(a+1)
gdy a jest nieparzyste, przenosimy jedynkę dodając p do b (np. (a-1)*p + (p+b)).
dalej rozważamy dwa wyrażenia:
[a',b',p'] = [a/2 , b, 2p]
oraz
[a/2, b-a, 2(p+1)]
Przenosimy wartości między pierwszą a drugą pozycją, by były jak najbliższe. Jest to związane z dzieleniem przez p+1, gdyż gdy a>b przenosimy k:
a-k = b+pk, stąd a-b=(1+p)k;
oraz przy a<b
a+k = b-pk, stąd a-b=-(1+p)k;
Jeśli różnica |a-b|<p-1, odcinamy ten ciąg przekształceń. Gdy a=b kończymy zwracając rozkład. Prodedura zawsze się zakończy, gdyż każdą liczbę n przedstawimy jako 1*(n-1)+1. Liczby pierwsze mają jedynie to przedstawienie. Nie można użyć |a-b|<p, co będzie pokazane w przykładzie dalej.
Uzyskamy w ten sposób kolejne wyrażenia, których wydaje się wykładnicza liczność. To się tylko wydaje. Na początku owszem, potem przycinianie bierze górę.
Przedstawić wszystkie możliwe przedstawienia dla rozkładu liczby 133.
p=2, a=44, b=45 (44*2+45 z dzielenia 133/3), czyli
[44, 45, 2]
kolejne trójki to:
[22, 45, 4] oraz [22, 45-44, 2(2+1)] = [22, 1, 6]
po poprzenoszeniu nadmiarów, by przybliżyć a do b mamy:
[26, 29, 4] oraz [19, 19, 6], które już wskazuje poszukiwane przedstawienie 19*(6+1). Cięcie.
Teraz z [26, 29, 4] uzyskujemy
[13, 29, 8] oraz [13, 3, 10]
Z tego drugiego przenosimy, np. do [12, 13, 10]. Kolejna iteracja da trójki [6, 13, 20] oraz [6, 1, 22]. W obu różnica |a-b| da 7, 5 odpowiednio, obie mniejsze niż p>19. Tniemy, choć z [6, 1, 22] mozemy uzyskać ostatnie przedstawienie [1, 1, 132] korzystając z konwersji na system o potrojonej podstawie.
Wracamy do [13, 29, 8], przenosimy jedynkę, tym razem zwiększając a - i tak zaraz dzielimy przez 2. Mamy [14, 21, 8].
Zauważmy, że różnica b-a=7 jest podzielna zarówno przez 7, jak i 14, i jest mniejsza niż p=8. Jest ochota na przycięcie, co zgubi kolejne przedstawienia.
Oto kolejne trójki: [7, 21, 16], oraz [7, 7, 18], z drugiej wynika kolejne przedstawienie 7*(18+1).
Pierwszą modyfikujemy do [8, 5, 16]. Co prawda teraz a>b, ale jest parzyste, zaraz się zmniejszy. Teraz podaję już tylko trójki nie spełniające warunku przycinania: [4, 5, 32], [2, 1, 66] i ostatecznie ucinane [1, 1, 132].
Znalezione trzy przedstawienia dla rozkładu 133 = 19*(6+1) = 7*(18+1) = 1*(132+1).
Teraz tylko zaimplementować...
Brak komentarzy:
Prześlij komentarz