Superincreasing sequence

In mathematics, a sequence of positive real numbers 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

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

References

Cryptography