Programowanie rekursywne współbieżne, szukanie wzorca w napisie

 Jestem blisko stylu programowania, o którym już dawno myślałem. Chcę ominąć ograniczenia, które przyjmuje się za podstawy programowania rekursywnego. 

Tymi ograniczeniami są: szybkie zużycie stosu na ciała wywołań kolejnych funkcji, wielokrotne obliczane tego samego. 

Moje podejście wydaje się omijać oba ograniczenia. Zamiast stosu używam kolejki, dzięki czemu nie muszę pamiętać wcześniejszego wywołania, oraz ograniczam pętle, wskazując konkretnie, gdzie odkładać wyniki pośrednie. 

Wiążą się z tym jednak inne problemy do rozwiązania. Pierwszym z nich jest: gdzie pojawią się wyniki? Należy w ciele wywołania funkcji trzymać adres klasy, do której trafią wyniki. Ma też inne zachowania, np. pozwala zastosować funkcje wielowartościowe.

Zastosowałem ten sposób do znajdywania wzorca w napisie. Najlepsze logarytmy mają złożoność O(n+m), gdzie n jest długością napisu, a m długością wzorca. Ta złożoność u mnie zachodzi dla dokładnie jednego wzorca, kiedy nie ma tekstów zaczynających się tak samo jak wzorzec. Moją złożoność szacuję na O(n*m), zależy od napisu i wzorca. Trzeba dodatkowo zapamiętać położenie pierwszej zgodności wartości oraz położenie wyników, te dane przy wychodzeniu z funkcji (rekursywnych mojego typu) są tracone.

Wywołanie odbywa się przez zapakowanie do klasy i uruchomienie ciągu: 

0. [szukajTekstu, napis, indeksNapisu, wzorzec, indeksWzorca, skadZgodnosc, wynik]

Klasa ma jedną metodę, która porównuje ze sobą dwie wartości

napis[ indeksNapisu ] == wzorzec[ indeksWzorca ]

Jeżeli są zgodne oraz skadZgodnosc jest ustawiona na jakąś pozycję, kolejny znak tekstu jest zgodny ze wzorcem. Jeśli nie, ustawia się skadZgodnosc na pozycję indeksNapisu, oraz wywołuje dwie funkcje, przez odłożenie ciągów

1. [szukajTekstu, napis, indeksNapisu+1, wzorzec, indeksWzorca+1, skadZgodnosc, wynik]

dla kontynuacji, oraz 

2. [szukajTekstu, napis, indeksNapisu+1, wzorzec, 0, nil, wynik]

dla poszukiwania początku kolejnego wzorca w napisie.

Jeśli wartości nie są zgodne, rekursja jest zatrzymywana dla tego konkretnego przypadku, ale póki nie sprawdzony jest cały napis, należy ponownie wywoływać 2. 

Oczywiście przy wywołaniu rekursywnym należy zacząć od przypadków szczególnych, indeksNapisu maksymalny to zakończenie tego ciągu rekursji, zaś indeksWzorca maksymalny to odłożenie do wyniku ciągu

3. [wynik, ?, skadZgodnosc]

W miejsce pytajnika należy podać informację o przebiegu. Nie wiadomo, czy algorytm się zatrzyma i kiedy. Dlatego klasa wynik musi być czymś w rodzaju sprytnego wskaźnika dla wywołań.

Jedno przejście po napisie wystarczy, by wyłapać wszystkie wystąpienia wzorca. Szukając 'na' w tekście 'ananas nasz' algorytm zwrócił tablicę [1,3,7]. Ale dla tego samego wzorca i napisu 'nanas nasz' o wyniku [0,2,6] pojawił się problem, jak trzymać w pamięci skadZgodnosc. Należało go zwiększyć o 1, gdyż inaczej blokowało wynik. Przyczyna nieznana, wszystkie dane były traktowane praktycznie jako void i kompilator nie wiedział co zrobić z semaforem na nil. Ewentualnie można przyjąć liczenie pozycji od 1, zaś 0 stosować jako semafor.

Szybkie sprawdzanie podzielności przez niektóre liczby

Mnożenie liczb mających w systemie binarnym same jedynki daje pośrednio (przed użyciem przeniesień między cyframi) bardzo specyficzną strukturę - piramidę, np. 3*7 = [1 2 2 1] _2. 

Długość piramidy jest o 1 mniejsza niż długość (liczność bitów) większego z dzielników, największa wartość piramidy to liczność bitów krótszego dzielnika. Zatem mogąc utworzyć z liczby taką piramidę - wartość w nawiasie powtarza się: 

1 (2) 1, 

1 2 (3) 2 1, 

1 2 3 (4) 3 2 1, itd. 

łatwo dopasujemy dzielnik. 

 Istnieje jeszcze jedna własność, gdy w dzielniku p dokładnie jeden z bitów jest wyzerowany, np. 2^k, liczba N = p*q, to przez dodanie t = q*2^k uzyskamy piramidę o znanym rozkładzie. Korzystając wtedy z 

N+q*2^k = q*(p + 2^k) = (2^r-1) * (2^s-1) 

uzyskujemy, że dodawana wartość jest wielokrotnością dzielnika N. Zatem dopełniając N do piramidy, oraz licząc największy wspólny dzielnik gcd(t,N), uzyskamy niezwykle szybko rozkład N. 

 Uzupełnianie do piramidy odbywa się następująco: przechodzimy po bitach N wyłączając skrajne najmniej i najbardziej znaczące cyfry. Jeśli jest tam 0, wstawiamy 2, jeśli 1 zostawiamy. Uzyskana podwojona wartość binarna jest tą, która jest iloczynem 3*(2^n-1) o postaci 1 (2) 1. 

