Так вот, продолжая историю про Эйлера.
1747-й год, пентагональная теорема все ещё только гипотеза.
Эйлер открывает другое утверждение — на этот раз о сумме делителей.
А именно — пусть σ(n) это сумма всех делителей числа n, включая 1 и его самого. Последовательность значений σ(n) —
1, 3, 4, 7, 6, 12, 8, 15, ... .
На вид достаточно нерегулярная — что естественно, σ(n) хорошо связано с разложением n на простые множители, но у n и у n+1 разложения совершенно разные.
Так вот — Эйлер обнаруживает, что она подчиняется практически такому же рекуррентному соотношению, что и p(n), с единственной заменой: если в правой части возникает σ(0), то нужно вместо него подставить n.
Он публикует статью Découverte d'une loi tout extraordinaire des nombres par rapport à la somme de leurs diviseurs — оригинал на французском можно найти тут, а ещё она в переводе вошла в книгу Пойа "Математика и правдоподобные рассуждения", см. главу VI.
Смотрите (подстановку n вместо σ(0) я выделяю жирным) :
σ(1)=1;
σ(2)=σ(2-1)+2=3;
σ(3)=σ(3-1)+σ(3-2)=1+3=4;
σ(4)=σ(4-1)+σ(4-2)=7;
σ(5)=σ(5-1)+σ(5-2)-5=4+7-5=6;
σ(6)=σ(6-1)+σ(6-2)-σ(6-5)=7+6-1=12;
σ(7)=σ(7-1)+σ(7-2)-σ(7-5)-7=12+6-3-7=8;
...
Удивительно, правда?