2
$\begingroup$

The following function is very similar to the one involved in Collatz Conjecture $$ f(n) = \begin{cases} 3n-1 & \text {if $n$ is odd} \\ \frac{n}{2} & \text {if $n$ is even} \end{cases} ,$$ but counter-examples (to the well-known statement) do exist, meaning that some values of n are such that for any $k$ : $$f^{k}(n)≠1\;.$$

For instance, $5, 7, 10, 14, 17, 20, 25, 34, 37, 41, 50, 55, 61, 68, 74, 82, 91, 110, 122, 136, 164, 182, 272$ yield cyclical patterns containing no $1$. But all these values allow to build only two different cyclical patterns:

(5 14 7 20 10) then again 5, etc. 
(17 50 25 74 37 110 55 164 82 41 122 61 182 91 272 136 68 34) then 17 etc.

Or for odd steps counter-examples are:

$$5,7$$

$$17,25,37,55,41,61,91$$

Of course, the sequence starting at,for example,$n=243$ wouldn't be considered as really new since it soon leads to one of these two patterns above.

The question: Is there another similar cyclical pattern?

$\endgroup$
  • $\begingroup$ By $f^k(n)$ you mean the $k$-th composition of $f$ with itself ? Like $f^3(n) = f(f(f(n)))$ ? $\endgroup$ – Zubzub Jul 13 '17 at 9:11
  • 1
    $\begingroup$ Yes.you are true. $\endgroup$ – Newuser Jul 13 '17 at 9:14
  • $\begingroup$ @Zubzub ı find counterexample. $95$ is not a counterexample. $\endgroup$ – Newuser Jul 13 '17 at 9:29
  • 2
    $\begingroup$ Does something make you think that other odd base cycle exist ? I could optimize the code even more (parallelize it) if it's worth the shot. But if you just want to "burn a CPU for the beauty of mathematics", I'm giving up here :p (Note I tried n = $2\cdot 10^7$ to $n=10^8$ with max $k=30000$ and found nothing new). $\endgroup$ – Zubzub Jul 13 '17 at 12:39
  • 2
    $\begingroup$ Comments at OEIS A001281 suggest this is an open problem, with the only known orbits being those starting at 1, 5, 17. $\endgroup$ – nickgard Jul 13 '17 at 15:29
2
$\begingroup$

For even examples, you can take $91\cdot 2^m$ for any $m$. For odd examples, take $$\frac{91\cdot 2^m+1}{3}$$ for odd $m$.

Of course this is assuming that $91$ is indeed a correct counter example, I did not check that.

$\endgroup$
  • 1
    $\begingroup$ No idea what you are trying to communicate with that... $\endgroup$ – Dirk Jul 13 '17 at 9:15
  • 1
    $\begingroup$ Dirk, I think the OP is looking for new cyclically repeating sequences of iterates. Your suggested starting points "drop down" to $91$ after a predictable number of iterations, and therefore don't give new cycles (because they then get stuck in the same cycle that you get when you start with $91$). $\endgroup$ – Jyrki Lahtonen Jul 13 '17 at 9:32
  • $\begingroup$ @Jyrki Lahtonen you are correct. $\endgroup$ – Newuser Jul 13 '17 at 9:36
  • $\begingroup$ Well, for example 5 and 7 are in the same cycle, as $f^2(5) = 7$, so this should be made more clear in the question. $\endgroup$ – Dirk Jul 13 '17 at 9:54
  • $\begingroup$ Please look carefully. I wrote all odd sequence. Because, $17,25...91$ at the same sequence too. $\endgroup$ – Newuser Jul 13 '17 at 10:02
0
$\begingroup$

You can find other counter examples: 5, 7, 10, 14, 17, 20, 25, 34, 37, 41, 50, 55, 61, 68, 74, 82, 91, 110, 122, 136, 164, 182, 272 (brute-force search) but maybe I didn't fully understand what you are asking (maybe you are only interested by odd terms in which case I don't bring any new one)?

Indeed for $n=272$ you get the sequence of terms: 272, 136, 68, 34, 17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, etc. where you can see your own $91$ occuring. Actually taking the highest term occuring in your 91-based sequence could have given to you the idea of a higher starting point (since the sequence is cyclycally repeating if I correctly understood your request).

But the fact is that brute-force search doesn't seem to return anything higher than 272.

$\endgroup$
  • $\begingroup$ Ohh, ı only find odd counterexample $\endgroup$ – Newuser Jul 13 '17 at 9:51
  • $\begingroup$ I see you edited your question in order to tell about that; I am not sure what I should do with my answer now; should I delete it? $\endgroup$ – Thomas Baruchel Jul 13 '17 at 9:54
  • $\begingroup$ Oh ı am so sorry.Dear Thomas.No problem.dont delete $\endgroup$ – Newuser Jul 13 '17 at 9:59
  • $\begingroup$ Thank you, for improve my question. @Thomas $\endgroup$ – Newuser Jul 13 '17 at 16:25
