Может ли разность кубов быть квадратом?

[nnosipov]

B@R5uk в сообщении #1435082 писал(а):

В связи с найденным вами забавным фактом возникает вопрос: если зафиксировать вычитаемый куб, то количество решений ограничено?

Да, так как на эллиптической кривой (в данном случае заданной уравнением Морделла) может быть только конечное множество целых точек (частный случай теоремы Зигеля). Однако указать разумные границы для этих точек --- очень сложная задача.

[B@R5uk]

Поверю на слово. Полное осознание этого утверждения для меня непосильная задача.

А верно, что если квадрат может быть представлен в виде разности кубов, то это представление единственное? Пока эксперимент, вроде, подтверждает гипотезу.

(Оффтоп)

    480491² =   6897³ -   4598³  /  2299
    485184² =   9728³ -   8816³  /  304
    487711² =   9690³ -   8759³  /  19
    488775² =   6370³ -   2695³  /  245
    489061² = 282360³ - 282359³  /  1
    492128² =   6760³ -   4056³  /  1352
    492156² =  10710³ -   9954³  /  126
    492804² =   6318³ -   2106³  /  2106
    494400² =   6280³ -   1480³  /  40
    494893² =   6649³ -   3660³  /  61

[nnosipov]

B@R5uk в сообщении #1435088 писал(а):

А верно, что если квадрат может быть представлен в виде разности кубов, то это представление единственное?

То, что таких представлений для данного квадрата конечное число, очевидно (кстати, это конечное число может быть сколь угодно большим). Но почему должна быть единственность? Я бы поискал контрпример. По аналогии со знаменитым примером Рамануджана: $1729=1^3+12^3=9^3+10^3$ (домножив на $1729^3$, получим два представления точного квадрата в виде суммы двух кубов).

[B@R5uk]

nnosipov в сообщении #1435090 писал(а):

По аналогии со знаменитым примером Рамануджана

Не удивительно, что я его ещё не нашёл: $1729^2=2'989'441$. Время поиска до встречи этого числа оценивается в 14 часов!

-- 14.01.2020, 08:43 --

Перепроверил ещё раз. Досчитал до миллиона и перед самым миллионом как раз встретил две подряд идущие пары квадратов, представимых, как я и хотел:

    980882² = 107037³ - 107009³  /  7
    984064² =   9920³ -   1984³  /  1984
    985123² =  11328³ -   7847³  /  59
    988869² =  10633³ -   6076³  /  1519
    990584² =  11172³ -   7448³  /  3724
    990584² =  17005³ -  15789³  /  19
    998001² =   9990³ -    999³  /  999
    998001² =  11988³ -   8991³  /  2997
   1005043² =  44720³ -  44551³  /  13
   1006236² =  10890³ -   6534³  /  2178
   1008273² =  10108³ -   2527³  /  2527
   1009513² =  13489³ -  11280³  /  47
   1011933² =  10137³ -   2604³  /  93
   1016064² =  10224³ -   3312³  /  144
   1016127² =  11684³ -   8255³  /  127
   1018464² =  10712³ -   5768³  /  824
   1021167² =  16866³ -  15543³  /  9
   1022351² =  53720³ -  53599³  /  1
   1023168² =  11680³ -   8176³  /  1168

-- 14.01.2020, 08:48 --

Сейчас ещё раз внимательно присмотрелся и обнаружил ещё несколько таких пар. Наименьшая из них, если я нигде не обсчитался и не прогляделся, вот эта:

     36963² =   1110³ -    111³  /  111
     36963² =   1332³ -    999³  /  333

А следующая эта:

    157339² =   3913³ -   3276³  /  91
    157339² =   7072³ -   6903³  /  13

[Dmitriy40]

B@R5uk в сообщении #1435093 писал(а):

Сейчас ещё раз внимательно присмотрелся и обнаружил ещё несколько таких пар. Наименьшая из них, если я нигде не обсчитался и не прогляделся, вот эта:

