Znajdowanie całkowitych rozwiązań równania z xorowaniem
: 8 lut 2023, o 03:24
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?
\(\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?