0
$\begingroup$

I think an easy example is $93$, one gets the following sequence $278,139,416,208,104,52,26,13,38,19,56,28,14,7,20,10,5,14,7,20,10,5\ldots$

$99$ is also an example, $296,148,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34,17,50,25,74$

As a side remark, if you change $3n-1$ to $3n+1$, then this is a famous conjecture without known counterexamples.

Edit: I wrote a simple program and played with it a little, apparently at least for any $n<100000$, $f^k(n)$ eventually becomes one of your given counter examples...

$\endgroup$
  • $\begingroup$ Dear @Qidi thank you for writig code. I dont know coding.. But I only find the new sequence..Please write code "only new sequence". Thank you so much. $\endgroup$ – Newuser Jul 13 '17 at 11:59
  • $\begingroup$ You should read the comment by Jyrki Lahtonen in another answer; the OP seems to want the starting term to belong to the repeating pattern. $\endgroup$ – Thomas Baruchel Jul 13 '17 at 12:19
  • 1
    $\begingroup$ Yes and as I mentioned I tried up to $n=100000$ and no such examples exist. $\endgroup$ – Qidi Jul 13 '17 at 12:24
  • $\begingroup$ @Qidi...Very good. Now, I know that if there is counterexample ıt must be $ > 100000$ thank so much! $100000$ so big...perfect. $\endgroup$ – Newuser Jul 13 '17 at 13:02
0
$\begingroup$

maybe just use the reverse map:

$$\cases{\{{n+1\over 3},2n\} & \text{if }n\equiv 2 \bmod 6 \\{2n}&otherwise}$$

$\endgroup$
0
$\begingroup$

I have a counterexample of a type that does not use 3n+1 and produces a proper superset of the odd numbers only. It ends in 1 (but since there are no even numbers, the descent uses other odd ones, including 3). The function is:

$f(n) = \begin{cases} n+ \frac {n+1}{2} & \mbox{if } n+1 \equiv 0 \mbox{ (mod } 4) \\ n-\frac{n-1}{4} & \mbox{if } n-1 \equiv 0 \mbox{ (mod } 8) \\ \frac {n-\frac{n+1}{2}}{2} & \mbox{otherwise} \end{cases}$

Compare for sequence $43$, for example, the odd-even and odd-superset sequences:

43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

43, 65, 49, 37, 9, 7, 11, 17, 13, 3, 5, 1

$\endgroup$
0
$\begingroup$

Let's denote one step on odd positive integers $a$ and $b$ as $$ b={3a-1 \over 2^A }$$ where $A$ is then the required value to make $b$ odd.

To make a cycle, of one such odd step, we must have $b=a$ and we can write $$ \begin{array} {} a &={3a-1 \over 2^A } \\ a2^A &= 3a -1 \\ 2^A &= 3 -\frac1a \\ \end{array} $$ and we find immediately that for natural $a$ there is only one solution: $(a,A)=(1,1)$
Now let's look for a two-step-cycle. We make the ansatz $$ b={3a-1 \over 2^A } \quad c={3b -1 \over 2^B} \quad \text{ and } c=a$$ and can rewrite $$ \begin{array} {} b\cdot a &={3a-1 \over 2^A }\cdot {3b-1 \over 2^B } \\ ab2^{A+B} &= (3a -1)(3b-1) \\ 2^{A+B} &= (3 -\frac1a)(3-\frac1b) \\ \end{array} $$ and we find, that the rhs must fall in the interval $[4,9]$ and since the lhs is a perfect power of 2 we need only look at $2^{A+B}=4$ or $2^{A+B}=8$ where from the first equality it is clear, that $A=B=1$ and we have the previous cycle with $(a,b)=(1,1)$. for $2^{A+B}=8$ we have $$ \begin{array} {} 8 &= (3 -\frac1a)(3-\frac1b) \end{array} $$ Now for each parenthese of the rhs guessing the geometric mean $g$ (requiring a coefficient $ a_m$ between $a$ and $b$) we get $$ \begin{array} {} \sqrt 8 &= (3 -\frac1{ a_m}) \\ 3-\sqrt 8 &= \frac1{ a_m} \\ a_m &= {1 \over 3-\sqrt 8 } \approx 5.82\\ \end{array} $$ and because neither $a$ nor $b$ can equal $3$ or $1$ one of them must be smaller and one of them must be greater than $5.82$; so assuming $a$ as minimal we have $a=5$ and then $b=7$. So we have a solution for a two-step-cycle.

