How to Find Number of Ways That the Integers 1,2,3 Can Add Up to N

How to find number of ways that the integers 1,2,3 can add up to n?

The recurrence relation is F(n+3)=F(n+2)+F(n+1)+F(n) with F(0)=1, F(-1)=F(-2)=0. These are the tribonacci numbers (a variant of the Fibonacci numbers):

It's possible to write an easy O(n) solution:

def count_ways(n):
    a, b, c = 1, 0, 0
    for _ in xrange(n):
        a, b, c = a+b+c, a, b
    return a

It's harder, but possible to compute the result in relatively few arithmetic operations:

def count_ways(n):
    A = 3**(n+3)
    P = A**3-A**2-A-1
    return pow(A, n+3, P) % A

for i in xrange(20):
    print i, count_ways(i)

How to find out the number of possible ways of adding 1 2 and 3 to given sum avoiding repetition?

Let F1, F2, F3 be the number of ways of constructing N from 1, 2 and 3, without starting with 1, 2, 3 respectively.

Then:

F1(N) = F2(N-2) + F3(N-3)
F2(N) = F1(N-1) + F3(N-3)
F3(N) = F1(N-1) + F2(N-2)

with the edge conditions:

F1(0) = F2(0) = F3(0) = 1
F1(x) = F2(x) = F3(x) = 0 (for x < 0)

Then to solve the original problem: F(0) = 1, F(N) = F1(N-1) + F2(N-2) + F3(N-3)

A linear-time solution that uses O(1) space:

def F(N):
    a, b, c, d, e, f, g, h, i = 1, 0, 0, 1, 0, 0, 1, 0, 0
    for _ in range(N-1):
        a, b, c, d, e, f, g, h, i = e+i, a, b, a+i, d, e, a+e, g, h
    return a+e+i

for n in range(11):
    print(n, F(n))

This uses these recurrence relations:

F1(i+1), F1(i), F1(i-1) = F2(i-1)+F3(i-2), F1(i), F1(i-1)
F2(i+1), F2(i), F2(i-1) = F1(i)+F3(i-2), F2(i), F2(i-1)
F3(i+1), F3(i), F3(i-1) = F1(i)+F2(i-1), F3(i), F3(i-1)

This gives you a way to construct Fn(i+1), Fn(i), Fn(i-1) from Fn(i), Fn(i-1), Fn(i-2) in the same way that the usual linear-time Fibonacci algorithm works (constructing Fib(n+1), Fib(n) from Fib(n), Fib(n-1)). These recurrence relations are encoded in the line that updates the variables a to i.

Number of ways to form array using only 3 elements?

The approach I would take is NOT to create the actual array. I would instead approach it by analyzing your restrictions.

1, 2 : 2
1, 3 : 3
2, 1 : 1
2, 3 : 0
3, 1 : 4
3, 2 : 3

So there are only a limited number of transitions allowed in your system.

So my starting point would be to count all of the possible transition combinations, associated with a min-length n for each. This can be performed using some brute force method, although there may or may not be a more efficient method.

A sample of the output resulting from the brute force method should be as below...

• min-length 2 transitions:

1, 2
1, 3
2, 1
3, 1
3, 2
So, n-2 pattern count = 5.

• min-length 3 transitions:

1, 2, 1
1, 3, 1
1, 3, 2
2, 1, 2
2, 1, 3
3, 1, 2
3, 1, 3
3, 2, 1
So, n-3 pattern count = 8.

Once we have calculated all of the possible combination counts for each minimum length, we perform permutations mathematics based on the actual input n. We can reuse the original structure we have created to perform calculations for multiple input of n very fast.

For example, where n = 3, we start with 3 for null-transitions. Then we add 8 for no permutations of transitions requiring min-length n. Then we calculate the permutations for min-length n - 1, n - 2, etc until n - x = 2. Permutations are calculated by shifting the position of each transition with excess space. i.e. where n = 3 and min-n = 2, excess space = 1, so we can shift the transition left/right by 1, giving us 2 patterns instead of 1. So since there are 5 patterns that are of length 2, and each can be transitioned to 2 patterns, that would give us 10 patterns. So we have 10 + 8 + 3 = 21.

To clarify the maths further, I'll use n = 10 on the n-3 pattern. We have 9 transition slots and 2 transitions and can apply permutation mathematics:

1. The first transition may occur anywhere in the first 8 of 9 transition slots. Which slot is selected determines where the second transition may go, but lets ignore that for now. Then this becomes 9!/7!. However, this includes all out of order combinations, so we want to further divide that by 2!. So we have 9 * 4 = 36 combinations, * pattern count of n-3 patterns = 36 * 8. Add this to the n-2 patterns, n-4 patterns, etc...

