Rozwiązania kilku równań diofantycznych

[matemix]

Szukam rozwiązań takich równań:

\(\displaystyle{ \frac {a^2}{8} + \frac {ab}{8} + \frac {b}{4} = x_{1}}\)

\(\displaystyle{ 3 \cdot \frac {a}{8} + \frac {b}{8} = x_{2}}\)

\(\displaystyle{ 5 \cdot \frac {a^3}{8} + \frac {a^2 \cdot b}{8} + \frac {ab}{4} + \frac {b}{2} = x_{3}}\)

\(\displaystyle{ 7 \cdot \frac {a^2}{8} + \frac {ab}{8} + \frac {b}{2} = x_{4}}\)

Wszystkie zmienne \(\displaystyle{ x_{i}}\) to liczby całkowite. Zaś liczby \(\displaystyle{ a}\) i \(\displaystyle{ b}\) też powinny być całkowite. Ale chyba nie ma liczb całkowitych \(\displaystyle{ a}\) i \(\displaystyle{ b}\), które spełniałyby to równanie (o ile dobrze mi się wydaje, nie wiem jak to wykazać)? Zastanawiam się zatem, czy istnieją jakieś rozwiązania w liczbach całkowitych zespolonych?

[a4karo]

Dziwne zadanie:
wstaw za \(a,b\) dowolne liczby parzyste i wylicz \(x_i\)

[matemix]

Zrobiłem błąd, już poprawiłem. Teraz równanie wygląda nieco inaczej. Ale znalazłem rozwiązania:

\(\displaystyle{ a=-7}\)

\(\displaystyle{ b=-3}\)

Tyle, że metodą brute force. Jak rozwiązywać takie równania?

[a4karo]

A co w tych równania jest niewiadomą?

[matemix]

Chcę znaleźć \(\displaystyle{ a}\) i \(\displaystyle{ b}\), one są niewiadomą i mają to być liczby nieparzyste. Liczby \(\displaystyle{ x_{i}}\) nie są dla mnie istotne, ale też są niewiadomymi.

Podobny problem mamy z takim układem równań:

\(\displaystyle{ \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{8} + \frac {b}{2} = x_{1}}\)

\(\displaystyle{ 3 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{2}= x_{2}}\)

\(\displaystyle{ 5 \cdot \frac {a^4}{16} + \frac {a^3 \cdot b}{16} + \frac {a^2 \cdot b}{8} + \frac {ab}{4} + \frac {b}{2}= x_{3}}\)

\(\displaystyle{ 7 \cdot \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{4} + \frac {b}{2}= x_{4}}\)

\(\displaystyle{ 9 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{8} = x_{5}}\)

\(\displaystyle{ 11 \cdot \frac {a}{16} + \frac {b}{16}= x_{6}}\)

\(\displaystyle{ 13 \cdot \frac {a^3}{16} + \frac {a^2 \cdot b}{16} + \frac {ab}{8} + \frac {b}{4}= x_{7}}\)

\(\displaystyle{ 15 \cdot \frac {a^2}{16} + \frac {ab}{16} + \frac {b}{4}= x_{8}}\)

Ale tutaj, o ile nie zrobiłem błędu (gdy wyliczałem równania) nie ma rozwiązań dla \(\displaystyle{ a}\) i \(\displaystyle{ b}\) całkowitych, nieparzystych. Dlatego myślałem o rozwiązaniach zespolonych. Ale nie wiem jak to rozwiązywać. Sprawdziłem tylko wszystkie wariacje z powtórzeniami \(\displaystyle{ a}\) i \(\displaystyle{ b}\) w zakresie od \(\displaystyle{ -15}\) do \(\displaystyle{ 15}\) (i wstawiałem po kolei do wzorów, patrząc, czy każde równanie da wynik całkowity, czy nie). Dla wybranych liczb \(\displaystyle{ a+16p}\) do \(\displaystyle{ b+16q}\) lewe strony równań, przemnożone przez \(\displaystyle{ 16}\) dają te same reszty z dzielenia modulo \(\displaystyle{ 16}\). Dlatego wystarczyło sprawdzić rozwiązania w tym zakresie. Pytanie czy są jakieś rozwiązania np. dla liczb zespolonych? Tylko tutaj nieparzystość chyba nie będzie istotna.

[Gosda]

Byłoby trochę prościej pomóc, gdybyś zdradził, skąd się te równania wzięły.

[matemix]

Jak wyjaśnię skąd się biorą te równania to raczej nie będzie prościej. Badam złożenia pewnych permutacji. Sposób generowania tych permutacji jest następujący - obliczamy funkcję rekurencyjną:

\(\displaystyle{ f(x) = \begin{cases} \frac {a}{2} \cdot x+ \frac {b}{2} &\text{dla } x - nieparzystych\\\frac {x}{2} &\text{dla } x - parzystych \end{cases}}\)

Dla dowolnych całkowitych \(\displaystyle{ a}\) oraz \(\displaystyle{ b}\). W ten sposób generujemy ciągi liczbowe. Na wejściu są kolejne liczby naturalne. Ciągi te obliczamy dla jakiejś liczby iteracji, przyjętej z góry (np. \(\displaystyle{ 4}\) iteracje) i przekształcamy w pewien sposób. Zamieniamy każdą liczbę nieparzystą w wygenerowanym ciągu na \(\displaystyle{ 1}\) a każdą parzystą na \(\displaystyle{ 0}\). I w ten sposób otrzymujemy pewną liczbę binarną. Ale odczytujemy ją odwrotnie, od najmniejszej potęgi dwójki z lewej, do największej. Jeżeli wykonamy takie obliczenia na przykład dla liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 16}\), to otrzymamy pewną permutację. Konkretnie wziąłem dwie permutacje \(\displaystyle{ a=3}\), \(\displaystyle{ b=1}\) i \(\displaystyle{ a=3}\), \(\displaystyle{ b=-1}\). I pomnożyłem jedną razy drugą. Otrzymałem w wyniku tego trzecią permutację:

