Make the frequent cases fast and the rare case correct

Collatz Conjecture – Problem 14 – Project Euler – ACM’s 3n+1 problem

The Collatz conjecture is an unsolved conjecture in mathematics named after Lothar Collatz, who first proposed it in 1937. The conjecture is also known as the 3n + 1 conjecture, the Ulam conjecture (after Stanisław Ulam), Kakutani’s problem (after Shizuo Kakutani), the Thwaites conjecture (after Sir Bryan Thwaites), Hasse’s algorithm (after Helmut Hasse), or the Syracuse problem the sequence of numbers involved is referred to as the hailstone sequence or hailstone numbers or as wondrous numbers

Take any natural number n. If n is even, divide it by 2 to get n / 2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called “Half Or Triple Plus One”, or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness

Paul Erdős said about the Collatz conjecture: “Mathematics is not yet ready for such problems.” He offered $500 for its solution. – Grateful to Wikipedia for this wonderful introduction.

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.

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

For instance, starting with n = 6, one gets the sequence 6, 3, 10, 5, 16, 8, 4, 2, 1.
n = 11, for example, takes longer to reach 1: 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

The sequence for n = 27, listed and graphed below, takes 111 steps, climbing to 9232 before descending to 1.

Pseudo code:

    function collatz(n)

        while n > 1

            show n
            if n is odd then

                set n = 3n + 1


                set n = n / 2



    show n 

Cool Application or Visual Property

Iterating a optimized collatz map in the complex plane produces the Collatz fractal.

Collatz iterations on the Ulam Spiral can be seen in this video

An online collatz chain length calculator can be found here


ACM question. : 3n+1 problem [you can find Java and C++ implementation in the link]

Consider the following algorithm to generate a sequence of numbers. Start with an
integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
process with the new value of n, terminating when n = 1. For example, the following
sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.
For an input n, the cycle-length of n is the number of numbers generated up to and
including the 1. In the example above, the cycle length of 22 is 16. Given any two
numbers i and j, you are to determine the maximum cycle length over all numbers
between i and j, including both endpoints.
The input will consist of a series of pairs of integers i and j, one pair of integers per
line. All integers will be less than 1,000,000 and greater than 0.
For each pair of input integers i and j, output i, j in the same order in which they
appeared in the input and then the maximum cycle length for integers between and
including i and j. These three numbers should be separated by one space, with all three
numbers on one line and with one line of output for each line of input.
Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

Problem 14 – Project Euler

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

import time

ulam = { 1: 1 }
def collatz(n):
    if not n in ulam:
        ulam[n] = collatz(3*n+1 if n%2 else n/2) + 1
    return ulam[n]

max = (0,0)
limit = raw_input("Enter the Max limit: ")
limit = int(limit)
index = raw_input("Enter the starting Number: ")
index = int(index)
#limit = 200
start = time.strftime('%s')
if index % 2 == 0:
        for i in range(index+3,limit,2):
                length = collatz(i)
                if length > max[1]: max = (i,length)
if index % 2 != 0:
        for i in range(index,limit,2):
                length = collatz(i)
                if length > max[1]: max = (i,length)

end = time.strftime('%s')
time = int(end) - int(start)
print "(Number, Chain Length) =", max
print "Time to execute the algorithm =", time ,"Second(s)"


labuser@ubuntu:~$ python
Enter the Max limit: 1000000
Enter the starting Number: 0
(Number, Chain Length) = (837799, 525)
Time to execute the algorithm = 10 Second(s)

labuser@ubuntu:~$ python
Enter the Max limit: 10
Enter the starting Number: 1
(Number, Chain Length) = (9, 20)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$ python
Enter the Max limit: 200
Enter the starting Number: 100
(Number, Chain Length) = (171, 125)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$ python
Enter the Max limit: 210
Enter the starting Number: 201
(Number, Chain Length) = (207, 89)
Time to execute the algorithm = 0 Second(s)

labuser@ubuntu:~$ python
Enter the Max limit: 1000
Enter the starting Number: 900
(Number, Chain Length) = (937, 174)
Time to execute the algorithm = 0 Second(s)

3 responses to “Collatz Conjecture – Problem 14 – Project Euler – ACM’s 3n+1 problem

  1. my emai id is my name September 5, 2013 at 2:15 pm

    is this how you optimise code?? why cant you just create a mapping of collatz’s accepted numbers and calculate run the code until it reaches such a collatz accepted number, which will mean that this number is also collatz acceptable.

    let the highest calculated collatz number be p. if while calculating a number we find that n has become larger than p, we temporarily push this number to a stack, as an indicator of it being a possible collatz acceptable number, and continue with our calculations. when n reaches a number equal to a collatz acceptable number it is proven that it is collatz acceptable, along with all the numbers in the stack. otherwise if n equals a number in the stack, it is proven collatz unacceptable.

    also, if we are able to prove (b^x) is collatz acceptable for a range of values, it would be better to do so instead, where b is prime, and x is as large as possible for enough numbers that cascade down to a single collatz acceptable number…. just my 2 cents….

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: