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,3

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, ...).

Links

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

Example

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.

Prog

(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 ()

Crossrefs

Sequence in context: A134977 A199081 A338106 * A266141 A266147 A326046

Adjacent sequences: A232459 A232460 A232461 * A232463 A232464 A232465

Keyword

nonn

Author

Christoph Neubauer, Nov 24 2013

Status

approved