|
|
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.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|