Спасибо, меня тоже заинтересовал этот вопрос, о единственности представления разностью кубов, но проверять я не стал (решений посыпалось много и от $gcd(l,r)=1$ я отказываться не стал, да и не догадался что для данного квадрата кубы ограничены сверху). А Вы нашли контрпримеры.

[B@R5uk]

Dmitriy40, а вы в своей программе использовали какие-нибудь алгебраические свойства задачи для ускорения поиска?

Я в своём последнем брутфорсе смог только избавится от необходимости вычислять кубический корень. Для этого заготавливается массив кубов необходимой длины, а затем по нему гоняются два указателя в ожидании того, когда же расстояние между указанными кубами будет в точности равно проверяемому квадрату. В результате сложность перебора $O(N^2)$ без всяких тяжёлых операций типа деления или чего по-хуже. Однако, это всё тот же брутфорс, и время поиска уже для миллионов очень медленное. Вот я думаю, можно ли как-то ранее выведенные формулы в расчётах приспособить для ускорения?

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

class gcd {
        public static int compute(int a, int b) {
                int temp;
                if (a < b) {
                        temp = a;
                        a = b;
                        b = temp;
                }
                while (0 < b) {
                        temp = a % b;
                        a = b;
                        b = temp;
                }
                return a;
        }
}

public class Study_Cube_Square_3 {
        
        private static final int startSquare = 1;
        private static final int maxSquare   = 20000;
        private static final int maxCube = (int) Math.ceil(maxSquare / Math.sqrt(3.0)) + 1;
        
        public static void main(String[] args) {
                int k, startIndex, leftIndex, rightIndex;
                long square, rightCube, tempValue, resultsCount, startTime, stopTime;
                startTime = System.nanoTime();
                System.out.println(maxCube);
                long[] cubesList = new long[maxCube];
                for (k = 1; maxCube >= k; ++k) {
                        cubesList[k - 1] = (long) k * k * k;
                }
                resultsCount = 0;
                startIndex = 0;
                for (k = startSquare; maxSquare >= k; ++k) {
                        square = (long) k * k;
                        while (square + 1 >= cubesList[startIndex]) {
                                ++startIndex;
                        }
                        leftIndex = startIndex;
                        tempValue = cubesList[leftIndex] - square;
                        rightIndex = 0;
                        rightCube = cubesList[rightIndex];
                        while (rightIndex < leftIndex) {
                                if (tempValue > rightCube) {
                                        ++rightIndex;
                                        rightCube = cubesList[rightIndex];
                                } else {
                                        if (tempValue == rightCube) {
                                                System.out.println(String.format("%10d² = %6d³ - %6d³  /  %d",
                                                                k, leftIndex + 1, rightIndex + 1,
                                                                gcd.compute(leftIndex + 1, rightIndex + 1)));
                                                ++resultsCount;
                                        }
                                        ++leftIndex;
                                        tempValue = cubesList[leftIndex] - square;
                                }
                        }
                }
                System.out.println(resultsCount);
                stopTime = System.nanoTime();
                System.out.println(1e-9 * (stopTime - startTime));
        }
}
 

[B@R5uk]

Нашёл трёхкратно представимый квадрат. Впрочем, после того, как верно заметил nnosipov о такси-числах, это не удивительно.

   1258712² =  12285³ -   6461³  /  91
   1258712² =  15652³ -  13104³  /  364
   1258712² =  28288³ -  27612³  /  52

[Yadryara]

B@R5uk, коль уж вы так разохотились, попробуйте добраться до 7 способов. Ибо даже дети в детском саду знают, что $24153319581254312065344$ можно представить в виде суммы двух целых положительных кубов 6-ю способами

-- 14.01.2020, 20:45 --

B@R5uk в сообщении #1435093 писал(а):

Наименьшая из них, если я нигде не обсчитался и не прогляделся, вот эта:

Код:

36963² = 1110³ - 111³ / 111
36963² = 1332³ - 999³ / 333

А следующая эта:

Код:

157339² = 3913³ - 3276³ / 91
157339² = 7072³ - 6903³ / 13

А между ними разве нет $66248$ ?

[B@R5uk]

