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)

    “The honor my country shall never be stained by an apology from me for the statement of truth and the performance of duty; nor can I give any explanation of my official acts except such as is due to integrity and justice and consistent with the principles on which our institutions have been framed.”
    —Andrew Jackson (1767–1845)

    “He has the common feeling of his profession. He enjoys a statement twice as much if it appears in fine print, and anything that turns up in a footnote ... takes on the character of divine revelation.”
    —Margaret Halsey (b. 1910)

    “Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
    —Ruth Mompati (b. 1925)