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. [1][2]

Formally, written:

Example

For example, (1,3,6,13,27,52) is a superincreasing sequence, but (1,3,4,9,15,25) is not.[2] 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
gollark: `battop` says the battery is at 97.80% functioning, which is good.
gollark: I probably could.
gollark: This one can theoretically do about 8 hours of light web browsing on charge, but I avoid using it away from a plug because using the battery slightly degrades it...
gollark: I would just carry a laptop in, you know, a laptop bag.
gollark: Well, reasonably priced given the market, but quite expensive by my price ranges...

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), ISBN 1-58488-127-5
  2. Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 463-464, Wiley; 2nd edition (October 18, 1996), ISBN 0-471-11709-9
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.