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, statement and/or problem:

    “I think, therefore I am is the statement of an intellectual who underrates toothaches.”
    —Milan Kundera (b. 1929)

    “After the first powerful plain manifesto
    The black statement of pistons, without more fuss
    But gliding like a queen, she leaves the station.”
    —Stephen Spender (1909–1995)

    “The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
    —Frank Pittman (20th century)