By uzyskać kolejny poziom, dodajemy po prostu wartość (2^(n-2*k)-1)*2^k dla odpowiedniego k przy długości nieparzystej podstawy piramidy. Dla długości parzystej modyfikacja jest niewielka. Zasada - w kolejnym składniku usuwamy obie skrajne jedynki i mnożymy przez 2.

I tak mając 25 = [1 1 0 0 1], aby uzyskać piramidę, należy dodać [1 2 2]*2 = 20, wspólny dzielnik gcd(25, 20) = 5 jest dzielnikiem. 

Ten sposób działa dla 7, 13, 11, 5, 31 i innych, zawodzi przy 19, która ma dwa bity wyzerowane w zapisie.

Sposób rozkładu liczb na dźdźownicę

Tym razem zamiast opisu kolejnego sposobu rozkładu liczb na czynniki, zapresentuję sposób, jak do niego doszłem. Mój zapis jest okropny, przypomina kod w LISPie opisany w nonsensopedii. Zaś złożoność i sposób przechodzenia do nowej iteracji nieodłącznie kojarzy mi się z dźdźownicą. Ma takie same fazy o znikomej złożoności. 

 Sposób należy do grupy  prezentacji liczb, w którym każda cyfra jest zapisana w innym systemie liczbowym, czyli 

\sum _{i} \prod _{0<k<i} a_i p_k

gdzie a_i są cyframi, a p_k iloczynami kolejnych podstaw. Odpowiednikiem w systemie dziesiętnym p_k są: 10, 100, 1000, ... Dalej p_k będzie oznaczać największy przyrost podstawy p_k = (i-1)/(i-2), bo reszta jest wyłączana przed nawias.

Jeśli mamy liczbę postaci N = A*p+a, to jest ona równa A*(p+2) + (a-2A), w ten sposób będę sprawdzać reszty z dzielenia. Warto zatem, by A było podzielne przez (p+2), by jak najłagodniej przekształcić a-2A w liczbę dodatnią nie większą niż p+2. W budowie A wyłączamy zatem p+2 do ostatniej cyfry w zapisie, by mieć mniej kłopotu z przenosinami. Niestety, okazuje się, że składnik z (p+2) występuje wewnątrz A i zarazem pojawia się drugi przy przekształceniu. Aby któryś opuścić, należy pomnożyć przez taki pozostałe cyfry liczby A. To są stosunkowo spore wartości, które po przenoszeniu na sąsiednią, bardziej odpowiadajacą im pozycję będą musiały być dzielone przez wartość bliską tej, przez którą mnożymy.

I można zapobiec temu wielokrotnemu mnożeniu i dzieleniu. Mamy przecież tożsamość b : (p+2) = (p+4)-2 = (p+6)-4, itd, dzięki czemu każdą kolejną cyfrę zapisujemy jako sumę wielokrotności p_k poprzedzającego cyfrę i jakiejś reszty. To jest rozwinięcie zapisu przypominające wygięcie pierścieni dżdżownicy. 

Stosując teraz rozdzielność mnożenia względem dodawania, łączymy elementy o tej samej wartości p_k z sąsiednich cyfr, co wygładza obliczenia i powstaje prosta postać liczby, rozpisana minimalną licznością symboli.Mamy sumę trzech wartości, pochodzących z A, -2A oraz przekształcenia b. Wymaga jeszcze dopasowania do ograniczeń na cyfry, by były nieujemne nie większe niż p_k, przenosinami, których jest do kilku sztuk. Obawiam się, że złożoność tych przekształceń dąży asymptotycznie do stałej.

Inicjacja liczby, reszta z dzielenia przez 3 to cyfra najmniej znacząca, następna jest resztą z dzielenia części całkowitej ilorazu przez 5, itd rekursja przez kolejne liczby nieparzyste aż liczba zmaleje poniżej p_k. 

Podczas iteracji wartości podstaw (p+k) przechodzą na (p+k+2), i to stosunkowo niskim kosztem przeniesień. Na kadej cyfrze mamy delikatne tłumienie, co jest najlepiej widoczne na cyfrze najbardziej znaczącej. 

Nie zapisuję przykładu, bo wyglądałby tak 2+3*(4+5*(...)), co przechodzi w 3+5*(2+7*(...)). 

I patrząc na odwłok tej pełznącej matematycznej dżdżownicy widać zmiany reszt z dzielenia przez kolejne liczby nieparzyste...

Liczby pierwsze jako palindromy

Palindrom, którego wszystkie współczynniki są podzielne przez a, sam jest izomorficzny z liczbą podzielną przez a. Tak 7 0 7 14 7 0 7 jest podzielne przez 7. 

Pojawiły się kłopoty, ale nie tyle natury obliczeniowej, bo algorytm zachłanny łatwo wyznaczy taki palindrom nieparzystej długości począwszy od wartości skrajnych (skrajne wyrazy są resztami z dzielenia). Po prostu jest takich za dużo...

Pierwsze podejście, wyrazy prócz środkowego to a oraz 0. 

Drugie podejście, wyrazy prócz środkowego to a oraz 2a.

W obu sposobach 'szaleństwo' wyrazu środkowego przy zmianie a o 2. Zmiany bywały parę rzędów wielkości większe niż a. 

Najbardziej optymalne jest rozpychanie (z głową) wyrazów od wyrazu środkowego na boki, zwiększając je o 2. Tak nad systemem binarnym pojawił się schemat ogólny [+2, -3, (-1), -3, +2], nad trójkowym [+3, -7, (-4), -7, +3]. Wyraz w nawiasie () powtarza się stosownie do długości palindromu. 

