Superincreasing sequence: Difference between revisions
Appearance
Content deleted Content added
No edit summary |
Improved Python example. I added parentheses to the print call so it works in Python 3. I also renamed the "sum" variable to "total" to avoid overwriting the built-in "sum" function. |
||
Line 8: | Line 8: | ||
For example, <nowiki>(1,3,6,13,27,52)</nowiki> is a '''superincreasing sequence''', but <nowiki>(1,3,4,9,15,25)</nowiki> is not.<ref name="schneier"/> The following [[Python (programming language)|Python]] source code tests a sequence of numbers to determine if it is superincreasing: |
For example, <nowiki>(1,3,6,13,27,52)</nowiki> is a '''superincreasing sequence''', but <nowiki>(1,3,4,9,15,25)</nowiki> is not.<ref name="schneier"/> The following [[Python (programming language)|Python]] source code tests a sequence of numbers to determine if it is superincreasing: |
||
<source lang=python> |
<source lang="python"> |
||
sequence = [1,3,6,13,27,52] |
sequence = [1,3,6,13,27,52] |
||
total = 0 |
|||
test = True |
test = True |
||
for n in sequence: |
for n in sequence: |
||
print |
print("Sum: ", total, "Element: ", n) |
||
if n <= |
if n <= total: |
||
test = False |
test = False |
||
break |
break |
||
total += n |
|||
print |
print("Superincreasing sequence? ", test) |
||
</source> |
</source> |
||
Revision as of 18:17, 16 June 2016
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
See also
References
- ^ Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematical & Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), ISBN 1-58488-127-5
- ^ a b 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