1-Apr-2010

1-Dec-2009

Ok, there is no such thing as an **Ultimate** cycle.

Cycle length is unbounded. One can always construct a cycle of arbitrary length in the 3n+C extension of the Collatz Conjecture.

For any graph structure, there is always a **C** such that that structure is
a cycle in 3n+**C**.

For example, suppose we want to see the structure

A_B | C_D | E | F_G | H | I | J_K | L | M | N | Obecome a cycle in some 3n+C system. First, we count the number of contiguous n/2 operations:

A_3n+1_B | n/2 1 n/2 operation | C_3n+1_D | n/2 | E | n/2 2 n/2 operations | F_3n+1_G | n/2 | H | n/2 | I | n/2 3 n/2 operations | J_3n+1_K | n/2 | L | n/2 | M | n/2 | N | n/2 4 n/2 operations | Owhich becomes our

X*a - Z g = ------- YWe just need to calculate the constants X,Y,Z and we can find a C that will give us a cycle:

def calc_xyz(sv): """calculate Hailstone Function Parameters calc_xyz(sv) sv: sequence vector returns HailstoneFunctionParameters (x,y,z) """ TWO = gmpy.mpz(2) TWE = gmpy.mpz(3) twee = gmpy.mpz(len(sv)) twoo = gmpy.mpz(sum(sv)) x = TWO**twoo y = TWE**twee z = gmpy.mpz(0) for i in xrange(len(sv)): z = z + (TWE**i * TWO**sum(sv[:-(i+1)])) return (x,y,z)Every Hailstone Function has a

Z Crossover Point = --- X-YThat rational number has to be an integer for the Crossover Point to be a cycle. Most of the time it won't be. In fact, the Collatz Conjecture is equivalent to saying "the only positive cycle is Sequence Vector [2]" which implies that only [2] gives you an integer rational Z/(X-Y).

That's for 3n+1, of course. Extending to 3n+C, we find that the **Extended
Crossover Point** is:

Z*C Extended Crossover Point = --- X-YWhich means we can make the non-integer Z/(X-Y) an integer by choosing a C for the Extended Crossover Point that cancels out the denominator of the 3n+1 Crossover Point. This, of course, rules out any C that's a power of 3 as X-Y cannot contain a factor of 3. Any C that's a power of 3 has the same cycles as 3n+1.

Putting it all together:

sequence vector: [1, 2, 3, 4] X,Y,Z parameters: 1024 81 133 crossover point: 133/943 choose C such that sv is a cycle: C: 943 ...which makes the crossover point numerator a cycle element: cycle point: 133 cycle of 3n + 943 odds only: 133 671 739 395 133 cycle length: 4

Hmm...tricky. But yes, I can do it.

But we can't just take **any** Sequence Vector of length 1000, it has to be "prime",
i.e., the list cannot be partitionable into identical sub-partitions.

[1,1,2,1,1,2] can be partitioned as [1,1,2][1,1,2] *identical* as [1,1][2,1][1,2] not identical as [1][1][2][1][1][2] not identical [1,1,2,1,1,2] is "composite" [1,1,2,1,1,3] can be partitioned as [1,1,2][1,1,3] not identical as [1,1][2,1][1,3] not identical as [1][1][2][1][1][3] not identical [1,1,2,1,1,3] is "prime"A "composite" Sequence Vector may be a cycle, but it represents multiple circuits of the smaller sub-cycle and thus, not the cycle length we sought.

If we're not picky about the cycle length and will settle for a power of 2 greater than 1000, we can use a 2-adic sequence to ensure the Sequence Vector is "prime":

To make a 2-adic sequence, start with [1] and:

repeat: 1) extend the sequence by appending a copy of itself 2) increment last number in the list until length>1000 [1] (1) [1,1] (2) [1.2] (1) [1,2,1,2] (2) [1,2,1,3] (1) [1,2,1,3,1,2,1,3] (2) [1,2,1,3,1,2,1,4] . . .This gives us a Sequence Vector of length 1024. Now we'll construct a 3n+C system that has this Sequence Vector as a cycle.