Ale nie widać, by przybliżało dzielniki. Jest jednak cecha charakterystyczna dla podstaw p większych od 2, wyrazy skrajne są powtarzajacym się ciągiem długości p^2. Zależy od dwu ostatnich cyfr zapisu w systemie o podstawie p.

Dla ratowania sytuacji sprawdziłem, czy jest zależność w przedstawianiu liczb pierwszych jako palindromów. Spodziewałem się rozkładu współczynników jak w rozkłądzie Gaussa, np. 1 2 4 2 1. Niestety, są wyjąctki, np. 3 2 0 2 3 = 71 nad binarnym.

Obwiednia wypukła jako punkt wyjścia innych algorytmów.

 Od paru dni rozmyślam nad obwiednią wypukłą, szykując się do projektowania matematyki. Podejście jest następujące. Obliczam punkty obwiedni wypukłej. Oddzielam je od innych. Generuję kolejną obwiednię wypukłą, i znów oddzielam jej punkty. Mam teraz dwa wielokąty wypukłe, jeden wewnątrz drugiego. Reszta punktów w środku, czeka na kolejną iterację.

I to moze być punkt startowy kilku wielomianów: np. triangulacji, cyklu Hamiltona, a nawet problemu komiwojażera w przypadku wagi będącej odległością euklidesową, gdyż szukanie najkrótszej trasy degeneruje się do lokalnego przeszukiwania spośród kilku punktów. Wystarczy wybrać sąsiednie bliskie sobie punkty obu obwiedni (przy komiwojażerze może być konieczny jeszcze jeden punkt z bardziej zewnętrznej obwiedni, sąsiad na powstającym cyklu Hamiltona, gdyż odcinek utworzony z dwu sąsiadujących punktów przekształcamy w wielokąt minimalizujący długość ścieżki).

Tworzenie oprogramowania, strategia szpitalna

 Napisałem własną wersję Kapi Hospital, skoro na oryginał nie mogę się zalogować. Przy okazji, niektóre zastosowane rozwiązania okazały się symulowaniem AI, w szczególności stopniowe (zależne od znajomości chorób) wyświetlanie danych. 

Zaczyna się brakiem rozpoznania, potem sugeruję lekarstwo, potem nazwę  choroby oraz poziom zniszczenia lekarstwa. Jeszcze później domniemaną (nie faktyczną) moc choroby. Finalnie pierwsza z chorób pacjenta jest rozpoznawana jeszcze na korytarzu szpitalnym. 

Mam pole morale, czyli zadowolenia pacjentów z leczenia. Wprowadziłem ograniczenie, że pacjent może być podleczony (albo nawet wyleczony z jednej choroby) zaledwie raz między nabywaniem energii przez lekarza - coś w rodzaju zakamuflowanej tury. I ten ogranicznik jako efekt uboczny powoduje 'ucieczkę' pacjenta z gabinetu na korytarz kiedy chcę mu coś ponownie aplikować.

Projekt uważam za niemal zakończony. Jest w fazie testowania - grania. I wciąga. Nawet mnie.

Widok kodu przypomina nieco programowanie obiektowo orientowane, ale to tylko przystosowanie - obiektowo nie jestem w stanie zrobić nic takiego. W końcu baza danych 146 chorób powstała w nieco ponad dwa dni na samym końcu, kiedy już niemal wszystko działało. Pozostały poprawki interfejsu i dobieranie współczynników.

Przy okazji pojawił się błąd segmentacji pamięci. Wprowadzając nowe choroby zapomniałem o stałej, w której trzymam ich liczność. Stała ta wyznacza rozmiar pamięci na trzymanie tablic wskaźników. I oczywiście podczas kompilacji pojawiły się odwołania poza zakres tablic, gdzie odkładałem wskaźniki (indeksy) na choroby lub lekarstwa. 

Następna wersja tego projektu może być typu RPG w stylu wczesnych wersji MIght & Magic czy Wizardry. Choć dalej tekstówka. 

Układ kongruencji dający wzory na dzielniki liczby

W ostatnim poście napisałem 'wzór na dzielniki'. Jest to raczej układ kongruencji, które są widoczne jako układ równań.

Postać wejściowa to palindrom [i,j,k,j,i]_p nad systemem pozycyjnym o podstawie p, który jest przedstawiony jako iloczyn dwu palindromów. W tym iloczynie wartości skrajne są znane, nieznane są tylko pozycje odpowiadające cyfrom dziesiątek liczb. 

Zatem dany jest iloczyn [a, x, a]_p * [b, y, b]_p , z niewiadomymi x, y. 

Konwertujemy palindrom na systemy o podstawach (p-1) oraz (p+1). Uzyskujemy w ten sposób nowe wielomiany, których współczynniki są blisko ze sobą związane. Niestety, przenoszenie między cyframi może się jeszcze zachować mimo próby jego uwzględnienia we współczynnikach stałych układu. Porównując teraz współczynniki (jako kombinacje liniowe i jako iloczyny) uzyskujemy wspomniany układ kongruencji. 

I to wszystko.  

Na przykładzie N = 8934053 = [15, x, 15]_{16} * [11, y, 11]_{16}

Jeden z palindromów to N = [165, 0, -7342, 0, 165]_{16}, inny N = [165, 3152, -57971, 3152, 165]_{16}. 

Mamy dodatkową stałą 4*165 = 660, oraz układ równań: 

