Проблема с функцией Ейлера

[fuck3r]

Добрый день, даже не знаю, что делать, уже везде искал, смотрел, никак не могу додуматься.
k=phi(n), где phi(n) функция Эйлера. Нужно найти минимальное n (k известно) такое, чтобы это уравнение было верным... Каким образом это можно сделать?

[Руст]

Не для всех k существует решение, например, если $k>1$ нечётное, то нет решения.

[Хорхе]

Гугл рулит.
Судя по найденным результатам, простого алгоритма нет.
Почитайте здесь и здесь.

[VAL]

Хорхе писал(а):

Гугл рулит.
Судя по найденным результатам, простого алгоритма нет.

Посмотрел, как считается invphi в Maple. В принципе алгоритм не сложный.
По крайней мере, короткий

proc (a) local d, divlist, i, j; 
if not type(a,'posint') then return ('procname')(args) end if; 
d := ifactors(a)[2]; 
divlist := sort(map(convert,combinat:-powerset([seq(seq(op(1,d[j]),i = 1 .. op(2,d[j])),j = 1 .. nops(d))]),'`*`')); 
divlist := select(type,divlist,'even'); 
divlist := select(x -> isprime(x+1),divlist); remove(has,sort(map(convert,invrec(a,divlist),'`*`')),FAIL) 
end proc

[Trotil]

VAL, а как это посмотреть можно?

[VAL]

Trotil писал(а):

VAL, а как это посмотреть можно?

>interface(verboseproc=2): eval(numtheory[invphi]);

[fuck3r]

Спасибо за ссылки. там не очень понятно по второй а для первой еще плагин не скачал... может кто-нибудь на пальцах растолковать?

[Хорхе]

VAL писал(а):

Хорхе писал(а):

Гугл рулит.
Судя по найденным результатам, простого алгоритма нет.

Посмотрел, как считается invphi в Maple. В принципе алгоритм не сложный.
По крайней мере, короткий

Если я правильно понял, это тупой перебор. Вряд ли можно назвать его коротким

[VAL]

Хорхе писал(а):

VAL писал(а):

Хорхе писал(а):

Гугл рулит.
Судя по найденным результатам, простого алгоритма нет.

Посмотрел, как считается invphi в Maple. В принципе алгоритм не сложный.
По крайней мере, короткий

Если я правильно понял, это тупой перебор. Вряд ли можно назвать его коротким

Короткий, в смысле, не сложный. А умного алгоритма я не обещал