What is a rho shaped sequence?

Question

I came across this in the solution presented by Saurabh Kr Vats at this http://www.careercup.com/question?id=14990323

He says:

# Finally, the sequence could be "rho-shaped." In this 
# case, the sequence looks something like this: 
# 
# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} 
# ^ | 
# | | 
# +-----------------------+ 
# 
# That is, the sequence begins with a chain of elements that enters a cycle, 
# then cycles around indefinitely. We'll denote the first element of the cycle 
# that is reached in the sequence the "entry" of the cycle.

I searched online and reached cycle detection. I could see the rho shaped being formed when we reach the start/end of a cycle and try to go to an element which is not adjacent to it. I did not however understand the representation of the sequence or its usage.

It would be great if someone could explain it with an example.

score 9 · Accepted Answer · answered Jan 02 '16 at 14:30

It means literally in the shape of the Greek letter rho, which is "ρ". The idea is that if you map the values out as a graph, the visual representation forms this shape. You could also think of it as "d" shaped or "p" shaped. But look carefully at the font and notice that the line or stem extends slightly past the loop, while it doesn't on a rho. Rho is a better description of the shape because the loop never exits; i.e., there shouldn't be any lines leading out of the loop. That and mathematicians love Greek letters.

You have some number of values which do not repeat; these form a line or the "stem" of the "letter". The values then enter a loop or cycle, forming a circle or the "loop" of the "letter".

For example, consider the repeating decimals 7/12 (0.5833333...) and 3227/55 (5.81441441444...). If you make your sequence the digits in the number, then you can graph these out to form a rho shape. Let's look at 3227/55.

x0 = 5
x1 = 8
x2 = 1
x3 = 4
x4 = 4
x5 = 1 = x2
x6 = 4 = x3
x7 = 4 = x4
...

You can graph it like so:

5 -> 8 -> 1 
         ^  \
        /    v
        4 <- 4

You can see this forms a "ρ" shape.

Nice explanation of the shape, and nice example. – John Coleman Jan 02 '16 at 14:42 — John Coleman, Jan 02 '16 at 14:42

score 2 · Answer 2 · answered Jan 02 '16 at 14:40

The comment in the code snippet looks incomplete. In context, I think that

# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}

should have been

# x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j} = x_k

which would make j the length of the cycle and x_0 -> x_1 -> ... -> x_{k-1} the "tail" of the sequence before you get to the circle that the tail is attached to.

A nice example is provided by the 3n+1 problem. This is where you start with a seed number which is a positive integer and either divide it by 2 if it is even or multiply it by 3 and add 1 if it is odd. With seed 5 this gives the sequence

5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> ...

which can be written like

5 -> 16 -> 8 -> 4
               /  \
              1 <- 2

which sort of looks like a rho which has fallen over.

The Collatz Conjecture is that all seeds yield rho-shaped sequences which end up in the same cycle of length 3.

Thanks a lot. The completed comment made it a lot clearer. – tanvi Jan 02 '16 at 20:55 — tanvi, Jan 02 '16 at 20:55

score 0 · Answer 3 · answered Jan 02 '16 at 14:18

If you have a sequence that turns into a cycle then at the point where the initial sequence meets the cycle there is a value that you can get to in two ways, either from the initial sequence or from the cycle.

I don't know if this is a representative example, but suppose that the array holds {1,2,3,1,0} and you start at 0. Then you end up with 0->1->2->3->1->2->3->1... and you find that f(0)=f(3)=1

What is a rho shaped sequence?

3 Answers3