N = [165, e, e+f, 2f, f] _{15} = [165, c, d-c, -2d, d]_{17}
e-c = 4*165 = 660  (co pochodzi z kombinacji liniowej (x,y) z (15,11))
c = 11x+15y-660
e = 11x+15y+660
d = xy -2*11x-2*15y+4*165 = g*h
f = xy+2*11x+2*15y+4*165 = (4*15-g)*(4*11-f)
g = 2*15-x
h = 2*11-y

W praktyce uzyskane współczynniki nie są zbyt miłe:
N = [165, 3812, -47525, -102674, -51337]_{15}
N = [165, 2492, -66437, 127890, -63945]_{17}

Dlatego jednak preferuję inne sposoby rozkładu... Nie jestem do końca pewien, czy potrafię rozwiązywać takie układy, czy palindrom początkowy nie ma tutaj znaczenia.

Wzór na dzielniki. przygotowanie postaci

 Już parę razy zastanawiałem się tutaj, czy istnieje wzór na dzielniki liczby. I teraz znalazłem postać, dla której istnieje układ równań, z którego można wyznaczyć dzielniki. 

W tym poście przedstawię ową specyficzną postać zapisu liczby. 

Palindromem nad postawą p nazywamy wielomian o współczynnikach całkowitych postaci 

a[n] * p^n+ ... + a[1] *p + a[0], 

w którym a[n] = a[0], a[n-1] = a[1], ... po zmianie oznaczeń (n = 2k+1, r naturalne, dla n parzystego dwa sąsiednie wyrazy w środku są równe) a[k+r]=a[k-r] , 

np. [7, 12, 18, -1, 18, 12, 7]_{16} to palindrom nad systemem szesnastkowym o długości 7 i wartości liczbowej N = 7*(16^6+1) + 12*(16^5+16) + 18*(16^4+16^2) - 1*16^3.  Palindrom tworzymy po prostu przenosząc od krajów wartości z cyfr do cyfr mniej znaczących kończąc w środku. Skaczemy od cyfr mało znaczących do dużo znaczących i na odwrót dopasowując wartości najpierw na pozycjach mniej znaczących.

Własności palindromu nad systemem p: 

- z dowolnej liczby całkowitej można uzyskać palindrom nieparzystej długości, palindrom parzystej długości udaje się wyznaczyć tylko wtedy, gdy wartość liczbowa jest podzielna przez p+1.

- skrajne współczynniki palindromu są wielokrotnościami reszty z dzielenia N przez p.

- cecha podzielności: wartość palindromu jest podzielna przez x, gdy wszystkie współczynniki palnidromu są wielokrotnościami x, np. [x, 3x, 0, 2x, 0, 2x, 0, 3x, x]_p; albo wspólny dzielnik wyraz skrajnego a[0] i p jest dzielnikiem N. 

- iloczyn palindromów jest palindromem. 

-  konwersja palindromu długości 3: [a, b, a] na sąsiedni system (p+1) lub (p-1) ma z dokładnością do znaku tylko dwa różne współczynniki [a, 2a+b, 2a+b]_{p-1} oraz [a, b-2a, 2a-b]_{p+1}. Konwersje niszczą zatem strukturę palindromu. 

- palindrom nie jest  jednoznacznie wyznaczony, niezmiennikiem palindromu długości 3 jest [a+p, b-p*p-1, a+p]_p = [a,b,a]_p . Najwięcej napotykanych palindromów jest nad systemem binarnym. np. skrajne o wyrazach dodatnich liczby nieparzystej to: pierwszy [1, (N-5)/2, 1]_2, w drugim mamy około (zależy od parzystości N) [floor(N/5), x, floor*N/5)]_2 , gdzie x ma jedną z wartości: 0, 1, 2, 3, 4 w zależności od N. Dla 8934053 mamy w ten sposób palindromy  o wyrazach dodatnich między [1, 4467024, 1]_2 oraz [1786809, 4, 1786809]_2. Ze wzrostem p palindromy są coraz rzadziej spotykane. 

Przechodzę do postaci liczby N. 

Tworzę palindrom długości 5 o takiej podstawie, by jego współczynniki były stosunkowo małe, a wyrazy skrajne były wielokrotnościami reszty z dzielenia przez p takimi, by wyraz skrajny a[0] = m*n \equiv (N%p) (mod p). Dobieram je tak, by 0<=m,n<p oraz p^2 | (N-mn). Oznacza to, że m, n są cyframi jedności dzielników liczby N zapisanymi w systemie p. 

np. N = 8934053 \equiv 5 (mod 16), oraz można tę wartość przedstawić jako palindromy 

N = [85, 85, 11773, 85, 85]_{16}

oraz 

N = [165, 0, -7342, 0, 165]_{16}

W tej drugiej postaci mamy odpowiednie wartości 165 = 15*11, zatem jest to iloczyn palindromów 

N = [15, x, 15]_{16} * [11, y, 11]_{16}

Mnożąc te palindromy uzyskujemy układ kongruencji, z których można poszukiwać zmiennych z oraz y. Ale jest to także układ wejściowy dla utworzenia układu równań, z których można wyznaczyć brakujące współczynniki dzielników... Zamierzam umieścić wkrótce...

Wymuszanie postaci dzielnika

 Alert cyberbezpieczeństwa obniżony, choć niektóre moje wyniki sugerują, że istnieje nie tylko wielomianowy algorytm rozkładu, ale nawet nieco szybszy (stosowałem bisekcję do aproksymacji wartości dzielnika). 

Zdecyfowałem się na wymuszanie specjalnej postaci któregoś z dzielników rozkładanej liczby, co prowadzi do układów równań. Oszacownie rozwiązań tych równań mocno przyspiesza lokalizację dzielników. 