sequence vector: [1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 10, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 9, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 7, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 6, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 11] X,Y,Z parameters: 1615850303565550365035743834433497598022205133485774201606517271376232 7569433945446598600705761456731844358980460949009747059779575245460547 5440761932241415603154386836504980458750988751948260533980288191920337 8413839610932130987808091904716923808523529082292601815252144378794577 0532904303776199561965192760957166694834171210342487393282284747428088 0176631610290389028296655130963542301570751292964320885583629718018592 3092867879917557615082295220184880661664361561356284235541010486257855 0863465661734839271290328348967522998634176499319107762583194718667771 801067716614802322659239302476074096777926805529798115328 3733918487410200435329597541848665882254097767837340077506369317220790 4061726525122999368893880397722046876506543147515810872705459216085858 1351336982809187314191748594262580938807019951956404285571818041046681 2887974029255176680123406172983965747316191523867230462351259348960585 9058828465479354050593620237654780744273058214452705898875625145281779 3413352141920744623027518729185432862375737063985485319476416926263819 972887006907013899256524297198527698749274196276811060702333710356481 8380618382145296825288792901524180703800135275282676893342146898293334 2149440917457995024433772406383954708358485246874943928753464886028226 8878310351555357453778021428255770844432103620335732612336869212817777 7964917643966677627193148443610359458278220620608180674734866573550370 3328095046884939758331533786933062068890362350792456466825065316026649 0369334317955008431452239714094787392821404098097834271190963786050217 9183612695542205538945966334879363029629456547713892003592919329372461 0242904718947286344375888372556268949831575149884155327332010993071794 310582307131219417929559044245738893676516828810562885 crossover point: 8380618382145296825288792901524180703800135275282676893342146898293334 2149440917457995024433772406383954708358485246874943928753464886028226 8878310351555357453778021428255770844432103620335732612336869212817777 7964917643966677627193148443610359458278220620608180674734866573550370 3328095046884939758331533786933062068890362350792456466825065316026649 0369334317955008431452239714094787392821404098097834271190963786050217 9183612695542205538945966334879363029629456547713892003592919329372461 0242904718947286344375888372556268949831575149884155327332010993071794 310582307131219417929559044245738893676516828810562885 / 1615850303565550365035743834433497598022205133485774201606517271376232 7569433945446598600705761456731844358980460949009747059779201853611806 5240326602643873754488504582407212621410911245578943313189882019267825 5414470717051733265761215398173776292712656376833385729394009245096296 1345590112027605299384253953937214738429885638524446346600995950025162 4999951486884216044330907814772018434340288941704971924997723835172044 3738817286297319960301550947126666208958462685731138953761669151043663 0118842634216110085857465973230459013148857022902181498763221831660864 787168460090505124131540553201877819966866103196087758847 choose C such that sv is a cycle: C: 1615850303565550365035743834433497598022205133485774201606517271376232 7569433945446598600705761456731844358980460949009747059779201853611806 5240326602643873754488504582407212621410911245578943313189882019267825 5414470717051733265761215398173776292712656376833385729394009245096296 1345590112027605299384253953937214738429885638524446346600995950025162 4999951486884216044330907814772018434340288941704971924997723835172044 3738817286297319960301550947126666208958462685731138953761669151043663 0118842634216110085857465973230459013148857022902181498763221831660864 787168460090505124131540553201877819966866103196087758847 ...which makes the crossover point numerator a cycle element: cycle point: 8380618382145296825288792901524180703800135275282676893342146898293334 2149440917457995024433772406383954708358485246874943928753464886028226 8878310351555357453778021428255770844432103620335732612336869212817777 7964917643966677627193148443610359458278220620608180674734866573550370 3328095046884939758331533786933062068890362350792456466825065316026649 0369334317955008431452239714094787392821404098097834271190963786050217 9183612695542205538945966334879363029629456547713892003592919329372461 0242904718947286344375888372556268949831575149884155327332010993071794 310582307131219417929559044245738893676516828810562885 cycle of 3n + 16158503035655503650357438344334975980222051334857742016 06517271376232756943394544659860070576145673184435898046 09490097470597792018536118065240326602643873754488504582 40721262141091124557894331318988201926782554144707170517 33265761215398173776292712656376833385729394009245096296 13455901120276052993842539539372147384298856385244463466 00995950025162499995148688421604433090781477201843434028 89417049719249977238351720443738817286297319960301550947 12666620895846268573113895376166915104366301188426342161 10085857465973230459013148857022902181498763221831660864 787168460090505124131540553201877819966866103196087758847 odds only: 8380618382145296825288792901524180703800135275282676893342146898293334 2149440917457995024433772406383954708358485246874943928753464886028226 8878310351555357453778021428255770844432103620335732612336869212817777 7964917643966677627193148443610359458278220620608180674734866573550370 3328095046884939758331533786933062068890362350792456466825065316026649 0369334317955008431452239714094787392821404098097834271190963786050217 9183612695542205538945966334879363029629456547713892003592919329372461 0242904718947286344375888372556268949831575149884155327332010993071794 310582307131219417929559044245738893676516828810562885 8204960793559931277558051065690350700668027696558111161432718560355563 7979411340994862928895313869754981115527682023751859457827311241349456 0234807668492699134249193233459899669721037782199752555134463134531394 3741827349918166493213974217523036855437455193476051357091069224084736 2277871985841300593296242776490069623182783627884118580007355729866212 2355297449190405348126322669571513982593765769996327139056483632650975 1381840621919732884591944230656521490236755276871403148862239545158901 9747856741864759724452968191740639099991758741759169823726089323200400 85050103505949391192664615167307518323947826841259723751 . <1021 cycle nodes skipped> . 5182552047689339177718568009296008161120157303431049358652733192109505 2384207017835791736444868143847498294579238945530046035435964744324667 3807484332447166103616294434220202022662012322956212358958675376194327 7952560205930674171576784204780079959280379818057389430820999165844954 1023449514664250441892909080567232126219192151966168165818912605732471 5758815065429213741094426373231368715385982217066464220800456666219600 6409740504724372327819929368902089758574221441328970623198876545170379 0552875410062644115808117804588259932035402961353522870537578894050056 653634701638077414596065456471131811427546787402648343211 8380618382145296825288792901524180703800135275282676893342146898293334 2149440917457995024433772406383954708358485246874943928753464886028226 8878310351555357453778021428255770844432103620335732612336869212817777 7964917643966677627193148443610359458278220620608180674734866573550370 3328095046884939758331533786933062068890362350792456466825065316026649 0369334317955008431452239714094787392821404098097834271190963786050217 9183612695542205538945966334879363029629456547713892003592919329372461 0242904718947286344375888372556268949831575149884155327332010993071794 310582307131219417929559044245738893676516828810562885 cycle length: 1024

Also, that 1024 represents just the odd numbers. If we want a cycle length of 1000 that counts odds and evens, we can create a Sequence Vector whose length + sum = 1000. We could set the length to, say, 300. Now, a Sequence Vector cannot have a 0 as a member, so we have to start with 300 1's: [1,1,1,...1,1,1]. That represents 600 iterations (300 odds each followed by 1 even.) To bring the total iteration count up to 1000, we can randomly distribute the 400 remaining evens amongst the 300 positions in the Sequence Vector:

sv: [2, 3, 1, 5, 1, 2, 4, 1, 4, 2, 1, 1, 4, 1, 1, 5, 3, 2, 4, 2, 2, 2, 2, 4, 2, 1, 2, 3, 3, 4, 2, 3, 2, 3, 1, 2, 3, 1, 1, 3, 6, 2, 4, 3, 2, 5, 3, 1, 1, 4, 2, 2, 1, 1, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 3, 3, 1, 2, 3, 2, 3, 1, 1, 2, 3, 3, 2, 3, 6, 2, 4, 3, 1, 1, 4, 5, 4, 3, 2, 3, 3, 2, 3, 1, 3, 4, 2, 3, 2, 2, 2, 1, 1, 3, 1, 3, 4, 2, 1, 2, 2, 4, 2, 2, 2, 2, 2, 3, 3, 3, 2, 3, 2, 1, 2, 1, 3, 2, 4, 2, 2, 1, 1, 1, 3, 1, 2, 3, 1, 3, 2, 2, 1, 3, 3, 1, 1, 2, 1, 2, 3, 4, 2, 1, 2, 3, 1, 2, 2, 5, 2, 4, 3, 2, 2, 3, 4, 2, 7, 3, 4, 1, 1, 1, 2, 3, 1, 4, 3, 2, 2, 1, 1, 1, 2, 1, 2, 1, 3, 2, 3, 4, 1, 4, 4, 2, 1, 5, 2, 3, 3, 2, 3, 2, 3, 1, 1, 3, 1, 1, 5, 3, 2, 1, 2, 1, 2, 3, 2, 2, 4, 3, 2, 4, 3, 2, 2, 2, 3, 2, 2, 4, 1, 2, 1, 2, 2, 1, 3, 1, 1, 4, 2, 3, 3, 2, 5, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 2, 4, 1, 3, 3, 3, 4, 2, 1, 3, 3, 2, 3, 4, 2, 3, 1, 3, 4, 2, 3, 1, 2, 2, 2, 2, 2, 2, 2, 1, 3, 3, 3, 2, 2, 3, 2, 5, 1, 1, 3] length sv: 300 sum sv: 700

Then proceed as before.

First - calculate Hailstone Function Parameters X, Y, Z X: 5260135901548373507240989882880128665550339802823173859498280903068 7321542970808221136665362775884512269829688561782177130194322501838 0386312781477065188084995522367112844459819166375788432271727129325 1735781376 Y: 1368914790585883759913260273820883159664636956253374364714801900783 6899717749907659380020615568894138825048444059799404281351273276569 5774566001 Z: 3475465209973734224893511750601637954807886445225111002484926063408 7080429355201811263189970713606631762237136529395611535266500813907 7421459203106933406364346195272179114593892633963652197574357461364 1114151103 Second - determine the rational number that is the Crossover Point CP.numerator : 34754652099737342248935117506016379548078864452251110024849260 63408708042935520181126318997071360663176223713652939561153526 65008139077421459203106933406364346195272179114593892633963652 1975743574613641114151103 CP.denominator: 52601359015483735072409898828801286655503398028231738594982809 03068595262818022233737675210250206362911016505160552880276547 95206010543486595031569405808064379953472974019411375106576384 1509204538527555961215375 Third - pick C to cancel the denominator C: 52601359015483735072409898828801286655503398028231738594982809 03068595262818022233737675210250206362911016505160552880276547 95206010543486595031569405808064379953472974019411375106576384 1509204538527555961215375 211 digits Fourth - test TEST: 3n + 5260135901548373507240989882880128665550339802823173859498280903068 59526281802223373767521025020636291101650516055288027654795206010543 48659503156940580806437995347297401941137510657638415092045385275559 61215375 attractor (smallest value in loop cycle): 83340916167962167455223215390221094185977558350495531958985252214113 25489538821814042037327289608274957108840242041144680259905841446366 17708488469804433416140353913753058550483999198139222579555573830379 84067 evens in loop cycle: 700 odds in loop cycle: 300 Note: by Sequence Vector Theory,ALLpossible patterns appear infinitely many times on the Collatz Graph, so there's no danger this won't work.

That's a bit better, C is 211 digits as opposed to the 617 digits for the 2-adic Sequence Vector. Still, the numbers are a tad large, aren't they? And that's only a cycle length 1000. What if we wanted a million? Or 10 million? In theory, the calculation would work. In practice, the computer starts to balk, taking forever only to crash over some silly issue such as not enough memory.

How about a smarter brain?

One that can find big cycles without getting hot? Not to mention the somewhat unsatisfying result of the C/(cycle length) ratio being so large in the constructed example. Are there any large cycles with relatively small C?

