Проверка что число - куб

[wrest]

При численном переборе вариантов решения великой теоремы Ферма для n=3 в одной из головоломок Ktina-ы понадобилось определять является ли натуральное число точным кубом.

В PARI/GP для этого есть функция ispower(x,{k},{&n}) которая определяет является ли x k-той степенью какого-либа числа и если да, то записывает это число в n.

Но поскольку перебирать надо много, а числа большие (пока речь о числах порядка $10^{15}-10^{20}$), то определение является ли число кубом -- узкое место.

Ув. mihaild предложил не совсем понятную методику "можно получить большое ускорение проверки, является ли число кубом, предварительно проверив это по какому-то модулю, по которому мало различных кубов" и даже привел текст, но чтобы не разводить офтопик там, спрошу тут: как этой методикой пользоваться? Подходит ли она для других степеней?

[mihaild]

Методика вполне рабоче-крестьянская: если $k$ - куб, то $k$ - куб по любому модулю. Соответственно выбираем число $n$ и заранее заполняем битовый массив размера $n$ - ставим $1$ в позиции, соответствующие кубам по модулю $n$.
Ну и надо выбрать $n$ так, чтобы доля единичек была поменьше.

[Sender]

wrest, про сравнения по модулю слышали? Возьмём, к примеру, $7$ в качестве модуля. Тогда
$0^3 \equiv 0 (\mod 7)$,
$1^3 \equiv 1 (\mod 7)$,
$2^3 \equiv 1 (\mod 7)$,
$3^3 \equiv 6 (\mod 7)$,
$4^3 \equiv 1 (\mod 7)$,
$5^3 \equiv 6 (\mod 7)$,
$6^3 \equiv 6 (\mod 7)$.

То есть по модулю $7$ кубы произвольных целых чисел могут принимать всего $3$ значения: $0$, $1$ и $6$.

[wrest]

Sender в сообщении #1331189 писал(а):

про сравнения по модулю слышали?

Да, но только что и слышал.

Sender в сообщении #1331189 писал(а):

То есть по модулю $7$ кубы произвольных целых чисел могут принимать всего $3$ значения: $0$, $1$ и $6$.

А достаточно посмотреть на таблицу из 6 кубов чтобы сделать такой вывод?
Но ясно: это уменьшает количество проверок на "истинную" кубичность примерно вдвое.

[Sender]

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

А достаточно посмотреть на таблицу из 6 кубов чтобы сделать такой вывод?

Вообще-то их 7. А каков остаток от деления на $7$ числа $(7m+n)^3$, где $0 \leqslant n \leqslant 6$?

[wrest]

Sender в сообщении #1331193 писал(а):

Вообще-то их 7. А каков остаток от деления на $7$ числа $(7m+n)^3$, где $0 \leqslant n \leqslant 6$?

А.... Ну да: после раскрытия скобок семерка будет множителем во всех слагаемых (и остаток там будет ноль) кроме последнего, последнее будет $n^3$ а его мы проверили.

[mihaild]

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

[realeugene]

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

[Dmitriy40]

Там смысл в этих двух кусочках кода (привожу с сокращениями):

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

//Заполнение массива флагов
const TInt CUBES_MOD = 575757;
std::vector<bool> cubesMod(CUBES_MOD, false);
for (t = 0; t < MAX_T; ++t) cubesMod[(t * t * t) % CUBES_MOD] = true;
//Использование массива флагов
if (!cubesMod[t_target % CUBES_MOD]) continue;//Такое t_target точно не является никаким кубом и извлекать корень не нужно

Т.е. словами, заполняем массив флагов так чтобы он по младшим цифрам числа указывал может ли куб какого-то числа иметь такие младшие цифры. Младшие цифры берутся не десятичные, а по модулю CUBES_MOD, при удачном выборе этого числа количество true в массиве будет сильно меньше количества false и для многих и многих t_target извлекать корень не понадобится.
Можно даже ещё ускорить заведя массив с индексацией по старшим цифрам t_target и содержащий начальное приближение (усечённое вниз) для кубического корня, тогда останется проверить буквально несколько чисел (возведя их в куб и сравнив с t_target). Не уверен, возможно в том коде подобное и сделано через t_pos и lower_bound.

И да, эту технику можно использовать почти в любых местах, хоть для степеней, хоть для произвольных функций. Только величину модуля придётся подбирать каждый раз индивидуально - или плюнуть на незначительное снижение эффективности и взять какое-нибудь простое число. Фактически это напоминает (если не является прямо) хэштаблицы.

[wrest]

В PARI/GP есть непонятные мне функции "модулярной арифметики" -- наверное можно как-то приспособить их?

mihaild в сообщении #1331197 писал(а):

И дальше нужно найти такое $n$, чтобы число кубических вычетов по модулю $n$ было мало по сравнению с $n$.

Ок, хочу убедиться что я правильно понимаю.

Считаем количество вычетов:

? Vychet(n)=my(v=vector(n,i^3%n));vecsort(v,,8);return(#v);
? Vychet(7)
3
? Vychet(575757)
4095

Для n=7 получается 3 различных вычета (потенциальное ускорение в 2 раза), для n=575757 получается 4095 различных вычетов (ускорение в 140 раз) . Пока верно?

[mihaild]

Да, так. Только ускорение всё же не совсем в 2 раза - поход в массив не бесплатный.
(и плюс не факт, что запросы равномерно распределены по нужному модулю)

[wrest]

mihaild в сообщении #1331209 писал(а):

Только ускорение всё же не совсем в 2 раза - поход в массив не бесплатный.

Ну, условно.

mihaild в сообщении #1331209 писал(а):

Да, так.

Ok и что дальше?

[iifat]

Да мало ли чего.
Можно просто довольствоваться ускорением в 140 раз.
Можно подобрать парочку таких чисел и ускориться в $140\times140$ раз или сколько там.
Можно набрать кучу таких чисел и вообще брать кубический корень по модулям, а потом считать число (учтя многозначность корня по модулю).
Вообще, как-то странно: в поле коммплексных чисел кубический корень имеет три значения, а в поле по модулю 575757 — в среднем 140. А может, и не странно.

[wrest]

iifat в сообщении #1331217 писал(а):

Можно подобрать парочку таких чисел

Они должны быть взаимно-простыми?

[guryev]

Переводим в double, извлекаем корень третьей степени, округляем его до ближайшего целого, возводим это целое в куб, сравниваем с исходным.