Yadryara в сообщении #1435196 писал(а):

Ибо даже дети в детском саду знают...

ОК, моя математика ещё в каменном веке.

Yadryara в сообщении #1435196 писал(а):

А между ними разве нет 66248 ?

Ага, есть. Только я проглядел.

-- 14.01.2020, 21:44 --

Yadryara в сообщении #1435196 писал(а):

попробуйте добраться до 7 способов

Это вряд ли. Я уже перебрал больше половины чисел, что можно перебрать не вылезая за пределы типа long. Запрягать для этого дела BigInteger — гиблое дело. Если не придумать какого-нибудь явного способа вычисления всех возможных решений, чтобы их потом компоновать, то ничего не получится. В лоб считается очень медленно. Я потому и спрашивал выше.

[Dmitriy40]

B@R5uk в сообщении #1435159 писал(а):

Dmitriy40, а вы в своей программе использовали какие-нибудь алгебраические свойства задачи для ускорения поиска?

Практически нет. Я решал исходную задачу, о нахождении разности кубов равной квадрату для взаимно простых чисел под кубами. Единственная оптимизация (условие $l>r$ не упоминаю ввиду очевидности) — искал не все решения, а лишь увеличивающие разницу $l-r$, это примерно раз в 7-8 сократило перебор по $r$. Ну и на асме x64 всё написал. И всё равно программа работала около полутора суток в одном потоке (подозреваю основным тормозом был квадратный корень, он вычислялся поразрядным взвешиванием, не самый скоростной метод). Но перебрала все квадраты до $2^{32}$ (под квадратом), решил на этом остановиться т.к. не хотелось связываться с возведением в куб для 128 битных чисел. Последнее найденное решение $2591402^3-24527^3=4171593675^2$.
С любимым методом ускорения, предпросчётом таблиц возможных кубов и/или квадратов на несколько младших цифр, чтобы перебирать не все подряд, а пропускать точно не дающие решений варианты комбинаций младших цифр, заморачиваться не стал, написание кода и расчёт таблиц заняло бы больше времени чем программа отработала и так.

-- 15.01.2020, 01:50 --

Yadryara в сообщении #1435196 писал(а):

Ибо даже дети в детском саду знают, что $24153319581254312065344$ можно представить в виде суммы двух целых положительных кубов 6-ю способами

А у нас разность вместо суммы. Да и это вовсе не квадрат натурального числа.

[B@R5uk]

Dmitriy40 в сообщении #1435255 писал(а):

чтобы перебирать не все подряд, а пропускать точно не дающие решений варианты комбинаций младших цифр

Это как? Такой подход позволяет сразу пропускать группы квадратов, для которых нет решений или же он позволяет не просчитывать старшие разряды, когда младшие не совпали в многоразрядных числах? Просто же умножение для стандартных типов — атомарная операция. Или я ошибаюсь?

[Dmitriy40]

B@R5uk в сообщении #1435259 писал(а):

Dmitriy40 в сообщении #1435255 писал(а):

чтобы перебирать не все подряд, а пропускать точно не дающие решений варианты комбинаций младших цифр

Это как?

Как это применить в данной задаче я даже не думал ещё, но общая идея такая: квадраты всех 10-ти цифр дают не все 10 вариантов младшей цифры, как и кубы. Значит для любого $l$ есть некий список допустимых вариантов комбинаций младшей цифры в $r$ и $k$, меньший 100 вхождений для любой младшей цифры из $l$, что позволяет во первых перебирать меньше разных $r$, во вторых перед проверкой на квадрат проверить пару-тройку-четвёрку младших цифр в $k^2$ на возможность извлечения корня тоже по таблице. Возведение в куб, а я считал сразу разность кубов по формуле $l^3-r^3=(l-r)(l^2+lr+r^2)=(l-r)((l+r)l+r^2)$ чтобы не выходить за границу $2^{64}$ для разности кубов и не морочиться с парами регистров под каждое число, требует лишь три умножения и три сложения/вычитания, это жалкие десяток тактов (на асме x64, про ЯВУ даже думать не хочу), так что тут даже и оптимизировать нечего.
Кроме того, я сразу исключал не взаимно простые $r$ с $l$, это хоть и требовало делений в алгоритме Евклида, но надеюсь тормозило в среднем не сильно (правда не проверял).

-- 15.01.2020, 02:32 --

Dmitriy40 в сообщении #1435261 писал(а):

Кроме того, я сразу исключал не взаимно простые $r$ с $l$, это хоть и требовало делений в алгоритме Евклида, но надеюсь тормозило в среднем не сильно (правда не проверял).

Тут я лоханулся, исключение НОД ускоряет программу вдесятеро, однако. Надо было НОД проверять в конце, это ускоряет почти втрое.

-- 15.01.2020, 02:39 --

Собственно Вы в соседней теме, которую я и не читал, как раз об этом и рассуждаете, о сравнении по разным модулям, что и позволяет перебирать не все комбинации.

[Yadryara]

Dmitriy40 в сообщении #1435255 писал(а):

Yadryara в сообщении #1435196 писал(а):

Ибо даже дети в детском саду знают, что $24153319581254312065344$ можно представить в виде суммы двух целых положительных кубов 6-ю способами

А у нас разность вместо суммы. Да и это вовсе не квадрат натурального числа.

Да, я в курсе. Равно как и другое таксикэбное число этой темы — $1729$. Однако ж nnosipov выше показал, как оно может пригодиться.

Ещё есть A038597 и A051393.

[Andrey A]

Dmitriy40 в сообщении #1435255 писал(а):

$2591402^3-24527^3=4171593675^2$

Эту тройку можно получить, подставив $a=25,b=37$ в тождество

Andrey A в сообщении #1434579 писал(а):

$\left [ \left ( \dfrac{a^2+3b^2}{2} \right )^2-3b^4 \right ]^3-\left [ \left ( \dfrac{a^2-3b^2}{2} \right )^2-3b^4 \right ]^3=\left ( \dfrac{3ab(a^4+3b^4)}{4} \right )^2$

Или Вы не ищите легких путей? ))

[B@R5uk]

Dmitriy40 в сообщении #1435261 писал(а):

Собственно Вы в соседней теме, которую я и не читал, как раз об этом и рассуждаете, о сравнении по разным модулям, что и позволяет перебирать не все комбинации.

Если честно, то я пытался понять, почему уравнение $x^2+1=y^3$ не имеет в качестве решения ничего, кроме тривиального $\left(0,1\right)$. Для этого я пытался рассматривать это уравнение по различным модулям (в том числе и довольно большим). Единственное, что мне удалось получить — это то, что $x=14k$, иначе уравнение не разрешимо по модулю 7 и по модулю 4. Так что я зашёл в тупик. За то, я обнаружил интересную закономерность для кубов и модулей, но это как-то мало относится к теме, если не считать вот этого сообщения, которое натолкнуло меня на второе свойство найденной мной последовательности модулей.

А вообще, я стал рассматривать $x^2+1=y^3$ пытаясь понять, почему не все кубы встречаются в решениях в качестве вычитаемых кубов. Но это сложная тема. Как верно заметил nnosipov, это связано с разрешимостью эллиптической кривой Морделла в целых числах.

Вообще, ваша идея откидывать заведомо неудачные решения весьма интересна. Однако считать в лоб по формуле, а потом сортировать результат должно должно быть гораздо быстрее. Вот даже есть такая формула:

Andrey A в сообщении #1435266 писал(а):

$\left [ \left ( \dfrac{a^2+3b^2}{2} \right )^2-3b^4 \right ]^3-\left [ \left ( \dfrac{a^2-3b^2}{2} \right )^2-3b^4 \right ]^3=\left ( \dfrac{3ab(a^4+3b^4)}{4} \right )^2$

Вот только я не пойму, как получить самый первый результат $13^2=8^3-7^3$? Дробные параметры? Или же формула даёт только часть решений? Или же она даёт одно уникальное решение для серии решений, отличающийся только общим множителем (в кубе и в квадрате, соответственно)?