Программировать влом, лучше подсчитать математически.
Попробую обрисовать свой ход мыслей.
Выпишем возможные варианты для первых чисел: (по три строчки для каждого числа)
-
-
1
-
2
1+1
3
2+1
1+1+1
3+1
2+2 2+1+1
1+1+1+1
3+2 3+1+1
2+2+1 2+1+1+1
1+1+1+1+1
3+3 3+2+1 3+1+1+1
2+2+2 2+2+1+1 2+1+1+1+1
1+1+1+1+1+1
3+3+1 3+2+2 3+2+1+1 3+1+1+1+1
2+2+2+1 2+2+1+1+1 2+1+1+1+1+1
1+1+1+1+1+1+1
3+3+2 3+3+1+1 3+2+2+1 3+2+1+1+1 3+1+1+1+1+1
2+2+2+2 2+2+2+1+1 2+2+1+1+1+1 2+1+1+1+1+1
1+1+1+1+1+1+1+1
3+3+3 3+3+2+1 3+3+1+1+1 3+2+2+2 3+2+2+1+1 3+2+1+1+1+1 3+1+1+1+1+1
2+2+2+2+1 2+2+2+1+1+1 2+2+1+1+1+1+1 2+1+1+1+1+1+1
1+1+1+1+1+1+1+1+1
Первая строчка - в слагаемых есть хоть одна тройка,
Вторая строчка - в слагаемых есть хоть одна двойка, но нет тройки
Третья - единичное представление.
Это все разложение в сумму, со слагаемыми не выше трех. Число вариантов для каждой строки:
s(1,1)=1 s(1,2)=0 s(1,3)=0
s(2,1)=1 s(2,2)=1 s(2,3)=0
s(3,1)=1 s(3,2)=1 s(3,3)=1
s(4,1)=1 s(4,2)=2 s(4,3)=1
s(5,1)=1 s(5,2)=2 s(5,3)=2
s(6,1)=1 s(6,2)=3 s(6,3)=3
s(7,1)=1 s(7,2)=3 s(7,3)=4
s(8,1)=1 s(8,2)=4 s(8,3)=5
s(9,1)=1 s(9,2)=4 s(9,3)=7
Всего способов разложить число n будет равно S(n)=s(n,1)+s(n,2)+s(n,3);
s(n,1)=1 (очевидно)
s(n,2)=s(n-2,2)+s(n-2,1)=s(n-2,2)+1;
=> s(n,2)=n/2, округленное снизу
s(n,3)=s(n-3,3)+s(n-3,2)+s(n-3,1)=s(n-3,3)+(n-3)/2 (округл.)+1= ... 3*k^2+ поправка
n=6k+остаток, поправка зависит от остатка:
s(6k,3)=3k^2;
s(6k+1,3)=3k^2+k;
s(6k+2,3)=3k^2+2k;
s(6k+3,3)=3k^2+3k+1;
s(6k+4,3)=3k^2+4k+1;
s(6k+5,3)=3k^2+5k+2;
Или это выразить через n: s(n,3)=(n^2)/12, с округлением вниз до целого.
Пример: s(9.3)=s(6*1+3,3)=3*1^2+3*1+1=7 (совпадает!) (или =81/12=7 + 7/12 -> 7 )
Для заданного n=23:
S(23)=s(26,3)=3*4^2+2*k=56;