Kiedy stosowałem podane już parokrotnie kryteria: suma cyfr w systemie o podstawie o 1 mniejszej jest bliska tej podstawie systemu, naprzemienna suma cyfr w systemie o podstawie o 1 większej jest blika zeru (wielokrotności podstawy), uzyskałem dobre i mocne wyniki. Najwięcej kłopotu sprawiają przeniesienia między cyframi. 

Specjalna postać dzielnika zmniejsza to "narastanie przyrostów", dzięki któremu mnożenie dużych liczb uchodzi za trudne do odrócenia. 

Jednym ze sposobów jest przedstawienie wartości jako palindrom nad systemem. Jest to wielomian o współczynnikach całkowitych, którego współczynniki od początku i od końca są równe sobie. Przedtawienie liczby nad systemem binarnym moze się odbyć na wiele sposobów, im większa podstawa, tym mniej możliwości, a po przekroczeniu pewnej wartości podstawy, pojawiają się liczne i duże wartości ujemne. Cyfra jedności palindromu jest silnie związana z resztą z dzielenia przez podstawę, zaś przekształcenia tożsamosciowe "przenoszą" spore wartości między poszczególnymi cyframi. Blokuje to zwykłe przeniesienia. Iloczyn dwu palindromów jest palindromem, zaś iloczyn palindromu przez dowolną wartość też wykazuje się powtarzalnością składników.

Aby nie być gołosłownym, wymuszając postać N = p*q = [a,b,c] * [1,f] zapisaną w trzech sąsiadujących ze sobą systemach pozycyjnych, dzielnik był w miejscu, gdzie dokładnie co trzecia postać jest ekstremum lokalnym obu wspomnianych cech podzielności. Związki miedzy współczynnikami tych trzech zapisów w systemach pozycyjnych wygenerowały proste równania nieliniowe, z których można było oszacować wartości. Szacując znak f bardzo szybko zbliżyłem się do dzielników. Nie było mowy o zbieżności, o ile nie brać pod uwagę (nieznanej przed znalezieniem rozkładu) różnicy p-q.

I tak, w nieprzyzwoicie krótkim przebiegu rozłożyłem 

1 512 264 139 457 755 655 776 587 407
= 33 084 353 498 509 * 45 709 345 341 323

I widzę kolejne możliwości skracania obliczeń... Także przez układy równań...

Sito dla rozkładu, ale już nie przeglądem zupełnym

 Stosowałem sito Eratostenesa dla podstawy systemu, dla cyfry dziesiątek. Zostały znalezione przyspieszacze obublikowane w poprzednim poście. 

A teraz przesunąłem obszar rozkładu w pobliże liczby rozkładanej, oraz zajmuję się niezmiennikiem

N = a*p+b

dla którego stosuję własności: 

- b jest dzielnikiem wtedy i tylko wtedy gdy b | a*p, drugim jest np. a+1 w systemie o podstawie p
maksymalny możliwy dzielnik to a (które zresztą maleje w trakcie obliczeń lub wtapia się z p - gdyż mamy dowolność wyboru systemu pozycyjnego).

- w każdej iteracji dla pewnej wartości rosnącej k wyliczam (a-k)*(p+k), co zwiększa b zachowując niezmiennik. Przeskakuję podstawy np bisekcją, dopóki b nie zrówna się z a. Dystans przeskakiwanych wartości jest funkcją słabo malejacą. Podejście to odrzuca liczby pierwsze za duże by być dzielnikami.
Jeśli w podanym kroku uzyskam nierówność b>a, przechodzę na sąsiedni system formułą: 

N = a*p+b = a*(p+1)+(b-a) = a*p'+b'

- jeśli interesują mnie małe liczby pierwsze, stosuję sito dla liczby złożonej a*p-K(), gdzie K() jest ciągłym przerzucaniem wartości podzielnych przez małe liczby  pierwsze na coraz większy iloczyn a*p. Wartości przesuwane są po to, by nie stosować w sicie kroku +1, ale wyznaczony przez kolejną lokalnie największą wartość b. W ten sposób badam równocześnie pierwszość przez małe, jak i przez bardzo duże liczby pierwsze. Krok sita nie jest stały! 

- jeśli w rozkładzie a*p pojawi się większa liczba pierwsza, jest ona ignorowana. Dotychczasowe doświadczenie z przebiegu sit wskazuje, że takie liczby stosunkowo szybko zaczną się przyznawać do swej pierwszości, a jako większe niż b ograniczone maksymalną wartością a, nie będą dzielnikami.  

 

Praktycznie dla liczby nieparzystej możemy nawet zacząć od liczby złożonej 2*a*a+a bliskiej N. Wtedy niejako dołączamy gratis system binarny, co dodatkowo zmniejsza krotność iteracji.Sprawdzanie pierwszości może być z dwu stron - od małych i gigantycznych wartości.

Wyjątkowo nie podaję przykładu i przebiegu - obawiam się to pokazywać osobom spoza branży.

Herystyki przyspieszające rozkład liczby w przeglądzie zupełnym

 Mimo aktualnych trudności (remont + wykluczenie) nabieram doświadczenia oglądając przebieg sita, które w jednej iteracji początkowej nie sprawdza statystycznie ułamka liczby pierwszej (liczba pierwsza pojawia się dopiero po pokonaniu dystansu do kolejnej), lecz na iterację napotykam kilka liczb pierwszych, z których część często nie jestem w stanie od razu rozpoznać (iloczyn kilku zbyt dużych liczb pierwszych nie jest odróżnialny od liczby pierwszej). To się zmienia, gdy daną liczbę pierwszą spotkam ponownie. 

