числа на Carmichael

Редицата числа на Carmichael (Carmichael numbers) съдържа нечетни съставни числа N, които са едновременно:

числа squarefree - нямат за делител квадрат на естествено число;

всеки делител е просто число p, така че числото p-1 е делител на числото N-1 p | n => p-1 | n-1.

Пример:

561=3*11*17; (561-1)/(3-1) = 280; (561-1)/(11-1) =560; (561-1)/(17-1)=35 като

560 mod (3-1) = 560 mod (11-1) = 560 mod (17-1) = 0

Следващите числа в редицата са:

1105 = 5*13*17 ; 1104/16 = 69;

1729 = 7*13*19; 1728 /18 = 96;

2465 = 5*17*29; 2464 /28 = 88

6601 = 7*23*41; 6600 /40 = 165 ...

Определението за числа на Carmichael е на Korselt - 1899 г. Редицата е описана подробно в https://oeis.org/A002997.

Съставете програма, чрез която се въвежда естествено число N от интервала [1..15] и се извеждат посочения брой елементи от редицата числа на Carmichael. Програмата да използва две аналогични функции - рекурсия и итерация.

С увеличаване на индекса намалява честотата на срещане на поредните числа на Carmichael, което ограничава използване на рекурсия.

Подробно описание за числа на Carmichael може да намерите и на следните адреси: https://en.wikipedia.org/wiki/Carmichael_number; http://mathworld.wolfram.com/CarmichaelNumber.html.

Разгледайте други основни типове примерни задачи, за чието решение се използват числови редици. Сравнете със прости числа, съставни числа, високо съставни числа, богати числа, много богати числа, числа без квадрат (Squarefree).