Доказать бесконечность множества решений в натуральных

[Ktina]

а) Доказать бесконечность множества решений в натуральных числах уравнения

$$x^4+y^4=z^5-t^3$$

б) А если $x, y, z, t$ должны быть взаимно простыми в совокупности?

в) А попарно взаимно простыми?

[wrest]

Пока оставлю тут несколько найденных решений
x=3 y=8 z=9 t=38
x=4 y=4 z=4 t=8
x=96 y=166 z=61 t=69
x=144 y=287 z=100 t=1407
x=189 y=216 z=81 t=324

[waxtep]

(а) $x=y=4a^{15},z=4a^{12},t=8a^{20},\forall a\in\mathbb{N}$

[wrest]

waxtep в сообщении #1330834 писал(а):

(а) $x=y=4a^{15},z=4a^{12},t=8a^{20},\forall a\in\mathbb{N}$

$x=y=4a^{15n},z=4a^{12n},t=8a^{20n},\forall a,n\in\mathbb{N}$
Ну и остальные серии так же.
А простота ни взаимная ни совокупная пока не просматривается.

[Otta]

wrest в сообщении #1330845 писал(а):

waxtep в сообщении #1330834 писал(а):

(а) $x=y=4a^{15},z=4a^{12},t=8a^{20},\forall a\in\mathbb{N}$

$x=y=4a^{15n},z=4a^{12n},t=8a^{20n},\forall a,n\in\mathbb{N}$

Это одно и то же.

[wrest]

Ну и функция которая ищет решения.
На вход подаём максимальное $zmax$, на выходе -- печать найденных решений для $z \le zmax$
На моём хилом ноутбуке удалось перебрать до $zmax=200$
Перебор идет до $x,y \le \sqrt[4]{zmax^5};t \le \sqrt[3]{zmax^5}$
Возможно, надо как-то еще дооптимизировать, чтобы ускорить.

? Ktina128911(zmax)=my(n=0,ny=0, nz=0, z=0,z5=zmax^5,xmax=sqrtnint(z5,4),ymax=xmax,tmax=sqrtnint(z5,3));print("xmax=", xmax," ymax=",ymax," tmax=",tmax);print("Solutions:");for(x=1,xmax,n=x^4;for(y=1,ymax,ny=n+y^4;if(x>y,next);if(ny>z5,next);for(t=1,tmax,nz=ny+t^3;if(nz>z5,next);if(ispower(nz,5,&z),print("x=",x," y=",y," z=",z," t=",t)))));
? Ktina128911(200)
xmax=752 ymax=752 tmax=6839
Solutions:
x=3 y=8 z=9 t=38
x=4 y=4 z=4 t=8
x=96 y=166 z=61 t=69
x=144 y=287 z=100 t=1407
x=189 y=216 z=81 t=324

[wrest]

Ktina в сообщении #1330817 писал(а):

б) А если $x, y, z, t$ должны быть взаимно простыми в совокупности?

Собсна вот: x=96 y=166 z=61 t=69 -- если я правильно понимаю "простые в совокупности" получаются в том числе когда хотя бы одно из них простое. z=61 тут простое.

Пока суть да дело, запустил счет до zmax=300 (считалось чуть больше часа) и нашлась еще пара-тройка решений. Итого, по возрастанию z

x=4 y=4 z=4 t=8
x=3 y=8 z=9 t=38
x=96 y=166 z=61 t=69
x=189 y=216 z=81 t=324
x=144 y=287 z=100 t=1407
x=416 y=800 z=224 t=4992
x=278 y=874 z=226 t=464
x=729 y=729 z=243 t=6561
x=578 y=1156 z=289 t=4913

Вижу что программа сильно неоптимальна по самому внутреннему циклу, где перебирается t, думаю как исправить.

[waxtep]

wrest в сообщении #1330858 писал(а):

Собсна вот: x=96 y=166 z=61 t=69

вот еще бы таких бесконечно дофига найти

[wrest]

Докладываю: перебор до $z=400$ новых решений не выявил.

[wrest]

Ktina в сообщении #1330817 писал(а):

в) А попарно взаимно простыми?

Нашлось и такое x=799 y=2861 z=681 t=42919 Причем y там простое.

Заодно -- вот функция которая проверяет одно конкретное $z$ и печатает первое найденное решение, если оно есть (другие решения не ищет). Функция радикально ускорена (предыдущая считала с 300 до 400 аж 24 часа, а новая считает с 400 до 500 всего 5 минут, надеюсь что новая ничего не пропускает), и теперь можно проверять дальше.

(Оффтоп)

Ktina128911_bis(z)=my(n=0,ny=0, nz=0, z5=z^5,xmax=sqrtnint(z5,4)+1,ymax=xmax,tmax=sqrtnint(z5,3)+1,tstart=1);for(x=1,xmax,for(y=1,ymax,if(x>y,next(1));ny=x^4+y^4;if(ny>z5,next(2));tstart=sqrtnint(z5-ny,3)-1;if(tstart<1,next);for(t=tstart,tmax,nz=ny+t^3;if(nz>z5,next(2));if(nz==z5,print("x=",x," y=",y," z=",z," t=",t);return()))));

Запуск:

? Ktina128911_bis(408)
x=578 y=1156 z=289 t=4913
? ##
  ***   last result computed in 2,308 ms.
? Ktina128911_bis(672)
x=1232 y=2904 z=672 t=39920
? ##
  ***   last result computed in 5,132 ms.
? Ktina128911_bis(1000)
? ##
  ***   last result computed in 24,369 ms.

И да, нашлись еще решения, теперь проверено до $z=1000$:

x=1360 y=1632 z=408 t=9248
x=1458 y=1458 z=486 t=26244
x=1232 y=2904 z=672 t=39920
x=799 y=2861 z=681 t=42919

