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)

    “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)

    “Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
    —Robert Benchley (1889–1945)

    “Involuntary mental hospitalization is like slavery. Refining the standards for commitment is like prettifying the slave plantations. The problem is not how to improve commitment, but how to abolish it.”
    —Thomas Szasz (b. 1920)