Sure. We just have to find them.

We could, of course, just run a bunch of sequences with various values of C and look for record setters. But there are better ways.

For one thing, there is a correlation between cycles and divisors of C and that fewer cycles often mean bigger cycles. So, choosing C to be prime is often a good bet as primes always have fewer divisors than composites. Although the relationship isn't as nice as one would expect. For the divisor C,

**Every** multiple of C is on a single graph component whose root cycle is 4C-2C-C-4C.

In fact, primes with **exactly** two cycles are considered "special" as that doesn't happen very often.

And some brute force testing with prime C showed that seed=1 was often a good choice as 1 must always be part of or lead to a non-trivial cycle.

As a result of such testing, a cycle was found

3n + 1271069 seed = 1 attractor = 97 cycle length = 115819 odd numbersWhich is pretty impressive. The Sequnce Vector has 115,819 nodes! And that's just the odd numbers. Calculating the X,Y,Z parameters as above gives you numbers in the order of 50,000+ digits! And one of the Crossover Points reduces down to 97. And keep in mind there is a Crossover Point for

But, as it turns out, this is hardly the **Ultimate Cycle**.

Because it doesn't take into account yet another idiosynchrocy of Collatz. There is another
group of special primes: those that are powers of two minus three. Here, the seed 1 is **always**
the attractor of a cycle that is **always** length 1. Specifically, for 2**n-3, the cycle of
seed=1 is always Sequence Vector [n] which can **never** be a record setting cycle.

But hold on, son. There's no law that says cycle [n] is the **only** cycle. Some of its
sibling cycles could be (and **are**) a lot bigger. And, of course, testing by always
using seed=1 will miss them.

How many candidates for **Ultimate Cycle** does this give us? Remember, we still want to
use primes to get large cycles. So a quick look reveals:

2**n-3 prime 2**n-3 composite 3 5 4 13 5 29 6 61 7 125 8 253 9 509 10 1021 11 2045 12 4093 13 8189 14 16381 15 32765 16 65533 17 131069 18 262141 19 524285 20 1048573 21 2097149 22 4194301 23 8388605 24 16777213 25 33554429 26 67108861 27 134217725 28 268435453** 29 536870909** 30 1073741821 31 2147483645 32 4294967293 33 8589934589 34 17179869181 35 34359738365 36 68719476733 37 137438953469 38 274877906941 39 549755813885 40 1099511627773 41 2199023255549 42 4398046511101 43 8796093022205 44 17592186044413 45 35184372088829 46 70368744177661 47 140737488355325 48 281474976710653 49 562949953421309 50 1125899906842621 51 2251799813685245 52 4503599627370493 53 9007199254740989 54 18014398509481981 55 36028797018963965 56 72057594037927933 57 144115188075855869 58 288230376151711741 59 576460752303423485 60 1152921504606846973 61 2305843009213693949 62 4611686018427387901 63 9223372036854775805 64 18446744073709551613 65 36893488147419103229 66 73786976294838206461 67 147573952589676412925 68 295147905179352825853 69 590295810358705651709 70 1180591620717411303421 71 2361183241434822606845 72 4722366482869645213693 73 9444732965739290427389 74 18889465931478580854781 75 37778931862957161709565 76 75557863725914323419133 77 151115727451828646838269 78 302231454903657293676541 79 604462909807314587353085 80 1208925819614629174706173 81 2417851639229258349412349 82 4835703278458516698824701 83 9671406556917033397649405 84 19342813113834066795298813 85 38685626227668133590597629 86 77371252455336267181195261 87 154742504910672534362390525 88 309485009821345068724781053 89 618970019642690137449562109 90 1237940039285380274899124221 91 2475880078570760549798248445 92 4951760157141521099596496893 93 9903520314283042199192993789 94 19807040628566084398385987581 95 39614081257132168796771975165 96 79228162514264337593543950333 97 158456325028528675187087900669 98 316912650057057350374175801341 ** - intractable2**29-3 would be a nice place to look as the next prime is 2**94-3.

