Collatz Conjecture - Statement of The Problem

Statement of The Problem

Consider the following operation on an arbitrary positive integer:

  • If the number is even, divide it by two.
  • If the number is odd, triple it and add one.

In modular arithmetic notation, define the function f as follows:

Now, form a sequence by performing this operation repeatedly, beginning with any positive integer, and taking the result at each step as the input at the next.

In notation:

(that is: is the value of applied to recursively times; )

or

{a_{i}} = \frac{1}{2}{a_{i-1}} - \frac{1}{4}(5a_{i-1}+2)((-1)^{a_{i-1}}-1)

(which yields for even and for odd ).

The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.

That smallest i such that ai = 1 is called the total stopping time of n. The conjecture asserts that every n has a well-defined total stopping time. If, for some n, such an i doesn't exist, we say that n has infinite total stopping time and the conjecture is false.

If the conjecture is false, it can only be because there is some starting number which gives rise to a sequence which does not contain 1. Such a sequence might enter a repeating cycle that excludes 1, or increase without bound. No such sequence has been found.

Read more about this topic:  Collatz Conjecture

Famous quotes containing the words statement of the, statement of, statement and/or problem:

    “Eroticism has its own moral justification because it says that pleasure is enough for me; it is a statement of the individual’s sovereignty.”
    —Mario Vargas Llosa (b. 1936)

    “It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
    —John Dewey (1859–1952)

    “The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.”
    —Ralph Waldo Emerson (1803–1882)

    “Hypocrisy is the essence of snobbery, but all snobbery is about the problem of belonging.”
    —Alexander Theroux (b. 1940)