(* Efficient Cycle Detection - for Collatz 3n+C Seed7 version using Brent's Cycle Detection Algorithm see Wikioedia article: http://en.wikipedia.org/wiki/Cycle_detection ecd010.sd7 *) $ include "seed7_05.s7i"; include "bigint.s7i"; # # use an output structure compatible with other cycle detection programs # const type: cycle is new struct var bigInteger: the_attractor is 0_; # smallest number in the cycle var bigInteger: the_initiator is 0_; # seed number that lead to the cycle var bigInteger: the_gcd is 0_; # gcd of cycle numbers var bigInteger: the_length is 0_; # length of cycle (in odd numbers) end struct; # # record all attractors found (with their stats) # var array cycle: cycle_stats is 0 times cycle.value; # # but only track unique ones, so keep a set of attractors found and # only add a cycle_stats record if attractor is unique # var set of bigInteger: att is (set of bigInteger).EMPTY_SET; # # the Collatz funtion (assumes n is odd): (3n+C)/2**LSB # const func bigInteger: collatz (in bigInteger: n, in bigInteger: C) is func result var bigInteger: cn is 0_; local var integer: LSB is 0; begin cn := n * 3_ + C; LSB := lowestSetBit(cn); cn >>:= LSB; # remove factors of 2 in one fell swoop end func; # # once cycle is detected, make one sweep of the complete cycle # to find the attractor and the cycle length # const func bigInteger: attractor (in bigInteger: n, in bigInteger: C, in bigInteger: seed) is func result var bigInteger: attractor is 0_; local var bigInteger: cycle_length is 0_; var bigInteger: entry_point is 0_; var bigInteger: cycle_gcd is 0_; var bigInteger: a is 0_; var cycle: attractor_stats is cycle.value; begin attractor := n; entry_point := n; # keep track of this so we know when cycle complete a := n; repeat if a < attractor then # is the new node smaller than current attractor? attractor := a; end if; a := collatz(a,C); cycle_length +:= 1_; if cycle_gcd = 0_ then # only do this once, on first cycle step cycle_gcd := gcd(a,entry_point); end if; until a = entry_point; if attractor not in att then # record the stats (will be printed later) incl(att,attractor); # add it to the set (used to record unique attractors) attractor_stats.the_attractor := attractor; attractor_stats.the_initiator := seed; attractor_stats.the_gcd := cycle_gcd; attractor_stats.the_length := cycle_length; cycle_stats &:= [](attractor_stats); # add attractor & stats to cycle_stats records end if; end func; # # Brent's modified 'tortoise & hare' strategy # const func bigInteger: brent (in bigInteger: n, in bigInteger: C) is func result var bigInteger: tortoise is 0_; local var bigInteger: power is 1_; var bigInteger: lam is 1_; var bigInteger: hare is 0_; var bigInteger: i is 1_; begin tortoise := n; hare := collatz(n,C); while tortoise <> hare do if power = lam then tortoise := hare; power *:= 2_; lam := 0_; end if; hare := collatz(hare,C); lam +:= 1_; end while; tortoise := n; hare := n; for i range 1_ to lam do hare := collatz(hare,C); end for; while tortoise <> hare do tortoise := collatz(tortoise,C); hare := collatz(hare,C); end while; end func; const proc: main is func local var bigInteger: n is 0_; # MUST be odd! var bigInteger: e is 0_; var bigInteger: C is 0_; var bigInteger: o is 0_; var cycle: a is cycle.value; var bigInteger: seed is 0_; begin if (length(argv(PROGRAM)) < 4) then writeln(); writeln("ABORTING -- requires 4 parameters"); writeln(); writeln(" usage: ecd010 N E C O"); writeln(" N - start of seed range (must be odd)"); writeln(" E - end of seed range"); writeln(" C - C of the 3n+C Collatz function"); writeln(" O - options none as of this version (enter 0)"); writeln(); writeln("EXAMPLE: $ ./ecd010 1 40 16777213 0"); writeln(" | | | |"); writeln(" | | | no options"); writeln(" | | use 3n+16777213"); writeln(" | up to 40"); writeln(" start @ 1"); writeln(); writeln("EXAMPLE OUTPUT: 16777213 16777213 16777213 1"); writeln(" 1 1 1 1"); writeln(" 143 3 1 254252"); writeln(" 29 5 1 254241"); writeln(" 119 7 1 254214"); writeln(" | | | |"); writeln(" | | | length of cycle"); writeln(" | | gcd of cycle"); writeln(" | seed that led to this cycle"); writeln(" attractor (smallest node in cycle)"); writeln(); writeln("C is always added to the attractor list even if outside the requested seed range"); writeln("because EVERY 3n+C has C as an attractor whose cycle stats are always C C C 1"); writeln(); exit(PROGRAM); end if; n := bigInteger parse (argv(PROGRAM)[1]); e := bigInteger parse (argv(PROGRAM)[2]); C := bigInteger parse (argv(PROGRAM)[3]); seed := n; # # enter C as the first attractor because 3n+C always has C as an attractor, # always has a gcd of C, and always has a length 1 (sv=[1]) # incl(att,C); a.the_attractor := C; a.the_initiator := C; a.the_gcd := C; a.the_length := 1_; cycle_stats &:= [](a); # # loop though seed values from n to e, some C have attractors > C # but can be run in stages (which may give you duplicate attractors # with different seeds, but they would be the same (and would be suppressed # if both occur in the seed range) # while seed < e do if seed <> C then o := brent(seed,C); # find a number in the cycle using Brent o := attractor(o,C,seed); # and then do the complete cycle (and collect stats) end if; seed +:= 2_; # seeds must always be odd end while; for a range cycle_stats do # all attractors found, print them out write(a.the_attractor); write("\t"); write(a.the_initiator); write("\t"); write(a.the_gcd); write("\t"); writeln(a.the_length); end for; end func;