This site is supported by donations to The OEIS Foundation.
Superincreasing sequences
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] i.e.
Contents
Examples
For example, {1, 3, 6, 13, 27, 52} is a superincreasing sequence, but {1, 3, 4, 9, 15, 25} is not.[2]
Python source code example
The following Python source code tests a sequence of numbers to determine if it is superincreasing
sequence = [1,3,6,13,27,52] sum = 0 test = True for n in sequence: print "Sum: ", sum, "Element: ", n if n <= sum: test = False break sum += n print "Superincreasing sequence? ", test
and 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
Minimally superincreasing integer sequences
A sequence of positive integers might be said to be minimally superincreasing if every element of the sequence is equal to the sum of all previous elements in the sequence, plus one, i.e.,
The minimally superincreasing sequence of positive integers starting at is thus
given by the formula
The sequence of powers of 2 is the "minimal" (i.e. with lowest terms) minimally superincreasing integer sequence
The "minimal" (i.e. with lowest terms, corresponding to ) minimally superincreasing (positive) integer sequence is thus
- {1, (1) + 1 = 2, (1+2) + 1 = 4, (1+2+4) + 1 = 8, (1+2+4+8) + 1 = 16, (1+2+4+8+16) + 1 = 32, (1+2+4+8+16+32) + 1 = 64, (1+2+4+8+16+32+64) + 1 = 128, ...}
which is the sequence of nonnegative powers of two
This results from the well-known formula
This implies that superincreasing sequences of positive integers grow at least as fast as the sequence of powers of 2, thus excluding sequences with polynomial growth, sequences with subexponential growth or sequences with exponential growth but with base less than two (e.g. the Fibonacci sequence, which is asymptotic to (1.6180339887499...) / 2.2360679774998...)
Suppose that a positive real number . If is a superincreasing sequence of positive real numbers and every , then we can always determine the unique 's simply by knowing , e.g. via a greedy algorithm. If then every positive real number is represented (in a unique way.) This is analogous to the fact that, for any natural number, we can always determine which bits are on and off in the binary bitstring representing the number.
k-superincreasing sequences
- This is a proposed definition, which may be removed if not considered of interest. — Daniel Forgues 06:03, 21 October 2011 (UTC)
A sequence of positive real numbers could be called k-superincreasing if every element of the sequence is greater than times the sum of all previous elements in the sequence, i.e.,
Superincreasing correspond to the case .
Minimally k-superincreasing integer sequences
A sequence of positive integers could thus be said to be minimally -superincreasing if every element of the sequence is equal to times the sum of all previous elements in the sequence, plus one, i.e.,
The minimally -superincreasing sequence of positive integers starting at is thus
given by the formula
The sequence of powers of (k+1) is the "minimal" (i.e. with lowest terms) minimally k-superincreasing integer sequence
The "minimal" (i.e. with lowest terms, corresponding to ) minimally -superincreasing (positive) integer sequence is thus
which is the sequence of nonnegative powers of
This results from the well-known formula
For example, gives
- {1, 9 * (1) + 1 = 10, 9 * (1+10) + 1 = 100, 9 * (1+10+100) + 1 = 1000, 9 * (1+10+100+1000) + 1 = 10000, 9 * (1+10+100+1000+10000) + 1 = 100000, 9 * (1+10+100+1000+10000+100000) + 1 = 1000000, ...}
This implies that -superincreasing sequences of positive integers grow at least as fast as the sequence of powers of , thus excluding sequences with polynomial growth, sequences with subexponential growth or sequences with exponential growth but with base less than
Suppose that a positive real number . If is a -superincreasing sequence of positive real numbers and every , then we can always determine the unique 's simply by knowing , e.g. via a greedy algorithm. If then every positive real number is represented (in a unique way.) This is analogous to the fact that, for any natural number, we can always determine which are the digits in the base (k+1) numeral system represention of the number.
See also
References
- ↑ Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematics and Its Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), ISBN 1584881275.
- ↑ 2.0 2.1 Bruce Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, pages 463-464, Wiley; 2nd edition (October 18, 1996), ISBN 0471117099.