This becomes generalized to:

• sum(i: n ... 1) { patternCount(i) * ((n - 1)!)/(n - i - 1)!/i! }

Given a number N, find the number of ways to write it as a sum of two or more consecutive integers

We can use dynamic programming to calculate the sums of 1+2+3+...+K for all K up to N. sum[i] below represents the sum 1+2+3+...+i.

sum = [0]
for i in 1..N:
  append sum[i-1] + i to sum

With these sums we can quickly find all sequences of consecutive integers summing to N. The sum i+(i+1)+(i+2)+...j is equal to sum[j] - sum[i] + 1. If the sum is less than N, we increment j. If the sum is greater than N, we increment i. If the sum is equal to N, we increment our counter and both i and j.

i = 0
j = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
  if cur_sum >= N:
    i++

There are better alternatives than using this dynamic programming solution though. The sum array can be calculated mathematically using the formula k(k+1)/2, so we could calculate it on-the-fly without need for the additional storage. Even better though, since we only ever shift the end-points of the sum we're working with by at most 1 in each iteration, we can calculate it even more efficiently on the fly by adding/subtracting the added/removed values.

i = 0
j = 0
sum = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
    sum += j
  if cur_sum >= N:
    sum -= i
    i++

Get all numbers that add up to a number

Here is one way to solve this problem:

def sum_to_n(n, size, limit=None):
    """Produce all lists of `size` positive integers in decreasing order
    that add up to `n`."""
    if size == 1:
        yield [n]
        return
    if limit is None:
        limit = n
    start = (n + size - 1) // size
    stop = min(limit, n - size + 1) + 1
    for i in range(start, stop):
        for tail in sum_to_n(n - i, size - 1, i):
            yield [i] + tail

You can use it like this.

for partition in sum_to_n(6, 3):
    print partition

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

Is there a way to recursively find the different ways a set of numbers can add up to a certain number?

This does not use recursion, but itertools.combinations_with_replacement:

def all_combs(y, x=range(1, 5+1)):
    all_combs = []
    for i in range(1, y+1):
        combs = combinations_with_replacement(x, i)
        all_combs.extend([comb for comb in combs if sum(comb) == y])
    return all_combs

combs = all_combs(5)
# [(5,), (1, 4), (2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 1, 2), (1, 1, 1, 1, 1)]
num_combs = len(combs) # 7

Given n, find the maximum numbers added to get n

I was about to post the answer but @Cruise Liu beat me to it. Ill try explaining it a bit .
Its a type of integer partitioning but you dont need to generate the elements since you're only interested in the 'number of elements'. i.e. the final answer 3 and not {1, 2, 3}

Given a number N, you have another restriction that numbers cannot repeat.
Hence the best case would be if N is actually a number say 1, 3, 6, 10, 15

i.e. f(x) = x * (x + 1) / 2. 

For example, take 6. f(x) = 6 exists. specifically f(3) = 6 . Thus you get the answer 3.

What this means is that if there is an integer X that exists for f(x) = N, then there is a set of numbers 1, 2, 3 ... x that when added up give N. And this is the maximum number possible (without repitition).

However, there are cases in f(x) = N where x is not an integer.

f(x) = x * (x + 1 ) / 2 = N
i.e. x**2 + x = 2*N
x**2 + x - 2*N = 0

Solving this quadratic we get

Since the number x is not negative we can't have

So we're left with

For N = 6

A perfect Integer. But for N = 12

which is 8.845 / 2 which is a fraction. The floor value is 4, which is the answer.

In short: Implement a function
f(N) = (int) ((-1.0 + sqrt(1 + 8*N))/2.0 )

i.e.

int max_partition_length(int n){
    return (int)((-1.0 + sqrt(1 + n*8))/2);
}

Get N-sized numbers that add up to a number X

This is closely related to partitions of an integer, which finds all distinct ways of breaking an integer into the sum of positive integers. For instance, the partitions of 4 are 4, 3 + 1, 2 + 2, 2 + 1 + 1, and 1 + 1 + 1 + 1. Although there is probably a more direct way of calculating your sum, it's easy to do atop a partitions function:

const partitions = (n, max = n) =>
  n == 0
    ? [[]]
  : n < 0
    ? []
  : Array .from ({length: Math .min (n, max)}, (_, i) => i + 1) // or use a `ramge` function
     .reverse()
     .flatMap (x => partitions (n - x, x) .map (p => [x, ...p]))

const sumToN = (n, c) => 
  partitions (n + c) 
    .filter (p => p .length == c)
    .map (p => p .map (x => x - 1))

console .log (sumToN (6, 3))

.as-console-wrapper {max-height: 100% !important; top: 0}