12 grudnia 2022

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.

21 października 2022

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).

19 września 2022

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. 

30 lipca 2022

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.

20 lipca 2022

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...

27 czerwca 2022

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ń...

17 lutego 2022

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.

25 stycznia 2022

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.