And even C runs slow in that range. Python is probably out of the question and wouldn't solve the memory problem anyway.

But wait! How about Seed? The author of that language is looking for some nifty examples. What better example than solving the
Seed7, actually. Not to be confused with **seed**, the term used for the initiator
of a Collatz Sequence.

Seed7 Homepage: http://seed7.sourceforge.net Seed7 - The extensible programming language: User defined statements and operators, abstract data types, templates without special syntax, OO with interfaces and multiple dispatch, statically typed, interpreted or compiled, portable, runs under linux/unix/windows.

Wrong question because power alone isn't enough. I've already got a Ferrari, my attractor locator. Alas, it runs out of gas before it can complete a single lap of 3n+(2**29-3). Now, if I could drive without needing gas, I could complete the lap albeit not at 200 mph.

Enter Floyd, Brent and Sedgewick and their cycle detection algorithms.

http://en.wikipedia.org/wiki/Cycle_detection

Well, Sedgewick does. But he uses a fixed amount, so we won't crash the system (you wish).

Brent is an improved version of Floyd, so we don't need both. The trade-off is memory for cpu time. But we need the lap to be completed in our lifetime, so it would behoove us to check out Sedgewick also as long as the fixed amount he requires fits in memory.

Brent's algorithm is the Python code I copied from Wikipedia and subsequently translated to Seed7. I had to look elsewhere for Sedgewick's algorithm and found a C implementation here:

http://www.cs.umbc.edu/~hosu/algorithm/tr.html

Alas, Mr. Su's program is buggy, but you get what you pay for. He has no checking of array bounds and subsequently gets segment faults. Nor does he check for overflow (and Collatz simply can't live in a space limited to 64 bits).

Seed7 will at least throw an exception rather than cause a segment fault. And some runtime checks can minimize the occurence of such faults by doing smarter memory management which is wanting in the original C program. And with unlimited precision integers, overflow errors simply don't exist.

With Seed7's bigIntegers and my fixing up the algorithm, we've got a lean, mean, fightin' machine.

The Seed7 programs:

Brent's algorithm:A quick look at Brent's alogrithm with C = 2**22-3:ecd010.sd7* Sedgewick's algorithm:scd002.sd7* * - These links have been disabled as they are no longer compatible with the current version of Seed7. See "The Quest Continues..." addendum for an updated Seed7 version of Brent's Algorithm.

usage: ecd010 N E C O N - start of seed range (must be odd) E - end of seed range C - C of the 3n+C Collatz function O - options none as of this version (enter 0) There are four numbers on each output line, each line representing a distinct cycle. - the attractor (smallest number in the cycle) - the seed (that lead to this cycle, may or may not be part of the cycle) - the GCD (of adjacent odd nodes in the cycle. will always be a divisor of C) - the cycle length (counting just the odd nodes) $ ./ecd010 1 400 4194301 0 4194301 4194301 4194301 1 1 1 1 1 2629 3 1 3812 2083 5 1 3812 2959 7 1 3816 7175 11 1 3811 13 13 1 3818 5617 19 1 3813 277 23 1 3811 3299 25 1 3816 787 29 1 3809 4123 31 1 3812 23225 35 1 3817 1177 37 1 3816 1535 41 1 3811 745 43 1 3814 2129 47 1 3808 149 49 1 3819 13805 53 1 3812 4021 55 1 3815 59 59 1 3806 905 61 1 3824 2357 65 1 3813 371 67 1 3812 1207 71 1 3812 3245 77 1 3814 7039 89 1 3811 3089 95 1 3811 3367 97 1 3814 10991 101 1 3817 445 113 1 3814 7939 115 1 3811 449 121 1 3813 971 125 1 3807 1319 137 1 3814 941 145 1 3818 3107 155 1 3808 317 157 1 3815 3053 161 1 3811 9283 167 1 3808 593 169 1 3813 4307 181 1 3819 2039 185 1 3817 1447 193 1 3811 8051 205 1 3804 11459 209 1 3814 3853 215 1 3811 5635 217 1 3813 4783 223 1 3812 1237 233 1 3812 4787 247 1 3809 11047 293 1 3810 2675 347 1 3820Works great and runs quick, but hardly record setters. Let's try the next prime on the list.

