Sum Of How Many Numbers Should N Be Partitioned

Partition of integer: 4 = 4 p(4,1) = 1 = 1+3, 2+2 p(4,2) = 2 = 1+1+2 p(4,3) = 1 = 1+1+1+1 p(4,4) = 1 /max(p(4, k)) = 2, at

Solution 1:

For rather small n values you can implicitly generate all partitions, count number of parts in every partition.

n = 7
kcounts = [0]*n

defparts(sum, last = 1, k=0):
    ifsum == 0:
        global kcounts
        kcounts[k-1] += 1returnfor i inrange(last, sum + 1):
        parts(sum - i, i, k + 1)

parts(n)
print(kcounts)

>>[1, 3, 4, 3, 2, 1, 1]

So k=3 gives maximum partitions

Solution 2:

Do the following :

N = int(input())
p = [[0]*(N+1) for i inrange(N+1)]

maximum = 0
k_number = 0
ans = []
for i inrange(N+1):
    p[i][1] = 1
    p[i][i] = 1for n inrange(2, N+1):
    k_number, maximum = 0, 0for k inrange(2, n+1):
        p[n][k] = p[n-1][k-1] + p[n-k][k]
        if p[n][k] > maximum :
              maximum = p[n][k] 
              k_number = k
              n_for_max = n
    ans.append([n, k_number, maximum])
print(sum(p[-1])) 
for x in p:
    print(sum(x))
for x in ans:
    print(x)
#print('k_number: ',k_number)