Superincreasing sequence explained

In mathematics, a sequence of positive real numbers

(s _{1,} s _{2,} ...) is called superincreasing if every element of the sequence is greater than the sum of all previous elements in the sequence.^{[1] [2]}

Formally, this condition can be written as

s _{n+1} > \sum ^{n} _{j =1} s _{j} for all n ≥ 1.

Program

The following Python source code tests a sequence of numbers to determine if it is superincreasing:

sequence = [1, 3, 6, 13, 27, 52]total = 0test = Truefor 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

Examples

• (1, 3, 6, 13, 27, 52) is a superincreasing sequence, but (1, 3, 4, 9, 15, 25) is not.^[2]
• The series a^x for a>=2

Properties

• Multiplying a superincreasing sequence by a positive real constant keeps it superincreasing.

See also

• Merkle–Hellman knapsack cryptosystem

References

1. Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000),
2. Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 463-464, Wiley; 2nd edition (October 18, 1996),