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.Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 463-464, Wiley; 2nd edition (October 18, 1996),
Formally, this condition can be written as
for all n ≥ 1.
Program The following Python source code tests a sequence of numbers to determine if it is superincreasing:
def is_superincreasing_sequence(sequence) -> bool: """Tests if a sequence is superincreasing.""" total = 0 result = True for n in sequence: print("Sum: ", total, "Element: ", n) if n <= total: result = False break total += n return result
sequence = [1, 3, 6, 13, 27, 52] result = is_superincreasing_sequence(sequence) print("Is it a superincreasing sequence? ", result)
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 Is it a superincreasing sequence? True
Examples (1, 3, 6, 13, 27, 52) is a superincreasing sequence, but (1, 3, 4, 9, 15, 25) is not. 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