Sum of how many numbers should N be partitioned

Question

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 k = 2

5 = 5                 p(5,1) = 1
  = 1+4, 2+3          p(5,2) = 2
  = 1+1+3, 1+2+2      p(5,3) = 2
  = 1+1+1+2           p(5,4) = 1
  = 1+1+1+1+1         p(5,5) = 1

/max(p(5, k)) = 2, at k = 2 and 3

and p(n) = Σp(n, k) for ∀k: 0


p(4) = p(4, 1) + p(4, 2) + p(4, 3) + p(4, 4) = 1 + 2 + 1 + 1 = 5
p(5) = p(5, 1) + p(5, 2) + p(5, 3) + p(5, 4) + p(5, 5) = 1 + 2 + 2 + 1 + 1 + 1 = 7
for this I used Euler's Identity p(n, k) = p(n-1, k-1) + p(n-k, k)
#p(n, k) = p(n-1, k-1) + p(n-k, k)
N = int(input())
p = [[0]*(N+1) for i in range(N+1)]
for i in range(N+1):
    p[i][1] = 1
    p[i][i] = 1
for n in range(2, N+1):
    for k in range(2, n+1):
        p[n][k] = p[n-1][k-1] + p[n-k][k]
print(sum(p[-1])) 
for x in p:
    print(x[1:])
    print(sum(x))

Using above code I could have been able to find partition of Integer: p(N) i.e The total number of ways in which a given number n can be expressed as sum of all positive integers.
But, Now I want to find the value of k for which p(n, k) is maximum.
But without using Euler's Identity in python.

user_15919783 · Answer

Do the following :

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

maximum = 0
k_number = 0
ans = []
for i in range(N+1):
    p[i][1] = 1
    p[i][i] = 1
for n in range(2, N+1):
    k_number, maximum = 0, 0
    for k in range(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)

user_844416 · Answer

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

n = 7
kcounts = [0]*n

def parts(sum, last = 1, k=0):
    if sum == 0:
        global kcounts
        kcounts[k-1] += 1
        return

    for i in range(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

Sum of how many numbers should N be partitioned

2 Answers