Очень красивая задача (особенно ее решение):

Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.


Например:

1 : 1^3 = 1 (На конце 1)
5 : 5^3 = 125 (На конце 5)
...

PS: Если кто-то вдруг знает решение, просьба немного подождать .

PS: В общем случае можно изменять степень и до какого числа считать.

PS: В идеале решается с использованием только Int32 и без каких-либо классов для работы с большими числами.

Здравствуйте, OlegO, Вы писали:

OO>Очень красивая задача (особенно ее решение):

OO>Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.
OO>
OO>PS: В идеале решается с использованием только Int32 и без каких-либо классов для работы с большими числами.

Если число N k-значное, то выражение "в конце его m-той содержится само число" означает, что

N^m = N (mod 10^k)

Так как

a*b (mod c) = a (mod c) * b (mod c)

то последовательно перемножая N надо всё время проводить деление по модулю, т.е. оставлять только последние k цифр. Поэтому больших чисел получаться не должно — максимум квадрат исходного числа.

Здравствуйте, OlegO, Вы писали:
Не совсем вписался в условие но я не придумал другого способа устроить умножение по модулю p*10

int maxp=1000000;
void Rec(unsigned int n, unsigned int p)
{
    if(p>=maxp)return;
    for(unsigned int i=1;i<10;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        y*=x;y%=p*10;
        y*=x;y%=p*10;
        if(y%(p*10)==x)
        {
            printf("%10i\n", x);
            Rec(x, p*10);
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}

Здравствуйте, OlegO, Вы писали:

OO>PS: Если кто-то вдруг знает решение, просьба немного подождать .

Гы! Так получится, что решив задачу, все будут молчать и писать не будут => задача не разрешима!
Но потом появится "Большой Ух" и скажет: "Всё, не могу больше терпеть! Показываюсь!"

Здравствуйте, OlegO, Вы писали:

OO>Очень красивая задача (особенно ее решение):

Полностью решить пока не получилось, но заметил, что числа надо учитывать только те, которые кончаются на 0, 1, 4, 5, 6, 9. Т.к. эти числа в кубе кончаются на самих себя. => Если большое число кончается не на них, то на самого себя его куб кончиться не может (ведь как минимум последняя цифра не совпадет).

Здравствуйте, Jenyay, Вы писали:

J>Здравствуйте, OlegO, Вы писали:

OO>>Очень красивая задача (особенно ее решение):

J>Полностью решить пока не получилось, но заметил, что числа надо учитывать только те, которые кончаются на 0, 1, 4, 5, 6, 9. Т.к. эти числа в кубе кончаются на самих себя. => Если большое число кончается не на них, то на самого себя его куб кончиться не может (ведь как минимум последняя цифра не совпадет).

А зная это, можно сделать цикл всего до 10 — перебрать вторую цифру — и получить двузначные числа с искомым свойством. И так далее — на каждый разряд всего 10 переборов!

Привет, OlegO!

OO>Для всех чисел от 1 до 1000000 , найти все числа третья степень которого в конце содержит само число.

Итак, если a — k-значное, то (a^3 — a) делится на 10^k, т.е. (a — 1), a или (a + 1) делится на 5^k, кроме того их произведение делится на 2^k.

Получаем по-крупному два варианта:
1) a делится на 5^k, (a — 1) или (a + 1) делится на 2^(k — 1);
2) a делится на 2^k, (a — 1) или (a + 1) делится на 5^k.

Алгоритм:
а) перебираем числа вида m * 5^k, где m от 1 до 2^k. Вместо 9*10^(k — 1) чисел перебираем всего 2^k чисел — уже не плохо! Кроме того переход к следующему числу — простая операция сложения (с 5^k разумеется).
б) в соответствиии с вариантом 1) или 2) проверяем , не делится ли соседнее число на интересующую нас степень двойки. При этом, благодаря тому, что компьютер работает с двоичными числами вторая операция осуществляется элементарно (т.е. это все-равно, что у школьника спросить делится ли 12345000 на 1000)!

Да... Забыл написать, что решение удовлетворяеит условиям, т.к. мы даже в квадрат числа не возводим! Вообще, если мы изучаем число a, то максимум для того, чтобы определить, хорошее оно или плохое нам надо число a+1!

Здравствуйте, Real 3L0, Вы писали:

R3>Здравствуйте, OlegO, Вы писали:

OO>>PS: Если кто-то вдруг знает решение, просьба немного подождать .

R3>Гы! Так получится, что решив задачу, все будут молчать и писать не будут => задача не разрешима!
R3>Но потом появится "Большой Ух" и скажет: "Всё, не могу больше терпеть! Показываюсь!"

Конечно терпеть не надо, надо сразу говорить

Здравствуйте, Apapa, Вы писали:

A>Да... Забыл написать, что решение удовлетворяеит условиям, т.к. мы даже в квадрат числа не возводим! Вообще, если мы изучаем число a, то максимум для того, чтобы определить, хорошее оно или плохое нам надо число a+1!

Хорошо, но это только для кубов...
А автор чего-то говорил про любую степень...

Здравствуйте, WolfHound, Вы писали:

Пример не верный в частности он не находит число:

501: 501^3 = 125751501

Здравствуйте, OlegO, Вы писали:
Ну очепятался маленько вот исправленый и расширеный вариант

