Metoda 'kolejnych dzieleń' od końca

Przyglądanie się zmianom wyglądu liczb zapisanych jako iloczyny małych wartości oraz liczby w systemie Fibonacciego spowodowały powstanie kolejnego algorytmu na poszukiwania dzielników.
Złożoność jest podobna jak przy przeskakiwaniu na kolejny system minimalizujący resztę, kiedy liczba jest dwucyfrowa. W odróżnieniu jednak od tamtego algorytmu można przeskakiwać część wartości, oraz sprawdzanych jest około połowa dopuszczalnych wartości - liczb od 1 do pierwiastka z n.

Założenie. Niech liczba nieparzysta n będzie przedstawiona wzorem
n = p*q+r,
gdzie p jest liczbą nieparzystą ograniczającą pierwiastek kwadratowy n z góry, analogicznie q jest liczbą bliską pierwiastkowi z n.

Algorytm jest następujący:
while (1<p) {
  p-=2;
  r+=2*q;
  q+= r/p;
  r = r%p;
  if( 0=r ) return dzielniki(p,q);
}
return liczba pierwsza; 

Wartość p maleje liniowo do 1, q rośnie skokami w zależności od części całkowitej ilorazu r/p. Ponieważ startujemy z wartości bliskich sobie, iloraz r/p początkowo jest równy 2 i bardzo powoli rośnie (niemonotonicznie). Dopiero kiedy sprawdzimy wszystkie dzielniki tej samej krotności cyfr dziesiętnych, iloraz ten przekroczy 20 (dzielenia rzędu 19/1). Reszta równa 0 oznacza, że mamy do czynienia z dzielnikami n = p*q. Przechodzimy tylko po wartościach p nieparzystych, gdyż dla parzystych nie ma dzielników przy nieparzystym n. 

Dla bardzo dużych wartości można dostrzec dodatkową własność, która pozwoli pominąć część przypadków. Z reszty ubywa elementów według ciągu rozbieżnego, który lokalnie daje się wyznaczać. 

Zatem sposób ten nadaje się jako konkurent rozkładu metodą dzielenia z resztą przez kolejne liczby nieparzyste (ta sama krotność przypadków), przy czym startuje od bardzo dużych wartości. Dodatkowo te ogromne są nieco prostsze w liczeniu.

Przykład numeryczny, 8934053 = 2989*2988+2921
p = 2989, q = 2988, r = 2921,  (r+2q)/p = 2
na początku nowego przebiegu pętli mamy wartości
p = 2987, q = 2990, r = 2923,  (r+2q)/p = 2
blisko pierwiastków
p = 1091, q = 8188, r = 945,  (r+2q)/p = 15
p = 1089, q = 8203, r = 986,  (r+2q)/p = 16
p = 1087, q = 8219, r = 0
rozkład 8934053 = 1087*8219.
W tym przypadku trzeba sprawdzać 952 przypadki zamiast 543 jak przy metodzie kolejnych dzieleń ze względu na położenie dzielników.

Wyjaśnienie (próba): liczba zapisana systemem Fibonacciego np. q=100100101
jest przekształcana do iloczynu (hybryda)
p*q = p00p00p0p.
Odjęcie 2 na każdej niezerowej pozycji powoduje zmniejszenie iloczynu o 2q, który jest przedstawiany jako nowa hybryda liczby Fibonacciego z taką samą wartością (p-2) na wartościach niezerowych oraz resztą r trzymaną oddzielnie.
Przechodząc z systemu Fibonacciego na dziesiątkowy powstaje ww algorytm.

Systemy niedziesiątkowe, wygląd liczby złożonej wskazującej dzielniki

Końcówka roku upłynęła na oglądaniu liczby złożonej przedstawianej w różnych systemach liczbowych, celem poszukiwania możliwości zmniejszenia krotności rozpatrywanych przypadków.

Kilka z algorytmów publikowanych na tym blogu korzysta z przedstawienia liczby w systemie o podstawach nieparzystych. Wtedy liczba złożona n=p*q w systemie o podstawie q ma cyfrę jedności równą 0.
Należy sprawdzać do połowy z pierwiastka kwadratowego z n przypadków.

Kiedy podstawy są parzyste, można oprócz konwersji na systemy p-2, p+2 łatwo przechodzić na systemy 2p, p/2. Miałem nadzieję, że manipulując tymi czteroma przekształceniami uda się dotrzeć do dzielników.
Przekształcenia działają, pojawiają się dodatkowe postacie błyskawicznie zwracające dzielnik, np:
n = a*(p-1)+a, tzn. naprzemienna suma cyfr dzieli p;
n = a*(p+1)+(p-a), tzn. suma cyfr dzieli p;
Wzory działają także dla liczb większych niż dwucyfrowe. Trudno je jednak znaleźć bez przeszukiwania.

Jeżeli mamy szczęście, to dodatkowo suma (naprzemienna) cyfr spełnia ten warunek także dla podstaw będących wielokrotnościami o potęgi całkowite z 2.
I na tym się kończy. Wiadomo jeszcze, że w pierwszej z tych postaci a jest nieparzyste (bo p-1 jest parzyste oraz wartość sumy ma być nieparzysta).
Myślałem, że dla kolejnych podstaw (p-1)*2^k wystarczy brać najmniejsze z możliwych a (nieparzyste), ale przeskakiwana jest wtedy szukana postać.

Drugie przypuszczenie: sumy i sumy naprzemienne majace w dzielnikach określoną postać w sąsiedztwie będą zbiegać do właściwych. Lecz nie do końca. Pojawiają się inne małe wartości dla sum bliskich szukanych z daleka od dzielników. Także przy samych dzielnikach wartości nie są monotoniczne.

Liczność przypadków może być nieco mniejsza, ale i tak wymagane jest sprawdzanie wielu przypadków (podstawy parzyste). Czasem widać dzielnik po przeliczeniu zaledwie połowy potrzebnych przypadków.

Nasuwa mi się możliwość zastosowania w tym przypadku specyficznego dodawania + mającego wiele argumentów. Jeden z argumentów jest dany relacją jednoargumentową '< r()', która zachowuje sumę tak długo, dopóki jest mniejsza od r, jeśli jest większa, blokuje dodawanie zwracajac wartość pustą NIL. Np. +(1, 2, 3, 4, 5, <7) zwraca NIL, bo 1+2+3+4>7. Z kolei +(1,2,3, <16, 4, 5) = 1+2+3+4+5=15<16 zwraca 15.