Если будут предложения по дальнейшему ускорению, велкам. Я еще дописывал там предвычисление всех кубов и 4-х степеней которые могут понадобиться, но оно ускоряет не слишком, а для больших $z$ замедляет.

[Ktina]

wrest
Большое спасибо!

[mihaild]

Не очень понимаю логику вашего кода. Моя реализация на плюсах пробегает от 400 до 500 за $0.5\, \text{---}\, 0.7$ секунды.
(из важных не совсем очевидных моментов - можно получить большое ускорение проверки, является ли число кубом, предварительно проверив это по какому-то модулю, по которому мало различных кубов)
При $z < 4000$ еще решения:
2704 7888 1320 43552
750 6875 1625 208750
13608 14256 2376 50544
12901 14647 2425 216407
972 18468 2592 87480
10368 25920 3456 311040
20736 20736 3456 497664
14250 25875 3500 329375

Используется синтаксис C++

#include <iostream>
#include <utility>
#include <ctime>
#include <vector>
#include <algorithm>

using TInt = uint64_t;

TInt gcd(TInt a, TInt b) {
    if (a < b) {
        std::swap(a, b);
    }
    while (b) {
        TInt tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

constexpr TInt int_pow(TInt x, TInt n) {
    TInt r = 1;
    for (auto i = n; i > 0; --i) {
        r *= x;
    }
    return r;
}

constexpr TInt upper_bound_root(TInt x, TInt n) {
    TInt r = 1;
    while (int_pow(r, n) < x) {
        r *= 2;
    }
    return r;
}

int main() {
    const TInt MAX_Z = 4000;
    const TInt MAX_T = upper_bound_root(int_pow(MAX_Z, 5), 3);
    const TInt MAX_X = upper_bound_root(int_pow(MAX_Z, 5), 4);

    static_assert(std::numeric_limits<TInt>::max() / MAX_Z / MAX_Z / MAX_Z / MAX_Z / MAX_Z > 0, "too big max_z");
    static_assert(std::numeric_limits<TInt>::max() / MAX_X / MAX_X / MAX_X / MAX_X > 0, "too big max_x");
    static_assert(std::numeric_limits<TInt>::max() / MAX_T / MAX_T / MAX_T > 0, "too big max_t");
    static_assert(int_pow(MAX_Z, 5) < int_pow(MAX_T, 3), "too small max_t");
    static_assert(int_pow(MAX_Z, 5) < int_pow(MAX_X, 4), "too small max_x");

    const TInt CUBES_MOD = 575757;
    std::vector<bool> cubesMod(CUBES_MOD, false);

    std::vector<TInt> cubes(MAX_T);
    for (TInt t = 0; t < MAX_T; ++t) {
        if (t % 1000000 == 0) {
            std::cerr << t << std::endl;
        }
        cubes[t] = t * t * t;
        cubesMod[cubes[t] % CUBES_MOD] = true;
    }
    std::vector<TInt> fourth(MAX_X);
    for (TInt x = 0; x < MAX_X; ++x) {
        fourth[x] = x * x * x * x;
    }
    std::cerr << cubes.size() << " cubes" << std::endl;
    clock_t start = clock();
    for (TInt z = 1; z < MAX_Z; ++z) {
        if (z % 100 == 0) {
            std::cerr << z << ' ' << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
        }
        TInt z5 = z * z * z * z * z;
        for (size_t i = 1; fourth[i] < z5; ++i) {
            auto t_pos = std::lower_bound(cubes.begin(), cubes.end(), z5);
            for (size_t j = i; fourth[i] + fourth[j] < z5; ++j) {
                TInt t_target = z5 - fourth[i] - fourth[j];
                if (!cubesMod[t_target % CUBES_MOD]) {
                    continue;
                }
                t_pos = std::lower_bound(cubes.begin(), t_pos + 1, t_target);
                if (*t_pos == t_target) {
                    TInt t = t_pos - cubes.begin();
                    std::cout << "found " << i << ' ' << j << ' ' << z << ' ' << t;
                    TInt numbers[] = {i, j, t, z};
                    bool coprime = true;
                    for (size_t ii = 0; ii < 4; ++ii) {
                        for (size_t jj = ii + 1; jj < 4; ++jj) {
                            if (gcd(numbers[ii], numbers[jj]) != 1) {
                                coprime = false;
                                break;
                            }
                        }
                    }
                    if (coprime) {
                        std::cout << " pairwise coprime";
                    } else if (gcd(z, gcd(j, gcd(i, t))) == 1) {
                        std::cout << " coprime";
                    }
                    std::cout << std::endl;
                }
            }
        }
    }
    return 0;
}
 

[wrest]

mihaild
Я вместо того чтобы просто проверить специальной функцией является ли число кубом, перебираю несколько кубов с сравниваю с этим числом типа в надежде что какой-то подойдет И это внутренний цикл который съедает основное время.
Чувствовал я, что что-то не так с этим, но никак не мог понять что именно.

Однако в ваших решениях есть два разных с одним и тем же $z$, а я думал так быть не может и останавливал проверку по первому нахождению решения.
Да, в 10 раз ускорилось.
Насчет модуля не понял - эта проверка подходит начиная с какого-то уже большого числа или для всех? И почему? И как найти именно тот по которому кубов мало?

[mihaild]

Еще решения (при которых $z^5$ еще влезает в $2^{64}$ - дальше для эффективности надо по паре модулей считать, видимо).

9248 18496 4624 1257728
648 25920 5400 1605744
18080 21696 5424 1634432
19683 39366 6561 2125764
20172 60516 6724 551368
10125 27000 6750 2379375
20250 60750 6750 607500