# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Collatz conjecture

The Collatz conjecture, named after Lothar Collatz (1910—1990), also known as the 3n + 1 conjecture, the Ulam conjecture after Stanislaw Ulam, or the hailstone sequence or hailstone numbers, was first stated in 1937 and concerns the following process:

1. Pick any positive integer n.
2. If n is even, divide it by two; if it is odd, multiply it by three and add one.
3. If n = 1, stop; else go back to step 2.

Sometimes the problem is stated differently. The termination condition ("If n = 1, stop") is removed from the procedure, so the sequence does not end. If the problem is stated this way, the conjecture becomes the statement that the sequence always ends up in the repeating loop 1, 4, 2, 1, 4, 2... This version is written using modular arithmetic as:

$f(n) = \begin{cases} n/2 &\mbox{if } n \equiv 0 \\ 3n+1 & \mbox{if } n\equiv 1 \end{cases} \pmod{2}.$

For instance, starting with n = 6, one get the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1. The Collatz conjecture says that this process always reaches 1, no matter what the start value.

A specific Collatz sequence can be easily computed:

def collatz(n)
print n
if n.odd? and n > 1
collatz(3n + 1)
else if n.even?
collatz(n / 2)

 Contents

## Supporting arguments

The conjecture has been checked by computer for all start values up to 3 × 253 = 27,021,597,764,222,976, but a proof of the conjecture has not been found. Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution. There are some heuristic, statistical arguments supporting the conjecture: if one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they eventually hit the bottom. ## Other ways of looking at it ### In reverse There is another approach to prove the following conjecture, which considers the bottom-up method of growing the Collatz graph. The Collatz graph is defined by an inverse relation, $R(n) = \begin{cases} 2n & \mbox{if } n\equiv 0,1 \\ 2n, (2n-1)/3 & \mbox{if } n\equiv -1 \end{cases} \pmod{3}.$ So, instead of proving that all natural numbers eventually lead to 1, we can prove that 1 leads to all natural numbers. Also, the inverse relation forms a tree except for the 1-2 loop. Note that the relation being inverted here is (3n + 1) / 2 (see Optimizations below). ### As rational numbers The natural numbers can be converted to rational numbers in a certain way. To get the rational version, find the highest power of two less than or equal to the number, use it as the denominator, and subtract it from the original number for the numerator (527 → 15/512). To get the natural version, add the numerator and denominator (255/256 → 511). The Collatz conjecture then says that the numerator will eventually equal zero. The Collatz function changes to : $f(n, d) = \begin{cases} (3n + d + 1)/2d & \mbox{if } 3n + d + 1 < 2d \\ (3n - d + 1)/4d & \mbox{if } 3n + d + 1 \ge 2d \end{cases}$ (n = numerator; d = denominator) This works because 3x + 1 = 3(d + n) + 1 = (2d) + (3n + d + 1) = (4d) + (3n - d + 1). Reducing a rational before every operation is required to get x as an odd. ### As an abstract machine Repeated applications of the Collatz function can be represented as an abstract machine that handles strings of bits. The machine will perform the following three steps on any odd number until only one "1" remains : 1. Add the original to the original with a "1" appended to the end. 2. Remove all trailing "0"s. 3. Repeat until the string length is one. ## Optimizations If n is a multiple of 4, it can be divided by 4. • Reason: It is initially even. When it is divided by two, it is still even. If n is odd, 3n + 1 is even. • If n is odd, one step can be skipped by finding (3n + 1) / 2 • Reason: an odd times an odd is always an odd (neither contributes a factor of 2 and without a 2, it cannot be even), so 3n is odd. • For instance: 3 × 35 + 1 = 106 3m + 1 is guaranteed to be in the Collatz sequence of 4m + 1. • If n ≡ 1 (mod 4), n can be converted to (n - 1) / 4 as many times as possible, saving a step every time this conversion is done. Whatever number is left, even or odd, will then be converted to 3n + 1. • Reason: 4m + 1 is always odd, so it will turn into 3(4m + 1) + 1 = 12m + 4 = 4(3m + 1) and then can be divided by two twice. • For instance: 405 can be converted: 405 → 101 → 25 → 6 → 19. The normal Collatz sequence also contains 19: 405 → 1216 → 608 → 304 → 152 → 76 → 38 → 19 The above facts can be used to create a new version of the Collatz function : $f(n) = \begin{cases} n / 4 & \mbox{if } n \equiv 0 \\ 3 g\left( (n-1)/4 \right) +1 & \mbox{if } n \equiv 1 \\ n / 2 & \mbox{if } n \equiv 2 \\ (3n+1)/2 & \mbox{if } n \equiv 3 \end{cases} \pmod{4}$ $g(n) = \begin{cases} n & \mbox{if } n \;\not\equiv\; 1 \\ g \left( (n-1)/4 \right) & \mbox{if } n \equiv 1 \end{cases} \pmod{4}.$ ## See also ## References and external links 03-10-2013 05:06:04 The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines. Start by looking for your science kit review or science toy review. Compare prices but remember, Price$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice