Collatz-Intro - The General loop |
Workshop |
|
|
A "general" loop is a distinguishing from special forms of loops, where no a-priori restriction is made to the exponents. So it may be written as a' = T(a;A,B,C,D,...G,H) with N exponents (=steps) and a'=a Since the exponents are arbitrarily mixed, ascending and descending steps may follow in arbitrary sequence, and the only things, that are known a priori is the length N and that the sum of all exponents 1 must roughly agree with the sum of all exponents >1, since the former are ascending steps and the latter descending. This can be estimated from the following form: L = number of 1's Ascending factor u ~ (3/2)^L M = number of exponents > 1 = N - L S = sum of all exponents ; S-L = sum of descending exponents descending factor d ~ 3^M / 2^S ascending factor * descending factor = 1 // required to satisfy a ~ a * u * d u * d ~ 1 3^L/2^L ~ 3^(N-L)/2^(S-L) 2^S ~ 3^N S ~ N*log(3)/log(2) ~ N * 1.59 In contrast to a general loop is the so called "primitive" loop, which is defined that after N-1 ascending steps one single descending step follows: a' = T(a;1,1,1,1...,1,A) with N-1 1's and a'=a Then A must be roughly 2^A ~ (2/3)^(N-1) or A ~ (N-1) (log(3)/log(2)
-1) and also be integer, by definition. This type of loop is easier accessible, and remarkable results were reached, especially the existence of such a loop of *any* length could be disproven with one proof. This is a qualitative difference to the problem of the general loop, where only disproofs are reached for a specified length or a interval of lengthes of the form "from length 1 up to length x". (currently ~ 250000, see [Rosendaal]) |
|
The most simple case: is there another 1-step-loop? A 1-step-loop means, whether after only one transformation the same number occurs as output, which was given as input. One known exemplar is 1; in the original Collatz-transformation the loop is 1 -> 4 -> 2 -> 1, and this loop is usually called the "trivial loop". In my notation this is only one step, namely 1 = T(1;2) But also: 1 = T(1;2,2) = T(1;2,2,2...) which rhs-transformations indicates, that this 1-step-loop (as any) can concatenated infinitely many times. Now I show, how to disprove, the possibility of another loop of the same length, by first finding out that this is one solution for a = T(a;A) and then showing, that there are no others. This example may be found too simple, but I use it to introduce my general line of arguing, which is only a schematic extension from this most simple case. |
|
Assume general 1-step-transformation a' = T(a;A) where a' = a or a' which makes it a loop, where se seek, whether there exists any exponent of A, which allows a to be an odd integer>1 or controversely, whether exist any a, which allows the exponent A be integer. The transformation-formula expanded says: 3*a + 1 Now, if a'/a = 1 we have: 3*a + 1 1 or 3*a + 1 which is 1 Now the qestion was: is there any A, that allows an integer solution for a, or conversely: is there any a which allows an integer exponent A? We see, that if a = 1 then the rhs is 4, so indeed we have a solution for A namely A=2 1 This result means, we have a loop with a = T(a;A) with a=1 and A=2 ---> 1 = T(1;2) Now we look, whether there could be another solution: this is not possible, since if we increase a, then the rhs would decrease, but cannot decrease below 3. But between 3 and 4 are no more powers of 2. We see, that the range of the rhs for any choice of a is 3<=rhs<=4 But since the lhs must be an integer power of 2 , this can be expanded to 3<=2^A = rhs<=4 The function powerceil2(x) denotes the smallest power of 2 equal or greater than x so powerceil2(3)<= 2^A = rhs <=4 This will be a standard notation for the critical-loop-criteria from now. From this we know, there can only be one solution, since for the critical inequality powerceil2(3) = 4 <= 2^A = rhs <=4 there can only be one solution for A, namely 2. Conversely, from that we can uniquely determine a 2^2 = 3+ 1/a ---> a = 1/(4-3) = 1 |
|
Now we extend this to the question, whether a 2-step-loop exists: We write both transformations with their two members a,b a -> b -> a -> b -> a .... a' = T(a;A) where b=a' and b'=T(b;B), where a = b' Then we state the trivial product
3a +1 3b +1 a * b = a' * b' = ----- * ----- 2^A 2^B and reorder like in the previous example: 3a + 1 3b + 1 2^(A+B) = ----- * ------ b a Rotating the denominator, and cancelling, this can be expressed as
1 1 and exibits a pretty simple exact extension of the one-step-condition before. For the smallest possible a,b (a=b=1) the rhs calculates to 4^2, and even if a and b grow to infinity, the rhs will always be greater or equal 3^2. So we have again the form of the critical inequality, only with the exponent N=2 and two parentheses: 1 1 powerceil2(3^2) <= 2^(A+B) =(3 + --)(3 + --) <= 4^2 a b Now we can insert on the lhs: 1 1 powerceil2(3^2) = 16 <= 2^(A+B) =(3 + --)(3 + --) <= 16 a b that means, we can have only the solution, where A+B=4 . Since the parentheses need their maximum 4 to form their product 16, a and b both must take their minimum, which is 1. So we have a solution for the 2-step-loop with a = T(a;A,B) --> a=1, A=B=2 and 1 = T(1;2,2) and this is the only solution. |
|
For more steps in the loop, the formula is simply extensible. The critical inequality for the general case with N=number of steps, S = sum of exponents we have: [Eq 2.1] "critical
inequality" for loops: powerceil2(3^N) <=
2^S = (3+1/a)(3+1/b)(3+1/c)...(3+1/h) <= 4^N This formula has the nice properties: one can either simply put candidates for a,b,c into the product, and see, whether a power of 2 occurs - or conversely one could search this way...(but that would result in too many combinatorical possibilities). Unfortunately weaken the bounds, that this inequality states, with growing N: there are multiple possibilities for the sum of exponents S to fit between powerceil2(3^N) and 4^N, so it is *generally* not yet sufficient. But still there are some lengthes of loops, which can be denied by this formula. The reason for this is, that there is another requirement on all members a,b,c... of a projected loop: they must all be different (otherwise the loop would already be shorter). Since they all · should be greater than 1, · should be odd, and · cannot be divisible by 3, the theoretically lowest values can be: a=5,b=7,c=11,... and this allows to disprove several loops up to the length of 100 to 200 as it is shown in the following table. |
Remarks to the approximation-approach
|
The following table lists results for the tests for general loops for lengthes up to 200 other than the trivial loop. N:= looplength ug:= powerceil2(3)/3^N prod:= (3+1/a)(3+1/b).../3^N ratio:= ug/prod must be <=1 to make this loop possible by satisfying the critical equation n
ug prod ug/prod ug > prod: ------------------------------------------------------------ 1 1.333333 1.066667 1.250000 -true- 2 1.777778 1.117460 1.590909 -true- 3 1.185185 1.151323 1.029412 -true- 4 1.580247 1.180844 1.338235 -true- 5 1.053498 1.203998 0.875000 6 1.404664 1.225120 1.146552 -true- 7 1.872885 1.242876 1.506897 -true- 8 1.248590 1.259447 0.991379 9 1.664787 1.273924 1.306818 -true- 10 1.109858 1.287622 0.861944 11 1.479811 1.299885 1.138416 -true- 12 1.973081 1.311596 1.504336 -true- 13 1.315387 1.322259 0.994803 14 1.753850 1.332509 1.316201 -true- 15 1.169233 1.341960 0.871288 16 1.558977 1.351089 1.153868 -true- 17 1.039318 1.359586 0.764437 18 1.385758 1.367826 1.013110 -true- 19 1.847677 1.375554 1.343224 -true- 20 1.231785 1.383070 0.890616 21 1.642379 1.390163 1.181429 -true- 22 1.094920 1.397079 0.783720 23 1.459893 1.403638 1.040078 -true- 24 1.946524 1.410048 1.380467 -true- 25 1.297683 1.416152 0.916344 26 1.730243 1.422127 1.216659 -true- 27 1.153496 1.427838 0.807861 28 1.537994 1.433438 1.072941 -true- 29 1.025329 1.438807 0.712625 30 1.367106 1.444077 0.946699 31 1.822808 1.449144 1.257852 -true- 32 1.215205 1.454124 0.835696 33 1.620274 1.458923 1.110596 -true- 34 1.080182 1.463644 0.738009 35 1.440243 1.468204 0.980956 36 1.920324 1.472694 1.303954 -true- 37 1.280216 1.477038 0.866746 38 1.706955 1.481319 1.152321 -true- 39 1.137970 1.485469 0.766068 40 1.517293 1.489561 1.018618 -true- 41 1.011529 1.493533 0.677273 42 1.348705 1.497453 0.900666 43 1.798274 1.501263 1.197840 -true- 44 1.198849 1.505026 0.796564 45 1.598465 1.508688 1.059507 -true- 46 1.065644 1.512306 0.704648 47 1.420858 1.515831 0.937346 48 1.894477 1.519316 1.246928 -true- 49 1.262985 1.522714 0.829430 50 1.683980 1.526076 1.103471 -true- 51 1.122653 1.529358 0.734068 52 1.496871 1.532605 0.976684 53 1.995828 1.535778 1.299555 -true- 54 1.330552 1.538919 0.864602 55 1.774069 1.541990 1.150506 -true- 56 1.182713 1.545032 0.765494 57 1.576951 1.548009 1.018696 -true- 58 1.051300 1.550957 0.677840 59 1.401734 1.553845 0.902106 60 1.868978 1.556707 1.200598 -true- 61 1.245986 1.559512 0.798959 62 1.661314 1.562292 1.063383 -true- 63 1.107543 1.565018 0.707687 64 1.476724 1.567721 0.941956 65 1.968965 1.570374 1.253819 -true- 66 1.312643 1.573004 0.834482 67 1.750191 1.575587 1.110818 -true- 68 1.166794 1.578149 0.739343 69 1.555725 1.580666 0.984221 70 1.037150 1.583163 0.655113 71 1.382867 1.585618 0.872131 72 1.843823 1.588053 1.161058 -true- 73 1.229215 1.590449 0.772873 74 1.638954 1.592826 1.028960 -true- 75 1.092636 1.595165 0.684967 76 1.456848 1.597487 0.911962 77 1.942463 1.599772 1.214212 -true- 78 1.294976 1.602041 0.808328 79 1.726634 1.604276 1.076270 -true- 80 1.151089 1.606495 0.716522 81 1.534786 1.608680 0.954065 82 1.023191 1.610851 0.635186 83 1.364254 1.612991 0.845792 84 1.819006 1.615116 1.126238 -true- 85 1.212670 1.617211 0.749853 86 1.616894 1.619292 0.998519 87 1.077929 1.621344 0.664837 88 1.437239 1.623384 0.885335 89 1.916319 1.625395 1.178986 -true- 90 1.277546 1.627395 0.785025 91 1.703394 1.629367 1.045433 -true- 92 1.135596 1.631328 0.696118 93 1.514128 1.633263 0.927057 94 1.009419 1.635187 0.617311 95 1.345892 1.637086 0.822126 96 1.794522 1.638974 1.094906 -true- 97 1.196348 1.640839 0.729108 98 1.595131 1.642693 0.971046 99 1.063421 1.644524 0.646643 100 1.417894 1.646345 0.861237 101 1.890526 1.648145 1.147063 -true- 102 1.260350 1.649934 0.763879 103 1.680467 1.651703 1.017415 -true- 104 1.120311 1.653462 0.677555 105 1.493749 1.655200 0.902458 106 1.991665 1.656930 1.202021 -true- 107 1.327777 1.658640 0.800521 108 1.770369 1.660341 1.066268 -true- 109 1.180246 1.662023 0.710126 110 1.573661 1.663697 0.945882 111 1.049107 1.665352 0.629961 112 1.398810 1.667000 0.839118 113 1.865080 1.668629 1.117732 -true- 114 1.243387 1.670251 0.744431 115 1.657849 1.671855 0.991622 116 1.105233 1.673452 0.660451 117 1.473643 1.675032 0.879770 118 1.964858 1.676605 1.171927 -true- 119 1.309905 1.678162 0.780560 120 1.746540 1.679711 1.039786 -true- 121 1.164360 1.681245 0.692558 122 1.552480 1.682772 0.922573 123 1.034987 1.684284 0.614497 124 1.379982 1.685789 0.818597 125 1.839977 1.687280 1.090499 -true- 126 1.226651 1.688764 0.726360 127 1.635535 1.690234 0.967638 128 1.090356 1.691697 0.644534 129 1.453809 1.693147 0.858643 130 1.938412 1.694590 1.143882 -true- 131 1.292274 1.696020 0.761945 132 1.723032 1.697444 1.015075 -true- 133 1.148688 1.698855 0.676154 134 1.531584 1.700260 0.900794 135 1.021056 1.701653 0.600038 136 1.361408 1.703040 0.799399 137 1.815211 1.704414 1.065006 -true- 138 1.210141 1.705783 0.709434 139 1.613521 1.707140 0.945160 140 1.075681 1.708492 0.629608 141 1.434241 1.709832 0.838820 142 1.912321 1.711167 1.117554 -true- 143 1.274881 1.712490 0.744460 144 1.699841 1.713808 0.991850 145 1.133227 1.715116 0.660729 146 1.510970 1.716418 0.880304 147 1.007313 1.717709 0.586428 148 1.343084 1.718996 0.781319 149 1.790779 1.720272 1.040986 -true- 150 1.193853 1.721544 0.693478 151 1.591804 1.722805 0.923960 152 1.061202 1.724062 0.615525 153 1.414937 1.725308 0.820107 154 1.886582 1.726550 1.092689 -true- 155 1.257721 1.727783 0.727940 156 1.676962 1.729011 0.969897 157 1.117975 1.730229 0.646143 158 1.490633 1.731443 0.860919 159 1.987510 1.732648 1.147094 -true- 160 1.325007 1.733849 0.764200 161 1.766676 1.735041 1.018233 -true- 162 1.177784 1.736228 0.678358 163 1.570379 1.737407 0.903863 164 1.046919 1.738582 0.602168 165 1.395892 1.739748 0.802353 166 1.861189 1.740910 1.069090 -true- 167 1.240793 1.742063 0.712255 168 1.654391 1.743213 0.949047 169 1.102927 1.744355 0.632284 170 1.470569 1.745493 0.842495 171 1.960759 1.746623 1.122600 -true- 172 1.307173 1.747749 0.747918 173 1.742897 1.748867 0.996586 174 1.161931 1.749982 0.663968 175 1.549242 1.751088 0.884731 176 1.032828 1.752192 0.589449 177 1.377104 1.753288 0.785441 178 1.836138 1.754380 1.046602 -true- 179 1.224092 1.755465 0.697304 180 1.632123 1.756547 0.929166 181 1.088082 1.757621 0.619065 182 1.450776 1.758692 0.824918 183 1.934368 1.759756 1.099225 -true- 184 1.289579 1.760817 0.732375 185 1.719438 1.761870 0.975916 186 1.146292 1.762921 0.650223 187 1.528390 1.763965 0.866451 188 1.018926 1.765005 0.577294 189 1.358569 1.766039 0.769274 190 1.811425 1.767070 1.025100 -true- 191 1.207616 1.768095 0.683004 192 1.610155 1.769116 0.910147 193 1.073437 1.770131 0.606417 194 1.431249 1.771143 0.808093 195 1.908332 1.772149 1.076846 -true- 196 1.272221 1.773152 0.717492 197 1.696295 1.774149 0.956118 198 1.130864 1.775143 0.637055 199 1.507818 1.776130 0.848934 200 1.005212 1.777116 0.565642 |
|
Again it is to say, that already loops smaller than N=250000 (collatz-transformations) are disproven, since all numbers < 2^40 are excluded. If we would start with such a number as smallest entry for a, we could get such a table: |
|
n ug prod
ug/prod ug > prod: ------------------------------------------------------------ 1 1.333333 1.000000 1.333333 -true- 2 1.777778 1.000000 1.777778 -true- 3 1.185185 1.000000 1.185185 -true- 4 1.580247 1.000000 1.580247 -true- 5 1.053498 1.000000 1.053498 -true- 6 1.404664 1.000000 1.404664 -true- 7 1.872885 1.000000 1.872885 -true- 8 1.248590 1.000000 1.248590 -true- 9 1.664787 1.000000 1.664787 -true- 10 1.109858 1.000000 1.109858 -true- 11 1.479811 1.000000 1.479811 -true- 12 1.973081 1.000000 1.973081 -true- 13 1.315387 1.000000 1.315387 -true- 14 1.753850 1.000000 1.753850 -true- 15 1.169233 1.000000 1.169233 -true- 16 1.558977 1.000000 1.558977 -true- 17 1.039318 1.000000 1.039318 -true- 18 1.385758 1.000000 1.385758 -true- 19 1.847677 1.000000 1.847677 -true- 20 1.231785 1.000000 1.231785 -true- ... 10000 1.296833 1.000e+0000 1.296833 -true- 10001 1.729111 1.000e+0000 1.729111 -true- 10002 1.152741 1.000e+0000 1.152741 -true- 10003 1.536987 1.000e+0000 1.536987 -true- 10004 1.024658 1.000e+0000 1.024658 -true- 10005 1.366211 1.000e+0000 1.366211 -true- 10006 1.821615 1.000e+0000 1.821615 -true- 10007 1.214410 1.000e+0000 1.214410 -true- 10008 1.619213 1.000e+0000 1.619213 -true- 10009 1.079475 1.000e+0000 1.079475 -true- 10010 1.439300 1.000e+0000 1.439300 -true- 10011 1.919067 1.000e+0000 1.919067 -true- 10012 1.279378 1.000e+0000 1.279378 -true- 10013 1.705838 1.000e+0000 1.705838 -true- 10014 1.137225 1.000e+0000 1.137225 -true- 10015 1.516300 1.000e+0000 1.516300 -true- 10016 1.010867 1.000e+0000 1.010867 -true- 10017 1.347822 1.000e+0000 1.347822 -true- 10018 1.797096 1.000e+0000 1.797096 -true- 10019 1.198064 1.000e+0000 1.198064 -true- 10020 1.597419 1.000e+0000 1.597419 -true- |
|
This was computed with the multi-precision interpreter Aribas with 1000-digits float-precision; but checks up to lengthes of N>250000 seemed to be too time consuming for this program. The above critical inequality shows, that we have N factors of the form (3 + 1/a) where a is assumed the minimal number. The maximum value for a member x is not known; if we set it to an astronomical optimistic value of a+N*3/2 (considering N in the area of 2^40) then we have powerceil2(3^N)
1 1 I don't have a function for bounds of the lhs depending on N for such high N at hand, but from some empirical calculations I have |
|
N N powerceil2(3)/3^N 1 1 + 3.3333333e-0001 3 1 + 1.8518519e-0001 5 1 + 5.3497942e-0002 17 1 + 3.9318248e-0002 29 1 + 2.5329408e-0002 41 1 + 1.1528852e-0002 94 1 + 9.4188494e-0003 147 1 + 7.3132484e-0003 200 1 + 5.2120395e-0003 253 1 + 3.1152137e-0003 306 1 + 1.0227618e-0003 971 1 + 9.7906399e-0004 1636 1 + 9.3536809e-0004 2301 1 + 8.9167411e-0004 2966 1 + 8.4798202e-0004 3631 1 + 8.0429185e-0004 4296 1 + 7.6060358e-0004 4961 1 + 7.1691722e-0004 5626 1 + 6.7323277e-0004 6291 1 + 6.2955022e-0004 6956 1 + 5.8586958e-0004 7621 1 + 5.4219085e-0004 8286 1 + 4.9851402e-0004 8951 1 + 4.5483910e-0004 9616 1 + 4.1116609e-0004 10281 1 + 3.6749498e-0004 10946 1 + 3.2382578e-0004 11611 1 + 2.8015849e-0004 12276 1 + 2.3649310e-0004 12941 1 + 1.9282962e-0004 13606 1 + 1.4916804e-0004 14271 1 + 1.0550838e-0004 14936 1 + 6.1850612e-0005 15601 1 + 1.8194754e-0005 47468 1 + 1.0929714e-0005 79335 1 + 3.6647274e-0006 190537 1 + 6.4507505e-0008 |
|
and I don't think, that an approximation to that of the rhs side, where "a" was assumed to be minimum 2^40 (and the minimal member of the loop) can be reached when n=250000, but with a much larger N. That means: the given critical formula seems to give much better restrictions than the currently used formulas and suggest, that with the exclusion of numbers a, where 1..a..2^40 the lengthes for excluded general loops are far higher than 250000. |
|
last update: 15.8.2004 |
|
|
|
|