Заслуженный участник |
 |
08/04/08 8562
|
Последний раз редактировалось Sonic86 20.12.2015, 12:34, всего редактировалось 13 раз(а).
Задача а) по большому счету - это простое упражнение на применение функции Кармайкла: https://en.wikipedia.org/wiki/Carmichael_function . Формула для ее вычисления имеется и несложная. С ее помощью задача преобразуется в такую: Найти все  . Далее несложно доказывается, что все решения свободны от квадратов (ограничение на показатель  будет  ) образуют ЧУМ по отношению делимости (т.е. не случайно  .): Пусть  , возьмем  ,  . Тогда    1)  - индукционный переход 2)  - ограничение сверху на  , дающее конечность перебора. Остается позаниматься перебором, и получить  , дальше цепь обрывается и все. С задачей б), похоже, аналогичная история, но в ней нет ограничения на показатели степеней простых и число решений явно бесконечно (например,  ). Далее лезут все простые Ферма - их список мы уже явно не знаем...... Т.е. пусть множество  таково, что  и если  , то  . Тогда  - это ответ к задаче  (данные)
Вот, например, код их вывода: Код: gp > for(n=3,10^3,if(Mod(n,znstar(n)[2][1])==0,print(n" "factor(n)))) А вот какие они бывают: 4 Mat([2, 2]) 6 [2, 1; 3, 1] 8 Mat([2, 3]) 12 [2, 2; 3, 1] 16 Mat([2, 4]) 18 [2, 1; 3, 2] 20 [2, 2; 5, 1] 24 [2, 3; 3, 1] 32 Mat([2, 5]) 36 [2, 2; 3, 2] 40 [2, 3; 5, 1] 42 [2, 1; 3, 1; 7, 1] 48 [2, 4; 3, 1] 54 [2, 1; 3, 3] 60 [2, 2; 3, 1; 5, 1] 64 Mat([2, 6]) 72 [2, 3; 3, 2] 80 [2, 4; 5, 1] 84 [2, 2; 3, 1; 7, 1] 96 [2, 5; 3, 1] 100 [2, 2; 5, 2] 108 [2, 2; 3, 3] 120 [2, 3; 3, 1; 5, 1] 126 [2, 1; 3, 2; 7, 1] 128 Mat([2, 7]) 144 [2, 4; 3, 2] 156 [2, 2; 3, 1; 13, 1] 160 [2, 5; 5, 1] 162 [2, 1; 3, 4] 168 [2, 3; 3, 1; 7, 1] 180 [2, 2; 3, 2; 5, 1] 192 [2, 6; 3, 1] 200 [2, 3; 5, 2] 216 [2, 3; 3, 3] 220 [2, 2; 5, 1; 11, 1] 240 [2, 4; 3, 1; 5, 1] 252 [2, 2; 3, 2; 7, 1] 256 Mat([2, 8]) 272 [2, 4; 17, 1] 288 [2, 5; 3, 2] 294 [2, 1; 3, 1; 7, 2] 300 [2, 2; 3, 1; 5, 2] 312 [2, 3; 3, 1; 13, 1] 320 [2, 6; 5, 1] 324 [2, 2; 3, 4] 336 [2, 4; 3, 1; 7, 1] 342 [2, 1; 3, 2; 19, 1] 360 [2, 3; 3, 2; 5, 1] 378 [2, 1; 3, 3; 7, 1] 384 [2, 7; 3, 1] 400 [2, 4; 5, 2] 420 [2, 2; 3, 1; 5, 1; 7, 1] 432 [2, 4; 3, 3] 440 [2, 3; 5, 1; 11, 1] 468 [2, 2; 3, 2; 13, 1] 480 [2, 5; 3, 1; 5, 1] 486 [2, 1; 3, 5] 500 [2, 2; 5, 3] 504 [2, 3; 3, 2; 7, 1] 512 Mat([2, 9]) 540 [2, 2; 3, 3; 5, 1] 544 [2, 5; 17, 1] 576 [2, 6; 3, 2] 588 [2, 2; 3, 1; 7, 2] 600 [2, 3; 3, 1; 5, 2] 624 [2, 4; 3, 1; 13, 1] 640 [2, 7; 5, 1] 648 [2, 3; 3, 4] 660 [2, 2; 3, 1; 5, 1; 11, 1] 672 [2, 5; 3, 1; 7, 1] 684 [2, 2; 3, 2; 19, 1] 720 [2, 4; 3, 2; 5, 1] 756 [2, 2; 3, 3; 7, 1] 768 [2, 8; 3, 1] 780 [2, 2; 3, 1; 5, 1; 13, 1] 800 [2, 5; 5, 2] 816 [2, 4; 3, 1; 17, 1] 840 [2, 3; 3, 1; 5, 1; 7, 1] 864 [2, 5; 3, 3] 880 [2, 4; 5, 1; 11, 1] 882 [2, 1; 3, 2; 7, 2] 900 [2, 2; 3, 2; 5, 2] 936 [2, 3; 3, 2; 13, 1] 960 [2, 6; 3, 1; 5, 1] 972 [2, 2; 3, 5] 1000 [2, 3; 5, 3]
|
|