Ale przebieg sita nasuwa mi przyspieszacze: np. istnieje przedział, w którym można przeskakiwać część iteracji (budowa liczby [1,b,c]_p, gdzie (p-1) jest bliskie (1+b+c) sugeruje kolejną podejrzaną o dzielnik pozycję przez przesunięcie o iloraz p/(b-1) ). W ten sposób sprawdzałem wręcz pierwszość liczb rzędu pięciu milionów, gdy największą wychwytywaną w danej iteracji była liczba rzędu 3-4 milionów (kwadrat dystansu zbliżał się do 2000). 

Teraz zmodyfikowałem wyrażenie sita, co jeszcze przyspieszyło obliczenia. Przesunąłem się na zakres nieco ponad pierwiastek kwadratowy z liczby rozkładanej

N = [a, b] _ p, a bliskie sqrt N

gdzie a*p+b = N, a maleje o 1 do połowy swej początkowej wartości, p rośnie (na ogół też o 1), b tworzy wykres piłokształtny przedziałami rosnący. Sito Eraostenesa stosuję do cyfry 'dziesiątek' a, ignorując złożoność jej dzielników (dystans będący licznikiem iteracji i tak wskaże pośrednio dzielniki). 

A teraz kolejna herurystyka, która zapowiada się interesująco. Najpierw przebieg teoretyczny: 

Bierzemy iloczyn dwu liczb nieparzystych b*d, który jest bliski liczby rozkładanej N: 

b*d - N + r = 0,  b >= d

Wartość d zapisuję we wszystkich dostępnych kolejnych systemach liczbowych o cyfrze 'dziesiątek' 1: d = [1,e]_(2*p). Sprawdzam czy  (2*p+1) dzieli r+(e-1)*b. 

Przejście na sąsiedni system: e-=2; p+=2; dla podzielności wystarczy zmodyfikować wartość o stałą 2b. Największe możliwe e to połowa (d-1)/2, gdyż z założenia b i d są nieparzyste. 

Jeśli mamy podzielność, 2*p+1 jest dzielnikiem, drugi uzyskamy w bardziej skomplikowany sposób, z sumy b oraz równomiernie rozlokowanej na pozycje wartości r+(e-1)*b. Po to nam była potrzebna podzielność!

Dlaczego to działa? 

Konwersje są niezmiennicze względem wartości liczbowych. Jeśli jeden czynnik traktujemy jako stały (b), a drugi d podlega konwersjom, mamy do czynienia z wyrażeniem [1*b, e*b] _ (2*p). Tu uwzględniana jest nieparzystość bardzo dużego b oraz fakt, że d zostało dobrane jako większe niż szukany dzielnik. Każdą liczbę można sprowadzić do postaci [1, e]_p wykorzystując wielokrotnie zwiększanie systemu o 1 oraz jego podwajanie. Nie wiemy jak to zrobić bez konkretnych wartości, dlatego potrzebujemy przeglądu. 

Liczba [1, 1]_ (2*p) jest podzielna przez 2*p+1, bo jest to inny zapis 1*(2*p)+1. Zabieramy nadmiar z pozycji jedności (tu (e-1)*b) oraz w sumie z r sprawdzamy, czy uda się to rozprowadzić na wszystkich pozycjach.  

Kiedy r nie jest ujemne, lecz dodatnie, znaleziona podzielność w przypadku testowym znalazła się tuż poza 'poprawnym' zapisem pozycyjnym liczby. Przy ujemnym podobnie. Ale i odległość między dzielnikami była spora.  

Przykład liczbowy, dla liczb pierwszych i niektórych złożonych nie znajdujemy podzielności: 

253 = 17 * 15 - 2

Zapisujemy 15 = [1, 7]_8 = [1, 5]_10 = [1, 3]_12 = [1, 1]_14 . 

Sprawdzamy kolejno odpowienie podzielności:
-2+(7-1)*17 = 100 = 9*(8+1)+1,
-2+(5-1)*17 = 100-34 = 66 = 6*(10+1)+0 dzielnik 11
-2+(3-1)*17 = 66-34 = 32 = 2*(12+1)+6
-2+(1-1)*17 = -2 = 0*(14+1)-2

Liczba złożona o dzielniku 11, drugim jest 17+66/11 = 23. 

259 = 17 * 15 + 4 = 17 * 17  - 30

Po rozpisaniu (jak wyżej) w pierwszej wersji potrzebowalibyśmy [1, 9]_6 do znalezienia dzielnika 7, gdyż dopiero 8*17+4 jest wielokrotnością 7. A to nie jest poprawna liczba. W drugiej wersji 17*17-30 podobnie [1,9]_8.

Gra paragrafowa, przykładowa implementacja w C++

Budowa gry paragrafowej wydaje się prosta: opis, wybór opcji i przejście dalej.

Zamierzam przedstawić swoją propozycję implementacji w C++. 

 

Najpierw założenia: 

Każda lokacja to inna funkcja. Istnieje kilka lokacji dostępnych z dowolnej innej, nazwijmy je 'ogólne'. Są to np.: opcje, finisz, pomoc, statystyki w przypadku gdy coś zbieramy i używamy. Dostęp do tych funkcji jest z petli głównej programu, a przy ich opuszczaniu wracamy do lokacji trzymanych przez wskaźnik. 

Występuje kilka zmiennych statystycznych pokazujących przebieg gry. Wydają się one globalne w programie, gdyż każda z lokacji może, ale nie musi z nich korzystać. 

W mojej implementacji lokacje są trzymane wskaźnikami do funkcji

int (*f) ();

