мерсеново число

Мерсеново число - по името на автора монаха Mersenne, изучавал ги  в началото на 17-ти век. Редицата с прости числа на Мерсен (Mersenne numbers) може да бъде представена с формулата: a(n) =  2^n - 1, където p е също просто число. Най-големите открити досега прости числа са числа на Мерсен. Интересен факт е, че ако мерсеново число с номер n е просто, то и числото n е също просто. Обратното твърдение е невярно. 

Друга редица, свързана с числа на Mersenne, съдържа също само естествени числа и може да бъде представена с рекурентната формула a(n) = a(n-1)+2a(n-2)+2, a(0)=0, a(1)=1.  При двоично представяне всяко от числата съдържа само цифра 1. Така дефинираната числова редица съдържа в себе си, като подмножество, редицата прости числа на Mersenne (3 , 7 , 31, 127 ...), които от своя страна са свързани със съвършените числа (perfect number 6, 28, 496, 8128...). 

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

Редицата с числа на Mersenne е представена в https://oeis.org редица A000225.  Подробно описание за мерсеново число може да намерите на адрес:  https://en.wikipedia.org/wiki/Mersenne_prime.

Разгледайте други основни типове примерни задачи, за чието решение се използват прости числа и числови редици. Прочетете допълнителен материал за: прости числа в интервал, факторизация, брой и вид прости делители, прости делители в естествено число.