\(\displaystyle{ 11,6,9,12,15,2,13,8,3,14,1,4,7,10,5,0}\)

I teraz chcę ustalić jakie parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\) odpowiadają tej permutacji. Jakie wartości trzeba wstawić do funkcji, aby dostać dokładnie taką permutację. W celu ustalenia tego zapisałem te liczby binarnie (ale w odwróconej kolejności), na przykład \(\displaystyle{ 11}\) to \(\displaystyle{ 1101}\) i przyporządkowałem kolejnym jedynkom i zerom odpowiadającą im operację. Jeśli jakieś \(\displaystyle{ a}\) i \(\displaystyle{ b}\) dają taką permutację, to dla liczby jeden w takim ciągu rekurencyjnym musi zachodzić mnożenie, mnożenie, dzielenie, mnożenie i dać na wyjściu jakąś liczbę całkowitą. Dokładnie to jest zapisane w pierwszym równaniu. Równania napisałem tylko dla liczb nieparzystych, bo wydaje mi się, że można to tak uprościć i, jeśli znajdzie się rozwiązanie dla liczb nieparzystych, to będzie się zgadzać także dla parzystych.

[arek1357]

dla:

\(\displaystyle{ a=3 , b=1}\)

\(\displaystyle{ f(3)=5 , f(5)=8 , f(8)=4 , f4)=2 , f(2)=1, f(1)=2}\)

\(\displaystyle{ (3,5,8,4,2,1,2)}\)

Co to za permutacja albo czegoś nie rozumiem?...

[matemix]

Permutacja dla \(\displaystyle{ a=3}\) i \(\displaystyle{ b=1}\), dla \(\displaystyle{ 4}\) iteracji, dla zakresu liczb od \(\displaystyle{ 1}\) do \(\displaystyle{ 16}\), to:

\(\displaystyle{ (5,10,3,4,1,6,7,8,13,2,11,12,9,14,15,0)}\)

Ponieważ ciąg:

\(\displaystyle{ f(x) = \begin{cases} \frac {3}{2} \cdot x+ \frac {1}{2} &\text{dla } x - nieparzystych\\\frac {x}{2} &\text{dla } x - parzystych \end{cases}}\)

Dla liczby \(\displaystyle{ 1}\) wygląda tak:

\(\displaystyle{ 2,1,2,1}\)

Po zamianie na zera i jedynki mamy:

\(\displaystyle{ 1,0,1,0}\)

Co daje liczbę:

\(\displaystyle{ 2^0 \cdot 1 + 2^1 \cdot 0 + 2^2 \cdot 1 + 2^3 \cdot 0 = 5}\)

Tak naprawdę liczbę zamieniamy na \(\displaystyle{ 1}\) w zapisie binarnym, gdy była wykonana operacja typu \(\displaystyle{ \frac {3}{2} \cdot x + \frac {1}{2}}\), a gdy dzielenie przez \(\displaystyle{ 2}\), to zamieniamy liczbę na zero. W poprzednim poście źle się wyraziłem. Możemy pozamieniać równie dobrze wszystkie liczby nieparzyste na \(\displaystyle{ 1}\), jeśli za pierwszą iterację uznamy już zaimplementowanie liczby i wtedy obliczenia według funkcji rekurencyjnej wykonujemy tylko \(\displaystyle{ 3}\), ale dostajemy i tak liczbę o \(\displaystyle{ 4}\) bitach. Ale może lepiej pozostać przy zasadzie zamienia liczby na jeden lub zero, w zależności do tego czy było wykonane mnożenie, czy dzielenie. Idąc dalej na przykład element \(\displaystyle{ 13}\) permutacji będzie obliczony tak:

\(\displaystyle{ 20,10,5,8}\)

co daje:

\(\displaystyle{ 1,0,0,1 = 9}\)

Tak samo permutację wyznaczyłem dla \(\displaystyle{ a=3}\) i \(\displaystyle{ b=-1}\), wynosi ona:

\(\displaystyle{ (15,14,9,12,11,2,13,8,7,6,1,4,3,10,5,0)}\)

I pomnożyłem jedną razy drugą. Otrzymałem:

\(\displaystyle{ (11,6,9,12,15,2,13,8,3,14,1,4,7,10,5,0)}\)

Liczyłem, że znajdę jakieś parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\), dla których wyznaczę permutację w ten sam sposób i będzie odpowiadała wynikowi mnożenia. W ogóle próbuję zrozumieć zasady tego mnożenia i jaka logika za tym stoi. Tj. chciałbym umieć mając tylko parametry \(\displaystyle{ a}\) i \(\displaystyle{ b}\) umieć wyznaczyć wynik mnożenia dwóch permutacji, również zapisany jako \(\displaystyle{ a}\) i \(\displaystyle{ b}\), bez rozpisywania całych permutacji. Nie wiem jednak, czy istnieje w tym jakaś logika.