Funkcje zwracają kod wciśniętego klawisza char przekonwertowany do int, co umożliwia dostęp do lokacji ogólnej lub wyście z programu. Wychodzę z gry przez ESC.

Ciało funkcji main(void) jest proste: 

f = enter; // funkcja enter() wprowadza do gry

int i = 0; // zmienna do której odkładam wynik f()

while(1) {

  i = f(); 

  if( i ) i = finisz(); // f=finisz nie pozwala wrócić do opuszczonej właśnie lokacji

  else // ... wywołania lokacji ogólnych

  if( ESC== i ) break; 

}

return 0; 

Ciało lokacji jest nieco bardziej rozbudowane, wszak bywa rozgalęzieniem. Ale można ogólnie wydzielić następujące części (Nr to liczba konkretnej funkcji): 

int nazwaNr () {

  listwa(); // czyszczenie ekranu i podanie opisu stałego (statystyki: zasoby itp.)

  opisNr; // co ma poczytać gracz w tej lokacji

  dzialanieNr; // jeśli może coś zrobić

  int c =  getch; // pobranie komendy od gracza

  nagroda(); // jeśli statystyki mają ulec zmianie

  f = wyborNr(c); // wskazanie nowej lokacji do której gracz przejdzie, nawet gdy c wskaże lokacje ogólną

  return c; // i po zwiedzeniu lokacji ogólnej wskazanej przez c gracz pójdzie do f()

}; 

Jeśli w kodzie piszę lokacje od ostatniej do pierwszej, na ogół większość jest widocznych dla siebie, i nie trzeba ich dodatkowo deklarować. Wyjątkiem są rozgałęzienia kilku niezależnych ścieżek. Lokacje węzłów zbiorczych muszą być wcześniej zadeklarowane.

Kiedy rozkładana liczba jest dwucyfrowa

 Szukanie dzielników liczby N zapisanej w systemie o podstawie większej niż pierwiastek kwadratowy z liczby wydaje się mijać z celem. Tyle przypadków... I co z tego, że istnieje system, w którym liczba N = s*q, s>q ma szczególnie prostą postać:

N = q q _ {s-1}

Jednak na ogół dzielnik można znaleźć zanim napotkamy tę postać. Korzystając z sita wspominanego parę wpisów wcześniej, na dzielnik N natrafimy stosując jeden ze sposobów: podstawa systemu oraz wyraz wolny mają wspólny dzielnik; dystans od wartości startowej jest tym dzielnikiem; dystans rozkłada iloczyn paru dużych liczb pierwszych, wyławiając dzielnik.

W systemie o podstawie odrobinę większym niż pierwiastek kwadratowy, postaci 

N = a b _ {2p}

wartość a jest bliska temu pierwiastkowi kwadratowemu oraz maleje ze wzrostem podstawy systemu. Maleje aż do jedynki, ale możemy zatrzymać szybciej, po przejrzeniu połowy przypadków. Wykorzystamy fakty: 

- wśród k kolejnych liczb naturalnych istnieje dokładnie jedna, która dzieli k; 

- liczba pierwsza mniejsza niż k występuje co najmniej raz w przedziale [k, 2k); 

- iloczyn dwu dużych liczb pierwszych w odpowiednim systemie niedziesiątkowym ma postać N = (r*q) q  _ {2p}, gdzie q jest liczbą pierwszą, oraz drugi z dzielników jest równy s=2rp+1. 

Zmodyfikujemy sito opisane przy liczbach trójcyfrowych na potrzeby liczb dwucyfrowych. Tam sito Eratostenesa działało dla podstaw systemów, teraz  będzie obsługiwało cyfrę dziesiątek. Wartość cyfry jedności będzie oscylowała wokół cyfry dziesiątek. Cyfra dziesiątek maleje, a podstawę systemu trzymamy parzystą.

1) Wybieramy wartość startową bliską pierwiastka kwadratowego z N, zapisujemy ją jako liczbę dwucyfrową a b _ {2p} o podstawie parzystej. 

2) Do wartości a stosujemy sito Eratostenesa, czyli zapamiętujemy kolejne dzielniki d, które wskazują kolejne, coraz mniejsze wielokrotności znajdowanych liczb pierwszych a-d. Połowę początkowej wartości a zapamiętujemy jako wartownika, oraz inicjujemy dystans d od punktu startowego. 

3) Pętla. Zamierzamy przenieść jedynkę z a zwiększajac równocześnie cyfrę jedności b. Jeśli uzyskana wartość jest większa niż a, zabieramy parzystą wielokrotność a zwiększając podstawę systemu (konwersja na system o większej podstawie parzystej, by b było stosunkowo blisko a). Zwiększamy dystans o 1, oraz sprawdzamy, czy w wyniku tzw. trial division przez przyczepione sitem małe liczby pierwsze wobec a pojawiła się liczba pierwsza, podobnie jsk opisano w poprzednim poście. Dystans też może okazać się liczbą pierwszą, traktowaną jako znajdowana. Jeśli rozpoznamy liczbę pierwszą, sprawdzamy jej podzielność przez cyfrę jedności b, co może zakończyć się powodzeniem w znalezieniu dzielnika i zakończeniem. Takie wartości możemy kasować jako już niepotrzebne. 

4) Kontunuujemy przebieg sita, aż znajdziemy dzielnik. Kiedy a zmaleje do wartości wartownika, nie znaleźliśmy dzielników, liczba jest pierwsza. 