We can proceed to test the 3-step cycle and so on. For the 3-step cycle we find easily, that $2^{A+B+C}=16$ is required to avoid the trivial cycle $(a,A)=(1,1)$ and $2^{A+B+C}=2^3=8$. Guessing $a_m$ by the geometric mean we have then $$ \begin{array} {} 16^{1/3} &= (3 -\frac1{ a_m}) \\ 3-16^{1/3} &= \frac1{ a_m} \\ a_m &= {1 \over 3- 16^{1/3} } \approx 2.08\\ \end{array} $$ It is immediately clear that we cannot have a cycle except the trivial one because there is only one odd number below $2.08$ and this is $1$.

For the 4-step-cycle we find the same criterion as for the 2-step cycle and this allows no new solution, because there is no other odd number "free" below $a_m \approx 5.82$

Note, that already the numbers $\{1,3,11,43,... , 1+2{4^k-1\over3},...\}$ as well as $\{5,19, 4\cdot 19-1, ... ,$ and $\{7,27, 4 \cdot 27-1, ... ,$ are already known to fall down to the cycles $1,1,...$ or $5,7,5,7...$.

For the 5-step-cycle we find the criterion $a_m \approx 2.77...$ and this allows no new solution besides the trivial cycle, because there is no other odd number "free" below $a_m \approx 2.77$

For the 6-step-cycle the same operation gives no new possibilities besides the (repetitions of) the trivial and of the 2-step-cycle.

For the 7-step cycle we find $a_m \approx 35.699$ and here indeed we have to check for some small $a$ below this number, where $a=13$ leads to $b=(3\cdot 13-1)/2=19 $ but which is already known as iterating into some cycle (namely $5,7,5,...$) . Then $a=17$ gives actually a new cycle (which you've already found).

Now this procedure can be done for higher $N$ parentheses; and for most of the smaller $N$ we find that $a_m$ is small such that all smaller numbers $a$ are already known to iterate to one of the already known cycles. This method allows to disprove a lot of attempted cycle-lengthes and small minimal elements $a$.
If you already know, for instance, that no $a \lt 10^8$ has a new cycle, then another lot of attempted cycle-lenghtes can easily be excluded because the $a_m$ are usally small. Special interesting high $a_m$ occur on $N$ given by the convergents of the continued fraction of $\log_2(3)$, but it is too much to expand on this here.


For example, knowing all $a \lt 10^8$ we can search for the first cycle-length such that $a_m$ is $a_m \ge 10^8$.

This is Pari/GP-code.
Here $N$ is the number of parentheses $(3- \frac1{a_k})$, or the number of odd values, or in other words the involved $N$'th power of $3$. And $S=A+B+C+...+$ the sum of the involved exponents at base $2$.
Because we have a minus in the parentheses, $2^S$ must be smaller than $3^N$ but must be as near as possible; $S$ is thus determined by the floor of $N \cdot \log_2(3)$.
The result of the computation is that the length $N$ of a cycle (measured in odd steps, the whole sum of steps is $N+S$) must be at least $N \ge 16266 $.

default(realprecision,200)
ld3=log(3)/log(2)
  \\ Pari/GP-output:  1.58496250072
{for(N=2,32000,
       S=floor(N*ld3);
       am=1/(3-2^(S/N));
       if(am<10^8,next());
       print([N,S,am]);
    ); }
 \\ output of Pari/GP (formatted)
  N        S          a_m
 16266    25781    2.129655 E8
 31867    50508    1.462138 E9


Appendix: A list of critical $N$ allowing $a_m$ (increasingly) large.

That means also, if all $a \le a_m$ are known to converge to one of the cycles $1$, or $5,7$ or $17,...$ in the $3x-1$-problem a new cycle can only exist of $a \gt a_m$ and the cycle length must be larger than the according $N$ in the table.

    k         N                S           am      k is index in cont.frac.
--------------------------------------------------------------------------
    2               1               1   1.000*2^0
    2               2               3   1.457*2^2
    4               7              11   1.116*2^5
    4              12              19   1.154*2^8
    6              53              84   1.033*2^13
    8             359             569   1.713*2^16
    8             665            1054   1.211*2^22
   10           16266           25781   1.587*2^27
   10           31867           50508   1.362*2^30
   12          111202          176251   1.199*2^33
   14          301739          478245   1.656*2^34
   14          492276          780239   1.376*2^35
   14          682813         1082233   1.944*2^35
   14          873350         1384227   1.268*2^36
   14         1063887         1686221   1.574*2^36
   14         1254424         1988215   1.894*2^36
   14         1444961         2290209   1.113*2^37
   14         1635498         2592203   1.286*2^37
   14         1826035         2894197   1.467*2^37
   14         2016572         3196191   1.655*2^37
   14         2207109         3498185   1.852*2^37
   14         2397646         3800179   1.029*2^38
   14         2588183         4102173   1.137*2^38
   14         2778720         4404167   1.249*2^38
   14         2969257         4706161   1.368*2^38
   14         3159794         5008155   1.492*2^38
   14         3350331         5310149   1.623*2^38
   14         3540868         5612143   1.760*2^38
   14         3731405         5914137   1.906*2^38
   14         3921942         6216131   1.029*2^39
   14         4112479         6518125   1.110*2^39
   14         4303016         6820119   1.196*2^39
   14         4493553         7122113   1.287*2^39
   14         4684090         7424107   1.384*2^39
   14         4874627         7726101   1.487*2^39
   14         5065164         8028095   1.597*2^39
   14         5255701         8330089   1.715*2^39
   14         5446238         8632083   1.841*2^39
   14         5636775         8934077   1.976*2^39
   14         5827312         9236071   1.061*2^40
   14         6017849         9538065   1.140*2^40
   14         6208386         9840059   1.225*2^40
   14         6398923        10142053   1.318*2^40
   14         6589460        10444047   1.420*2^40
   14         6779997        10746041   1.531*2^40
   14         6970534        11048035   1.654*2^40
   14         7161071        11350029   1.789*2^40
   14         7351608        11652023   1.940*2^40
   14         7542145        11954017   1.054*2^41
   14         7732682        12256011   1.149*2^41
   14         7923219        12558005   1.257*2^41
   14         8113756        12859999   1.381*2^41
   14         8304293        13161993   1.523*2^41
   14         8494830        13463987   1.690*2^41
   14         8685367        13765981   1.888*2^41
   14         8875904        14067975   1.063*2^42
   14         9066441        14369969   1.209*2^42
   14         9256978        14671963   1.392*2^42
   14         9447515        14973957   1.630*2^42
   14         9638052        15275951   1.949*2^42
   14         9828589        15577945   1.200*2^43
   14        10019126        15879939   1.545*2^43
   14        10209663        16181933   1.067*2^44
   14        10400200        16483927   1.687*2^44
   14        10590737        16785921   1.918*2^45
   16        21372011        33873836   1.263*2^47
   16        32153285        50961751   1.365*2^48
   16        42934559        68049666   1.621*2^49
   16        53715833        85137581   1.145*2^52
   18       225644606       357638239   1.240*2^55
   20       623217985       987777136   1.828*2^56
   20      1020791364      1617916033   1.604*2^57
   20      1418364743      2248054930   1.201*2^58
   20      1815938122      2878193827   1.667*2^58
   20      2213511501      3508332724   1.109*2^59
   20      2611084880      4138471621   1.440*2^59
   20      3008658259      4768610518   1.846*2^59
   20      3406231638      5398749415   1.177*2^60
   20      3803805017      6028888312   1.505*2^60
   20      4201378396      6659027209   1.944*2^60
   20      4598951775      7289166106   1.281*2^61
   20      4996525154      7919305003   1.748*2^61
   20      5394098533      8549443900   1.268*2^62
   20      5791671912      9179582797   1.038*2^63
   20      6189245291      9809721694   1.168*2^64
   22     12776063961     20249582285   1.349*2^65
   22     19362882631     30689442876   1.159*2^66
   22     25949701301     41129303467   1.794*2^66
   22     32536519971     51569164058   1.331*2^67
   22     39123338641     62009024649   1.959*2^67
   22     45710157311     72448885240   1.476*2^68
   22     52296975981     82888745831   1.188*2^69
   22     58883794651     93328606422   1.128*2^70
   22     65470613321    103768467013   1.002*2^72
$\endgroup$
  • $\begingroup$ @Helms, you say that, If there is counter example, and we know $n≈10^8$, What is the limit sequence lenth, for $n$ to your method? $\endgroup$ – Newuser Jul 13 '17 at 15:41
  • $\begingroup$ @Newuser : see update of my answer $\endgroup$ – Gottfried Helms Jul 13 '17 at 17:48
  • $\begingroup$ Very good answer +1 $\endgroup$ – Newuser Jul 13 '17 at 17:56
  • $\begingroup$ plase explain me, is $log_23$ mathematical argument or exact true? $\endgroup$ – Newuser Jul 13 '17 at 18:35
  • $\begingroup$ @Newuser: I don't understand the question. I mean $ld3=\log_2(3)$ to be defined as the constant ${\log(3) \over \log(2)} \approx 1.5849$ (in Pari/GP with default(realprecision,200) having it exact to at least 200 decimal digits). $\endgroup$ – Gottfried Helms Jul 13 '17 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.