This site is supported by donations to The OEIS Foundation.

Superincreasing sequences

From OeisWiki
Jump to: navigation, search


This article page is a stub, please help by expanding it.


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.

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

  1. Richard A. Mollin, An Introduction to Cryptography (Discrete Mathematics and Its Applications), Chapman & Hall/CRC; 1 edition (August 10, 2000), ISBN 1584881275.
  2. 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.