unsigned int maxp=100000000;
unsigned int pow=5;
unsigned int numBase=16;
char symbols[]="0123456789ABCDEF";
void print(unsigned int n)
{
    if(!n)
    {
        printf("\n");
        return;
    }
    print(n/numBase);
    printf("%c", symbols[n%numBase]);
}
void Rec(unsigned int n, unsigned int p)
{
    if(p>=maxp)return;
    for(unsigned int i=0;i<numBase;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        for(unsigned int j=0;j<pow-1;j++)
        {
            y*=x;
            y%=p*numBase;
        }
        if(y%(p*numBase)==x)
        {
            print(x);
            Rec(x, p*numBase);
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}

Это обьясняет повторяющеяся числа(лениво было искать противоядие)

    000000
     00000
      0000
       000
        00
         0
    000001
     00001
      0001
       001
        01
         1

хотя можно сложить в set и печатать оттуда.

Пока расскажу основную идею :

Пусть у нас есть чило N надо определить, есть ли число N на конце числа полученного N^K.

Для решения задачи вспомним про Бином Ньютона и про то, что число N можно представить в виде:

N = A*1000 + B, где A и B = [0,1000]  ;)

Тогда для N^3 мы получим:

N^3 = (A*1000 + B)^3 = (A*1000)^3 + 3*(A*1000)^2*(B) + 3*(A*1000)*(B)^2 + (B)^3 = ...

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

 ... = 3*(A*1000)*(B)^2 + (B)^3

Ну и теперь его еще можно разложить, и упростить оставляя только интересующие нас разряды, тем самым получая числа находящиеся на конце степени числа N и не превышая int32 диапозона.

Вот вобщем-то и все.

Привет, OlegO!

OO>Пока расскажу основную идею :
OO>Пусть у нас есть чило N надо определить, есть ли число N на конце числа полученного N^K.
OO>N = A*1000 + B, где A и B = [0,1000]
OO>N^3 = (A*1000 + B)^3 = (A*1000)^3 + 3*(A*1000)^2*(B) + 3*(A*1000)*(B)^2 + (B)^3 = ...
OO> ... = 3*(A*1000)*(B)^2 + (B)^3
OO>Ну и теперь его еще можно разложить, и упростить оставляя только интересующие нас разряды, тем самым получая числа находящиеся на конце степени числа N и не превышая int32 диапозона.
OO>Вот вобщем-то и все.

Для третьей степени мой вариант

Автор: Apapa
Дата: 10.02.03

намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32... Этот вариант почему-то проигнорировали (наверное, из зависти... )...

Интересно было бы обощить твой вариант для произвольной степени, т.к. мой вариант на вскидку при `больших степенях не пройдет!

Здравствуйте, Apapa, Вы писали:

A>Для третьей степени мой вариант

Автор: Apapa
Дата: 10.02.03

намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32... Этот вариант почему-то проигнорировали (наверное, из зависти... )...

Да нет не из-за зависти , вариант очень хорош . Просто пока руки не дошли попробывать его в действии (реализовать) и посмотреть как он работает.

A>Интересно было бы обощить твой вариант для произвольной степени, т.к. мой вариант на вскидку при `больших степенях не пройдет!

Надо будет подумать

Здравствуйте, Apapa, Вы писали:

A>Для третьей степени мой вариант

Автор: Apapa
Дата: 10.02.03

намного легче, быстрее и позволяет рассматривать числа вплоть до 4 294 967 294 с использованием только int32... Этот вариант почему-то проигнорировали (наверное, из зависти... )...

Мой вариант тоже игнорируют...хотя он для произвольной степени и для произвольной системы счисления...ну и что что перебор зато с КАКИМИ отсечениями.

unsigned int maxRec=5;
unsigned int pow=3;
unsigned int numBase=10;
char symbols[]="0123456789ABCDEF";
unsigned int nums[100];
unsigned int numsPos=0;
void Rec(unsigned int n, unsigned int p)
{
    if(numsPos>=maxRec)return;
    for(unsigned int i=0;i<numBase;i++)
    {
        unsigned int x=n+i*p;
        unsigned __int64 y=x;
        for(unsigned int j=0;j<pow-1;j++)
        {
            y*=x;
            y%=p*numBase;
        }
        if(y%(p*numBase)==x)
        {
            nums[numsPos]=i;
            for(int j=20-numsPos;j>=0;j--)    printf(" ");
            for(int j=numsPos;j>=0;j--)        printf("%c", symbols[nums[j]]);
            printf("\n");
            numsPos++;
            Rec(x, p*numBase);
            numsPos--;
        }
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    Rec(0, 1);
    return 0;
}

unsigned __int64 использован для того чтобы умножение по модулю 2^32 под ногами не путалось.

Привет, WolfHound!

WH>unsigned __int64 использован для того чтобы умножение по модулю 2^32 под ногами не путалось.

Здравствуйте, Pushkin, Вы писали:

P> А зная это, можно сделать цикл всего до 10 — перебрать вторую цифру — и получить двузначные числа с искомым свойством. И так далее — на каждый разряд всего 10 переборов!

А я в этом не уверен. Во-первых, я не уверен, что это справедливо для чисел, у которых больше 1 разряда. А, во-вторых, даже если это и так, то все-равно надо проверять окончание числа с бОльшими разрядами на значение ВСЕХ пердыдущих подошедших чисел. И все-равно числа получатся слишком большие.

Здравствуйте, WolfHound, Вы писали:

WH>Мой вариант тоже игнорируют...хотя он для произвольной степени и для произвольной системы счисления...ну и что что перебор зато с КАКИМИ отсечениями.

Ну вы еще подеритесь .