Superincreasing sequence

In mathematics, a sequence of positive real numbers [math]\displaystyle{ (s_1, s_2, ...) }[/math] is called superincreasing if every element of the sequence is greater than the sum of all previous elements in the sequence. Formally, this condition can be written as

[math]\displaystyle{ s_{n+1} \gt \sum_{j=1}^n s_j }[/math]

for all n ≥ 1.

Example

For example, (1, 3, 6, 13, 27, 52) is a superincreasing sequence, but (1, 3, 4, 9, 15, 25) is not. The following Python source code tests a sequence of numbers to determine if it is superincreasing:

sequence = [1, 3, 6, 13, 27, 52]
total = 0
test = True
for n in sequence:
    print("Sum: ", total, "Element: ", n)
    if n <= total:
        test = False
        break
    total += n

print("Superincreasing sequence? ", test)

This produces the following output:

Sum:  0 Element:  1
Sum:  1 Element:  3
Sum:  4 Element:  6
Sum:  10 Element:  13
Sum:  23 Element:  27
Sum:  50 Element:  52
Superincreasing sequence?  True

See also

• Merkle–Hellman knapsack cryptosystem