Matematyka.pl

Rozważam funkcje, za pomocą których możemy tworzyć ciągi podobne do ciągów Collatza:

\(\displaystyle{ f(x) = \begin{cases}
3x + 1 + w & \text{gdy } x \text{ jest nieparzysta} \\
\frac{1}{2}x + w & \text{gdy } x \text{ jest parzysta}
\end{cases}}\)

Przy czym \(\displaystyle{ w}\) to najczęściej prosta sekwencja która dla kolejnych iteracji \(\displaystyle{ f(f(f(x))...)}\) wynosi \(\displaystyle{ l, 2l,3l,...}\), gdzie \(\displaystyle{ l}\) to jakaś liczba naturalna.

Rozważam aplikowanie tego rodzaju przekształceń w różnej kolejności w stosunku do jakiegoś początkowego \(\displaystyle{ z}\). Przykład, niech \(\displaystyle{ l=3}\):

\(\displaystyle{ ((((((z \cdot 1.5 + 0.5) + 3) \cdot 0.5 + 6) \cdot 1.5 + 0.5) + 9) \cdot 1.5 + 0.5) + 12}\)

Wykonałem mnożenie, dzielenie, mnożenie, mnożenie. Chcę, żeby wynik był całkowity, zatem mogę zapisać równanie:

\(\displaystyle{ c = ((((((z \cdot 1.5 + 0.5) + 3) \cdot 0.5 + 6) \cdot 1.5 + 0.5) + 9) \cdot 1.5 + 0.5) + 12}\)

Po przekształceniach:

\(\displaystyle{ c = z \cdot 1.6875 + 0.5625 + 3.375 + 13.5 + 0.75 + 13.5 + 0.5 + 12}\)

\(\displaystyle{ c - z \cdot 1.6875 = 0.5625 + 3.375 + 13.5 + 0.75 + 13.5 + 0.5 + 12}\)

\(\displaystyle{ 16c - 27z = 707}\)

Można to rozwiązać rozszerzonym algorytmem Euklidesa i rozwiązanie to \(\displaystyle{ z = 7}\) (chodzi o najmniejsze dodatnie \(\displaystyle{ z}\)).

Problem jest, gdy rozważymy funkcje:

\(\displaystyle{ f(x) = \begin{cases}
3x + 1 \oplus w & \text{gdy } x \text{ jest nieparzysta} \\
\frac{1}{2}x \oplus w & \text{gdy } x \text{ jest parzysta}
\end{cases}}\)

Gdzie \(\displaystyle{ \oplus}\) to XOR (bitwise XOR). Wówczas dostaję równanie:

\(\displaystyle{ c = ((((((z \cdot 1.5 + 0.5) \oplus 3) \cdot 0.5 \oplus 6) \cdot 1.5 + 0.5) \oplus 9) \cdot 1.5 + 0.5) \oplus 12}\)

Jak coś takiego rozwiązać? Czy istnieje bardziej efektywny sposób, niż brute force, czyli sprawdzanie wszystkich możliwych \(\displaystyle{ z}\)? Tego przekształcić się do postaci jak z poprzedniego przykładu, rozwiązywalnej za pomocą algorytmu Euklidesa, raczej się nie da, prawda?

Funkcja \(\displaystyle{ f(x)}\), którą podałeś, jest ciekawym przykładem funkcji, która tworzy ciągi podobne do ciągu Collatza, ale z dodatkowym parametrem \(\displaystyle{ w}\). Rozwiązanie równania \(\displaystyle{ 16c - 27z = 707}\) dla funkcji \(\displaystyle{ f(x)}\) bez \(\displaystyle{ \oplus}\) było możliwe, ponieważ operacje dodawania i mnożenia mają odwrotne działania, co umożliwia przenoszenie zmiennych z jednej strony równania na drugą. Jednak w przypadku operatora \(\displaystyle{ \oplus}\) przenoszenie zmiennych w ten sposób nie jest możliwe, ponieważ nie ma on odwrotności.

