2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Доказать бесконечность множества решений в натуральных
Сообщение05.08.2018, 23:35 
Аватара пользователя


01/12/11

8634
а) Доказать бесконечность множества решений в натуральных числах уравнения
$$x^4+y^4=z^5-t^3$$

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

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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 02:17 


05/09/16
8059
Пока оставлю тут несколько найденных решений
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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 02:35 
Аватара пользователя


07/01/16
908
Аязьма
(а) $x=y=4a^{15},z=4a^{12},t=8a^{20},\forall a\in\mathbb{N}$

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 08:37 


05/09/16
8059
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}$
Ну и остальные серии так же.
А простота ни взаимная ни совокупная пока не просматривается.

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 08:39 
Заслуженный участник
Аватара пользователя


09/05/13
7877
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}$

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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 10:34 


05/09/16
8059
Ну и функция которая ищет решения.
На вход подаём максимальное $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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 11:49 


05/09/16
8059
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, думаю как исправить.

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение06.08.2018, 12:01 
Аватара пользователя


07/01/16
908
Аязьма
wrest в сообщении #1330858 писал(а):
Собсна вот: x=96 y=166 z=61 t=69
вот еще бы таких бесконечно дофига найти :-)

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение07.08.2018, 14:31 


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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение07.08.2018, 18:43 


05/09/16
8059
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$ замедляет.

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение07.08.2018, 23:05 
Аватара пользователя


01/12/11

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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение07.08.2018, 23:20 
Заслуженный участник
Аватара пользователя


16/07/14
4040
Москва
Не очень понимаю логику вашего кода. Моя реализация на плюсах пробегает от 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;
}
 

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение07.08.2018, 23:53 


05/09/16
8059
mihaild
Я вместо того чтобы просто проверить специальной функцией является ли число кубом, перебираю несколько кубов :facepalm: с сравниваю с этим числом типа в надежде что какой-то подойдет :oops: :lol: И это внутренний цикл который съедает основное время.
Чувствовал я, что что-то не так с этим, но никак не мог понять что именно.

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

 Профиль  
                  
 
 Re: Доказать бесконечность множества решений в натуральных
Сообщение08.08.2018, 21:10 
Заслуженный участник
Аватара пользователя


16/07/14
4040
Москва
Еще решения (при которых $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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модератор: Модераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group