A232462 Number of iterations of the map n -> f(f(f(...f(n)...))) to reach the end of the cycle, where f(n) = A006666(n), the initial number n is not counted.

0, 1, 4, 2, 3, 0, 6, 5, 8, 4, 5, 7, 7, 8, 8, 3, 9, 9, 9, 1, 1, 6, 6, 6, 4, 6, 7, 8, 8, 8, 11, 4, 10, 5, 5, 9, 9, 9, 7, 7, 7, 7, 2, 8, 8, 8, 11, 9, 10, 10, 10, 9, 9, 12, 12, 9, 7, 9, 7, 9, 9, 7, 7, 1, 10, 10, 10, 6, 6, 6, 11, 4, 0, 4, 6, 4, 4, 7, 7, 6, 4, 7, 7, 6, 6, 2, 2, 8, 2, 8, 8, 8, 8, 11, 11, 5, 7, 10, 10, 10, 10, 10, 10, 5, 7, 5, 2, 5, 5, 5, 9, 9, 5, 7, 7, 9, 9, 7, 7, 9

Offset: 1

Author

Christoph Neubauer, Nov 24 2013

Keywords

• nonn

Comments

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. As multiplying by 3 and adding 1 always gives an even number, the next step is always a division by 2. So there already exists a shortened version of Collatz problem: If n is even, multiply it by three, add one and divide the result by two, else divide it by two. A006666(n), which is the Number of halving steps to reach 1 in '3x+1' problem, also is the number of all steps for the shortened form to reach 1. If you map this function onto itself, you'll get a sequence that ends with 1 or 6 (for 6, 20, 21, 43, 64, 86, ...) or 73 (for 73, 216, 218, ...).

Examples

			For n = 3, the mapping of the shortened Collatz sequence is [3, 5, 4, 2, 1], its number of steps is 4. For n=6 the sequence is [6], the number of steps is 0.
		

Links

• Christoph Neubauer, Table of n, a(n) for n = 1..10000

Programs

Python

#!/usr/bin/env python
# output to
outputStr = "b232462.txt"
# max index
maxIndex = 10000
# goodies
sep=" "
eol="\n"
# subroutine for collatz sequence; classical and shortened
def collatz (n, k):
    # put starting number to list
    list = [n]
    # collatz assumption used as end criterion
    while (n > 1):
        # collatz formula
        if (n%2 == 0):
            n = n // 2
        else:
            n = (3*n + 1) // k  # if k==2 --> shortened
        # put new number to list
        list.append(n);
    # return complete list
    return list
# subroutine for collatz composition; classical and shortened
# composition:  collatz (collatz (collatz (...)))
def composition (n, k):
    # put starting number to list
    list = [n]
    # calculate collatz(starting number)
    l = len (collatz(n, k))-1
    # while we do not have a cycle
    while ((l >= 1) and (not l in list)):
        # put new number to list
        list.append(l)
        # get next collatz number
        l = len (collatz(l, k))-1
    # return complete list
    return list
# open output
output = open (outputStr, 'w')
# for index 1 to maxIndex
for i in range (1, maxIndex+1):
    # compute complete composition sequence
    list = composition(i, 2)
    # get number of steps
    l = len(list)-1
    # write to file
    output.write (str(i)+sep+str(l)+eol)
# close output
output.close ()