Куб натурального числа.

[Thinker]

Доброго времени суток!
Сегодня мне предложили задачу, которая поставила меня в тупик:

Может ли число, состоящее из 10 различных цифр, быть точным кубом натурального числа?

Мне в голову пришло только следующее:
1. Поскольку сумма всех цифр = 45, то наше число делится на 9. Если бы удалось как-нибудь доказать, что оно не делится на 27, то на вопрос задачи мы дали бы отрицательный ответ.
2. Чтобы $n^3$ было десятизначным числом, n должно принадлежать $[1000; 2154]$.
3. Куб натурального числа может оканчиваться любой цифрой.
Как рассуждать дальше, не имею ни малейшего представления. Буду очень признателен всем, кто поделится какими-нибудь идеями.

[mustitz]

Перебор говорит что нет

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

$ cat test.c 
#include <stdint.h>
#include <stdio.h>

static inline void test(uint64_t x)
{
    const uint64_t xxx = x * x * x;

    unsigned int mask = 0;
    uint64_t tmp = xxx;

    while (tmp != 0) {
        const unsigned int digit_mask = 1u << (tmp % 10);
        if (digit_mask & mask) {
            fprintf(stderr, "! %3ld %10ld -> %1ld\n", x, xxx, tmp % 10);
            return;
        }
        mask |= digit_mask;
        tmp /= 10;
    }

    printf("%3ld %10ld\n", x, xxx);
}

int main()
{
    for (uint64_t x=1000; x<=2155; ++x)
        test(x);
}
$ gcc -std=gnu99 test.c -o test
$ ./test 2>/dev/null
$ ./test
! 1000 1000000000 -> 0
! 1001 1003003001 -> 0
! 1002 1006012008 -> 0
! 1003 1009027027 -> 7
! 1004 1012048064 -> 4
! 1005 1015075125 -> 5
! 1006 1018108216 -> 1
! 1007 1021147343 -> 3
..................................
! 2146 9883008136 -> 0
! 2147 9896830523 -> 3
! 2148 9910665792 -> 6
! 2149 9924513949 -> 9
! 2150 9938375000 -> 0
! 2151 9952248951 -> 2
! 2152 9966135808 -> 8
! 2153 9980035577 -> 7
! 2154 9993948264 -> 4
! 2155 10007873875 -> 7
 

[Thinker]

Спасибо, но хотелось бы понять, как эта задача решается без перебора. Если, как Вы говорите, "нет", то это надо бы как-то доказать.

[gris]

Идея с $27$ плохая.Число $9999999999$ на $27$ не делится. Несложные рассуждения, лишние здесь, приводят к тому, что есть числа нашего типа, кратные $27$.

[Thinker]

gris в сообщении #1163352 писал(а):

Идея с $27$ плохая.Число $9999999999$ на $27$ не делится. Несложные рассуждения, лишние здесь, приводят к тому, что есть числа нашего типа, кратные $27$.

Что-то я Вас не понял. Почему идея с 27 плохая? Ведь если число делится на 9, то, будучи кубом, оно обязано делиться и на 27. А если не делится на 27, значит, оно - не куб. Или я не прав?
И при чем тут число 9999999999?
1. Оно не является кубом натурального числа.
2. В задаче говорится про десятизначное число, записанное разными цифрами.

[grizzly]

Thinker
А откуда задача, не знаете? Ну, есть стандартная такая задача для школьных олимпиад, в которой спрашивается про куб простого числа. С этим понятно. Может, кто-то просто решил самостоятельно "обобщить"? Или предполагается солидный первоисточник?

[Thinker]

Я - репетитор по математике. Один мой ученик учится в физ-мат лицее. Их учитель постоянно дает им решать олимпиадные задачи. Но сегодня вышло так, что одну из этих задач я тоже не смог решить (позор для репетитора )

[Батороев]

Thinker
Можно использовать сравнение $1000\equiv 1\pmod {27}$. Сравните с проверкой делимости на $9$, имея в виду то, что $10\equiv 1\pmod{9}$.

-- 27 окт 2016 10:08 --

Это, что касается проверки делимости. Про наличие куба, не знаю.

[gris]

Thinker, я имел в виду, что среди чисел нашего вида (состоящих из 10 различных цифр), имеются числа, кратные $27$. Вот мои рассуждения без калькулятора и бумажки. Рассмотрим любое число нашего вида, оканчивающееся на $27$. Если оно делится на $27$, то мы нашли нужное число. Если нет, то оно имеет остаток от деления на $27$ равный или $18$, или $9$. Если $18$, то рассмотрим число, в котором первые 8 цифр такие же, а оканчивается оно на $72$. Это число имеет другой остаток от деления на $27$. То есть, либо $0$, либо $9$. Если $0$, то мы нашли то, что нужно. Если нет, то у нас есть число нашего типа, которое имеет остаток от деления на $27$ равный $9$. Вот теперь число $9999999999$ делим на $9$. Получаем $1111111111$. Остаток от деления на $3$ равен $1$. Значит остаток от деления $9999999999$ на $27$ равен $9$. Разность $9999999999$ и найденного числа, конечно, делится на $27$. И она представляет собой число нашего типа, так как его цифры являются дополнениями до $9$ цифр вычитаемого.
То есть среди чисел нашего вида имеются кратные $27$. То есть не надо доказывать, что их нет. Хотя условие делимости возводимого в куб числа на $3$ сокращает поиск на компьютере в три раза. Да чего его жалеть, тот компьютер.

[ИСН]

(Оффтоп)

Любой перебор такого размера кто-то сделал до нас. A129525

[gris]

TC хочет без перебора. А это даже арифметических действий с числами большими ста не предполагает.
Кстати, в OEIS задача решалась перебором. Только вот почему до $10000$? В теме уже озвучено, что хватит 2155. Ведь если больше, то будет уже больше 10 цифр в кубе, и наверняка будут две одинаковых. Нарушаются права компьютеров!

[atlakatl]

$2134567890$ на 27 делится. Так что надо что-то другое искать.

[Umka2000]

Thinker в сообщении #1163317 писал(а):

3. Куб натурального числа может оканчиваться любой цифрой.

в нашем случае число не заканчивается на ноль, т.к. иначе будет сразу три нуля, что не возможно по нач. условию - все цифры разные

[venco]

Перстановка троек цифр не влияет на делимость на 27.

[Thinker]

gris в сообщении #1163444 писал(а):

Кстати, в OEIS задача решалась перебором. Только вот почему до $10000$? В теме уже озвучено, что хватит 2155.

Они решили задачу перебором до того, как я создал эту тему
Короче, без перебора решить никто не может? Хороша задачка для 6-го класса!