$ ./ecd010 1 400 16777213 0 16777213 16777213 16777213 1 1 1 1 1 143 3 1 254252 29 5 1 254241 119 7 1 254214Wow! Three cycles

$ ./scd002 1 400 16777213 0 10000000 409600 999999 16777213 16777213 16777213 1 1 1 1 1 143 3 1 254252 29 5 1 254241 119 7 1 254214We got the same answer at least. That's a good sign.

But it took 168 seconds!

**Did I do all that work on Sedgewick's algorithm for nothing?!**

No. Note the extra parameters required by the scd002 program. These are table size, scan parameter and iteration limit. By adjusting these parameters, we can tune the Sedgewick algorithm for optimum performance (with a little trial and error).

Using ./scd002 1 400 16777213 0 130000 49999 999999, the time reduced to 77 sec, so
ideally, Sedgewick can halve the time required by Brent.*

(* - Nevertheless, because of memory usage and tuning requirements, I have **NOT**
updated scd002.sd7 to work with the current version of Seed7.)

Now, using the (hopefully) optimized Sedgewick algorithm, a cycle of 2**29-3
in...(drum roll)...50 seconds! That's effectively just one seed. Sometimes we need
to test seeds > C to find **all** the cycles, and at 50 sec a pop with C=536870909,
I'll settle for just one.

$ ./scd002 1 4 536870909 0 9500000 3999999 99999999 536870909 536870909 536870909 1 1 1 1 1 167 3 1 19883729

As I mentioned earlier, this is 2**29-3 and the next prime is 2**94-3. If the run-time
scales up proportionally, the cyle of 2**94-3 might take someting like a couple trillion
years to find. But I thought: why not try it, it **might** have many cycles like
16777213 does and be small enough to be tractable yet still a new record.

I figured Sedgewick is comepletly out of the question as the finite table size won't fit in memory, so I'll have to try it with Brent's algorithm. And just to shave every last micro-second off the run time, I did this directly in C.

And it started off

$ ./bcd000 1 4 19807040628566084398835987581 0 1 1 1 23091222

**There must be something horribly wrong.**

After all, the algorithm worked fine for 16777213 and 536870909 . Aha, there **was**
a bug, but not in the algorithm. Seems in the course of converting the command line
parameter for C to an mpz (GMP unlimited precision integer), I had foolishly first
converted the string to a long integer and then the long integer to the mpz. The correct
way to do this was to convert the string directly to the mpz. This fixed the problem and
as I feared, 19807040628566084398835987581 proved intractable (at least it had nothing
to show after a 10 hour run).

That satisfied my curiosity, but what exactly **was** I seeing when it was broken?

Well, if you convert the string "19807040628566084398835987581" to a long integer, you
get a bit of an overflow and the result is 2147483647. And what happens if I use 2147483647
as C? It's not 2**n-3, so the attractor of seed 1 doesn't have to be length 1. It **is**,
in fact:

$ ./bcd001 1 40 2147483647 0 1 1 1 23091222 191 5 1 23091222 371 13 1 23091222Which is greater than

Dag nab it, that record didn't last long. All that mucking about with powers of two minus three, only to be trumped by the occurence of a lucky freak accident.

Well, luck favors the prepared mind, so I'll just quietly claim the **The Ultimate Cycle**
is

3n + 2147483647 seed = 1 attractor = 1 cycle length = 23091222 odd numbersand act all smug about how clever I am.

Well, not quite. None of this moves us any closer to proving or disproving the conjecture.

But I'll settle for **3n+2,147,483,647** with its cycle of **23,091,222** odd numbers as
the **Ultimate Cycle**.

For now.

1-Apr-2010

1-Dec-2009

