# Application of Brent's Cycle Detection Algorithm

I would like to find cycles in a finite length list of numbers where there is no function:

xn = f(xn-1).

For example, in the list:

3, 12, 11, 46, 1034, 23, 12, 11, 46, 1034, 5

x0 = 3, x1 = 12, etc. and the cycle starts at x1 with a length of 4.

There is a Java implementation of Brent's Cycle Algorithm here which includes some sample data with the expected output.

Brent Cycle Algorithm Test

Enter size of list
9

Enter f(x)
6 6 0 1 4 3 3 4 2

Enter x0
8

First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6

Length of cycle : 3
Position : 4


Here you can see that x0 = 8 and that the 8th entry in the entered list is 2 (using a zero based index), which when used as an index gives 0, which when used as an index gives 6 and so on producing the first 9 elements in the sequence 8, 2, 0, 6, etc.

My problem (likely due to my lack of understanding about the purpose or use of Brent's Algorithm) is that the numbers in the list I provided (3, 12, 11, 46, etc.) cannot be used as indexes (indicies?) to access the next number in the list. In other words, there is no f(x) such that xn = f(xn-1).

Does this put Brent's Algorithm out of reach for my application? Maybe there's a simple modification to Brent's Algorithm that hasn't occurred to me.

• In that case you don't necessarily have a cycle, right? So an adaptation of the algorithm may not terminate. – md5 Jun 23 '17 at 19:45
• @md5 "In that case you don't necessarily have a cycle, right?" That depends on the definition of a cycle, and there, I am uninformed. The data in my example has a cycle: it is 12, 11, 46, 1034 (which repeats once). Does this constitute a cycle in the Brent's Cycle Algorithm sense? Or must my data be representable by a function f(x) such that x sub n = f(x sub n-1) in order to constitute a cycle in the Brent's Cycle Algorithm sense? – mbmast Jun 23 '17 at 20:26
• A cycle is a sequence that keeps repeating forever and can only exist in an infinite sequence. For example, 1/x contains a cycle in its decimal expansion for every x. – Albert Hendriks Jul 24 '17 at 4:34