CODEWITHSUNDEEP
pythonmathematical-optimization
user13541811
user13541811

Reputation:

Representing an positive integer as a sum of three numbers

In how many ways the positive integer n can be represented as the sum of three different positive integers. The two methods are different if one contains a number that the other does not.

I've managed to get the following script to count the number of ways to write n as a sum of three numbers, but it's not takin the other condition in consiredation.

def nways(n):  
  
    if (n <= 2):  
        return False
    else:           
        ways = (n - 1) * (n - 2) / 2
          
    return ways

For example if n = 8 I would need to return 2 since 1 + 2 + 5 = 8 and 1 + 3 + 4 = 8, but the current function returns 21...

What would be the correct algorithm and math behind this?

Upvotes: 0

Views: 1633

Answers (4)

AnnieFromTaiwan
AnnieFromTaiwan

Reputation: 4505

Solution

def nways(n):
    nways = 0
    for i in range(1, n-2):
        min_j, max_j = i+1, (n-i-1)//2
        nways += (max_j - min_j + 1) if max_j >= min_j else 0
    return nways

This algorithm consumes O(N) time and O(1) space.

Explanation

Let's denote the three positive numbers as i, j, k.

And since they are all different, these three numbers must be greater than or smaller than each other. We assume the smallest number to be i, the middle one to be j, the largest to be k. So then the relation would be i < j < k.

Take n = 18 for example

  • we start from i = 1, then j + k should be 17.
    • So (j,k) could be from (2,12), (3,14), ... to (8,9).
    • Notice (j,k) couldn't be (9,8), (10,7) because j<k
    • Therefore min_j would be i+1 (in this case 2), max_j would be (n-i-1)//2 (in this case 8)
    • Number of (j, k) combinations are max_j - min_j + 1 which is 7 pairs in this case
  • we go on with i = 2, then j + k should be 16.
    • min_j would be i+1 (in this case 3), max_j would be (n-i-1)//2 (in this case 7)
    • Number of (j, k) combinations are max_j - min_j + 1 which is 5 pairs in this case

We try all the possible values of i then add up all the combinations of (j, k) pair, then we get the answer.

Upvotes: 1

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16724

A very different approach would be to use a constraint solver. Here is an example:

import constraint as con

n = 8

p = con.Problem()
p.addVariables(['x','y','z'],range(1,n-2))
p.addConstraint(con.ExactSumConstraint(n))
p.addConstraint(lambda a, b, c : a < b < c, ("x", "y", "z"))
sols = p.getSolutions()

print(len(sols))
sols

This gives:

2
[{'x': 1, 'y': 3, 'z': 4}, {'x': 1, 'y': 2, 'z': 5}]

I am not aware of a simple formula that predicts the number of solutions.

Upvotes: 0

CryptoFool
CryptoFool

Reputation: 23089

You can make some pretty significant optimizations to @hgb123's already great answer to still use brute-force, but be a little more clever about it:

def ways(n):
  tuple_sum_set = set()

  for i in range(1, n-2):
    for j in range(i+1, n-2):
      for k in range(j+1, n-2):
        if i + j + k == n:
          tuple_sum_set.add((i,j,k))

  print(tuple_sum_set)
  return len(tuple_sum_set)

(If you up-vote this answer, please up-vote @hgb123's as well as this is a derivative of his answer)

Upvotes: 0

hgb123
hgb123

Reputation: 14891

You could use brute-force, with some more works:

  • check if three terms is different
  • store a set of unique terms
  • the length of that set is your result
def ways(n):
  tuple_sum_set = set()

  for i in range(1, n+1):
    for j in range(1, n+1):
      for k in range(1, n+1):
        if i + j + k == n and len(set([i, j, k])) == 3:
          tuple_sum_set.add(tuple(sorted([i,j,k])))

  print(tuple_sum_set)
  return len(tuple_sum_set)

print(ways(8))

Demo: https://repl.it/repls/ChocolateHelplessLivecd

Upvotes: 0

Related Questions