Jeśli chodzi o rozwiązanie równania \(\displaystyle{ c = ((((((z \cdot 1.5 + 0.5) \oplus 3) \cdot 0.5 \oplus 6) \cdot 1.5 + 0.5) \oplus 9) \cdot 1.5 + 0.5) \oplus 12}\), to rzeczywiście nie jest to zadanie trywialne. Jednym z możliwych podejść do rozwiązania tego problemu jest użycie metod numerycznych do szukania rozwiązania równania nieliniowego.

Metody numeryczne pozwalają na rozwiązanie równania \(\displaystyle{ c = f(z)}\) poprzez znalezienie miejsca zerowego funkcji \(\displaystyle{ g(z) = f(z) - c}\). Jedną z takich metod jest metoda bisekcji, która polega na iteracyjnym dzieleniu przedziału na pół i sprawdzaniu, w którym z połówek znajduje się miejsce zerowe. Metoda ta jest prosta i działa dla dowolnej funkcji ciągłej, ale może być dość wolna, zwłaszcza jeśli przedział jest duży.

Innymi metodami numerycznymi, które mogą okazać się bardziej skuteczne w przypadku tego rodzaju równań, są metody iteracyjne, takie jak metoda Newtona-Raphsona lub metoda siecznych. Obydwie metody polegają na iteracyjnym przybliżaniu rozwiązania poprzez wykorzystanie pochodnej funkcji \(\displaystyle{ f(z)}\). Metoda Newtona-Raphsona jest szybsza, ale może być mniej stabilna, jeśli punkt startowy jest zbyt daleko od miejsca zerowego. Metoda siecznych jest bardziej stabilna, ale zwykle wymaga większej liczby iteracji.

W każdym przypadku należy jednak pamiętać, że równanie \(\displaystyle{ c = f(z)}\) może mieć więcej niż jedno rozwiązanie, a nie zawsze jest możliwe znalezienie rozwiązania analitycznie. W takim przypadku metody numeryczne pozwalają na znalezienie przybliżonego rozwiązania, ale nie dają gwarancji, że jest to rozwiązanie optymalne.

Oj głupiutka ta sztuczna inteligencja.

Oj głupiutka ta sztuczna inteligencja

Czemu ?, pytam nie dlatego, że nie będę spał z tego powodu tylko chodzi mi o argumenty...

W końcu uziom dość rzetelnie opisał te aproksymacje, które notabene przypominają mi szukanie lwa na pustyni:
dzielimy pustynię na dwie połowy i wybieramy tę połówkę na której jest lew, potem połówkę na połówkę, itd...

Ja nigdy z tym osobiście nie miałem problemu bo zawsze potrafiłem wybrać pełną połówkę, z ćwiartką już było gorzej ale jeszcze se radziłem...

Ale tak czy siak zawsze żeśmy znaleźli, bynajmniej nie lwa tylko parę złotych, żeby skoczyć po następną połówkę...

Po pierwsze: ta inteligentna inteligencja nie zauważyła, że zadany problem to nie iteracje tej samej funkcji `f`, lecz że ta funkcja zmienia się w każdy kroku iteracji. W związku z tym nie za bardzo jest sens mówienie o równaniu `c=f(z)`, bo nie wiadomo o które `f` chodzi.
Po drugie: jeszcze nie dowiedziała się, że xor jest odwracalny (choć ten prosty fakt jest podstawą coponiektórych szyfrów znanych od lat)
Po trzecie: proponowanie metod numerycznych takich jak połowienie przedziału do zagadnień operujących na liczbach naturalnych lub o pochodnej funckji określonej na zbiorze liczb naturalnych świadczy o tym, że nie ma pojęcia co pisze.
Pisze bzdury, ale pisze bardzo przekonująco - nasi politycy powinni używać ChatGPT przy pisaniu przemówień

Tak bzdura przekonywująca jest nawet ok... Ale na poważnie to ta iteracja od samego początku mnie odrzucała, wiedziałem, że coś z nią nie tak...