#Recurrence formula x_{n+1} = f(x_{n})When the columns given in have a cycle
#Measure the length l to enter the circulation and the length m of the circulation
def find_cycle(x0, limit = nil, &f)
#Set limit on the number of cycle detections (end nil or Float)::Infinite with INFINITY)
seq = 1..limit
# step1:Detect circulation
# -Both x and y start at the starting point (x0)
# -x advances by one, y advances by two
# -→ If you enter the circulation, be sure to x==Become y
# -→ This x==The position of y is parallel to x0
#(Always f for a sufficiently large n^{n}(x) == f^{n}(x0)Holds)
x = y = x0
k = seq.find { (x = f[x]) == (y = f[f[y]]) }
raise "failed to detect a cycle" unless k
# step2:Measure the length to enter the circulation
# -Return x to the starting point and y continue from the end of step1
# -Advance x and y one by one (maintain parallel positional relationship)
# -→ Be sure to x when you enter the circulation==Become y
x = x0
l = (x == y) ? 0
: seq.find { (x = f[x]) == (y = f[y]) }
# step3:Measure the length of the circulation
# -Both x and y start in the cycle (here at the end of step2)
# -x advances by one, y advances by two
# -→ x is exactly one lap and always x==Become y
m = seq.find { (x = f[x]) == (y = f[f[y]]) }
[l, m]
end
if $0 == __FILE__
#Test: x_{n+1} ≡ x_{n} * 2 (mod 360), x_{0} = 133
l, m = find_cycle(133) { |x| x * 2 % 360 }
p [l, m]
# x_{l} == x_{l+m}(And x_{l-1} != x_{l+m-1}) Should be
ary = (l + m).times.inject([133]) { |a, _| a << (a.last * 2 % 360) }
ary.each_with_index { |x, i| puts "%3d %4d" % [i, x] }
end
Recommended Posts