The Quest for the Ultimate Cycle


Updates
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
            |
            O

become 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
                                |
                                O

which becomes our Sequence Vector [1,2,3,4]. Every Sequence Vector has an associated Hailstone Function:

          X*a - Z
      g = -------
             Y

We 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 Crossover Point where g = a. That point is:
                       Z
    Crossover Point = ---
                      X-Y

That 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-Y

Which 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, ALL possible 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 numbers
Which 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 each of the 115,819 cyclic permutations of the Sequence Vector, each of which is an integer. This is because each Crossover Point represents one of the odd numbers that comprise the cycle and the cyclic permutaions are as if you entered the cycle at a different point.

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
** - intractable
2**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 Ultimate Cycle?

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: 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. 

A quick look at Brent's alogrithm with C = 2**22-3:
 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       3820
Works 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       254214

Wow! Three cycles each more than twice the size of my previous record. But it took 143 seconds to find them. Let's try Sedgewick.

$ ./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       254214
We 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.)

The Ultimate Cycle

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
Holy Mother of Pearl! A cycle of length 19,883,729! An astounding new record!

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
Whoa!! That's impossible! The cycle whose attractor is 1 has to be length 1. And the cycle will be [94]. I don't need a test to show this, it's straight mathematics.

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       23091222
Which is greater than The Ultimate Cycle!!!

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 numbers
and 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.


The Quest continues. . .


Updates
1-Apr-2010
1-Dec-2009

The trouble with powers of 2 minus 3 is that there are no primes between 229-3 and 294-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 raised
because 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. IF you use THIS version with the latest Seed7 release.

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 sec 
Wow. 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 The Mensanator