The trouble with powers of 2 minus 3 is that there are no primes between 2^{29}-3 and
2^{94}-3. But we don't have to use a prime C, some composites have long loop cycles.
I noticed that with a C consiting of two 3-digit factors, I get loop cycles ranging from length 6
to over length 100. So I came up with a scheme to generate composite C's with long loop cycles.

This may not be the best (a pair of 3-digit factors only had a cycle of length 88), but it's
very consistent. The cycle length increases by a factor of 4-5 for every one digit increase in
factor size. At that rate, 12-digit factors were up to cycle length of over 20 million, putting me
on the verge of a new **Ultimate Cycle**.

But, my C program chose that moment to choke again. There must be another place where it's getting hung up on 32-bit longs. Numerous attenpts to convert everything to unlimited prcision integers failed to resolve the problem. And it doesn't outright fail, it just doesn't halt and that can take hours.

So I'll use that Seed7 program, it's also compiled and only slightly slower than pure C. And after all the trouble I took to implement a Seed7 version, it too let me down,

c:\ >ecd010 1000000007 1000000009 40000003700000063 0 c:\ >*** Uncaught EXCEPTION_RANGE raisedbecause I'm always pushing the envelope, constantly trying to solve ever bigger problems and subsequently hitting the limitations of language designs. For instance, once I got a 64-bit processor I assumed gmpy would no longer give me "outragous exponent" if my exponentials had an exponent of more than 32 bits. Which works, but then you encounter another limit in how many digits the resulting number can have.

And the Seed7 version I was using turned out to be unable to handle the "set of bigInteger" if the bigIntegers in question were bigger than allowed by a set. This required an update to Seed7. Also, some variables in ecd010.sd7 needed to be cast as bigInteger. Mr. Mertes (Seed7 author) claims this fixes everything so the above now works.

corrected ecd010.sd7

Alas, I stayed one jump ahead of him. While he was fixing Seed7, I was upgrading my laptop to a Mac Airbook with a 64-bit processor. Now we're in a bind over 64-bit compatability issues. We almost have it working. I can get ecd010.sd7 to run in the interpreter (albeit slowly) and verify Mr. Mertes has a valid solution to the above problem.

The compiler is still having a problem but it will have to wait because Mr. Mertes doesn't have a Mac and he's relying on me to test proposed changes. There is almost nothing worse than trying to debug a C program by e-mail.

So, it's back to Python where it all began. First, to prove the halting problem (actually the
lack of which) is actually a bug in the C program. And then try to optimize it with gmpy to get
some decent performance. I'm so near a new **Ultimate Cycle** I can almost reach out and touch
it (only to be frustrated by C being too low level).

But now I've got a bigger advange than before. Python has been upgraded to version 3.1 and I just downloaded a new release of gmpy that looks to cut run-time by up to a third.

And not only did the new gmpy release come through with a much improved run-time, it easliy sailed past the 32-bit bottleneck. That proves the C program is buggy.

But more importantly, there is no more restraint on cycle length!

i: 15 f1: 1000000000000037 f2: 4000000000000021 C: 4000000000000169000000000000777 loop @: 50797194815244528496208163978013 found in: 31842.499 sec len(sv) 7929771085 determined in: 7441.559 secWow. A cycle length of 7.9 BILLION (short scale). And that's just the odd numbers! There ought to be about twice as many evens. And it took less than a day to calculate.

**BUT WAIT...**when I did the Python run, I used different parameters than I had tried with
ecd010.sd7. Turns out I should have stuck with the ones that crashed as once Mr. Mertes got Seed7
working with my test numbers, **HIS** result (confirmed with my 64-bit interpreter run) had
a cycle of **11,165,673,618. That's over 11 BILLION.** It took Mr. Mertes (on a Linux machine, presumably)
4-5 hours to compute. Until we get the compiler working, I'm limited to using the interpreter, which
arrived at the identicle result in 48-55 hours (I don't think I'll be using the
Seed7 interpreter to find any new records).

Still, it's mind boggling to think that after over 33 billion iterations of 3n+40000003700000063, the number 10880083 will return to 10880083.

Back to