Pętla dla liczb pierwszych wykona się tyle razy, ile wynosi połowa wartości punktu startowego. Oprócz trail division jest dzielenie cyfry jedności przez rozpoznawane liczby pierwsze. Dopóki nie rozpoznamy prawidłowo gigantycznych liczb pierwszych w sicie, chyba potrzebujemy pamiętać te postaci. W innym przypadku do sita mogą trafiać liczby złożone. Kiedy dystans będzie tak duży, że jego kwadrat przekroczy a, każda napotkana większa wartość jest pierwsza, dystans przestaje być potrzebny. Mamy tyle dzieleń cyfr jedności, ile jest liczb pierwszych. 

Dla liczby złożonej pętla często zatrzyma się, zanim dystans osiągnie wartość mniejszego z dzielników. 

 

Sprawdziłem dodatkowe przyspieszenie, stosując cechy podzielności przez p-1 oraz p+1. Wartości w sicie są zapisywane jako pary (wartość o podstawie p=4k, produkt), w którym produkt przekształca się w postać kanoniczną wartości. Opisana wcześniej heurystyka jest modyfikowana, i raczej nie nadaje się do obliczeń ręcznych. Ale maszynowo może być wydajniejsza, bardziej dopasowana dla obliczeń współbieżnych rozproszonych. Wartość dystansu nieco traci na znaczeniu. Liczby pierwsze ujawniają się nawet przy wstawianiu nowej wartości do sita,

Funkcja sumy cyfr dla wielu liczb trójcyfrowych i dwucyfrowych jest funkcją piłokształtną. Gdy cyfra setek jest już wystarczająco mała i nie zmienia się podczas konwersji, cyfra dziesiątek jest od niej znacznie większa (co najmniej ośmiokrotnie), można łatwo oszacować system, w którym suma ta znów będzie blisko podstawy. Niech n = a*p*p + b*p + c. Iloraz p/(b-a) wyznacza przesunięcie podstawy, przy której znów a+b+c approx p. Stosuję to do sprawdzania pierwszości wartości odkładanych do sita, gdy liczba może być półpierwsza, czyli jest iloczynem dwu liczb pierwszych. Tempo zmiany podstaw z liniowego (x4) przechodzi w wykładnicze. A w ostatniej iteracji się na ogół sypie, ale wtedy mam heurystykę: kwadrat wyrazu wolnego nie przekracza wymaganego przesunięcia wartości podstawy systemu.

Szukanie bardzo dużych dzielników, propozycje

 Już zmieniono tu grafikę na taką, w której trudniej mi się znaleźć. Tylko jeszcze czekam tu na blokadę logowania się. Mam to już na kontach w Linkedin oraz na nowo otwartej skrzynce pocztowej. Stara jest technicznie blokowana, a na nową nie mogę się zalogować z racji nieoczekiwanego błędu.

Zamierzam tu podsumować swoje jeszcze nie przetestowane do końca spostrzeżenia. Nie wiadomo, jak dalej potoczy się moje narastające wykluczenie... 

Przypomnę:

Cyfrą jest nieujemna liczba ograniczona z góry przez podstawę systemu. Zatem, dla systemów o podstawach rzędu milionów, cyframi stają się liczby nawet rzędu tysięcy w systemie dziesiątkowym. Dalej używam pojęć  np. 'cyfra setek' dla wskazania pozycji cyfry w liczbie. 

Dla odpowiednio dużej podstawy systemu p, każdą odpowiednio dużą liczbę można zapisać jako trójcyfrową [a, b, c]_p. I o takich będę dalej pisać.

Jeśli liczba n = p*q, p<q, to można zapisać liczbę q w systemie o podstawie p dla pewnych danych parametrów  a, b:

q = [a, b]_p

oraz n = p*q = [a, b, 0]_p .

Zobaczmy, co się stanie z tą wartością, gdy zmienimy podstawę systemu o 1, czyli zamiast p zastosujemy podstawy systemów: p-1, p+1, bez zmiany wartości liczby n (co sztucznie powiększone, odejmiemy itp.): 

[a, b+2a, a+b+0] _ {p-1}

[a, b-2a, a-b+0] _ {p+1}

Przywracając cyfrę jedności c=0, uzyskujemy warunki dla podstaw systemów sąsiadujących z systemem o podstawie dzielnika: w jednym suma cyfr jest równa podstawie systemu (por. cecha podzielności przez 9), w drugim naprzemienna suma cyfr jest równa 0 (por. cecha podzielności przez 11). 

Właściwie powinienem pisać, że dostaję całkowite wielokrotności podstawy, ale dla liczb nieparzystych n o bardzo dużych podstawach mamy redukcję do tych warunków. A dodatkowo, funkcja sumy cyfr liczby trójcyfrowej w kolejnych systemach liczbowych jest funkcją przedziałami monotoniczną. Rozmiar 'ząbków' rośnie wraz ze wzrostem wartości. Aż się narzuca algorytm wyżarzania lub bisekcji dla szukania wartości podstaw okalających dzielnik.

Kolejnym podejściem, wykładniczym względem krotności cyfr zapisu binarnego liczby, jest stosowanie tych cech, gdy liczbę zapiszemy najpierw jako iloczyn 

n = 4*d+2*e+1 , 

e jest cyfrą dziesiątek liczby n w systemie binarnym, całe wyrażenie jest wielomianem (d jest za duże by być cyfrą w binarnym), oraz traktując jako liczbę trójcyfrową mamy dwie rekursywne gałęzie, w pierwszej podwajamy podstawę systemu, w drugiej przechodzimy na system o 1 większy i też podwajamy podstawę. Póki mamy odpowiednio duże 'cyfry setek', sprawdzamy sumę i naprzemienną sumę współczynników, jak wyżej. 

Czyli rekursja przebiega: 2 -> (4 -> 8 -> ...  4+1=5 -> ...) 2+1=3 -> ...