# Looking for counter-examples in Collatz-like sequences

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?

• By $f^k(n)$ you mean the $k$-th composition of $f$ with itself ? Like $f^3(n) = f(f(f(n)))$ ? – Zubzub Jul 13 '17 at 9:11
• Yes.you are true. – Newuser Jul 13 '17 at 9:14
• @Zubzub ı find counterexample. $95$ is not a counterexample. – Newuser Jul 13 '17 at 9:29
• 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). – Zubzub Jul 13 '17 at 12:39
• Comments at OEIS A001281 suggest this is an open problem, with the only known orbits being those starting at 1, 5, 17. – nickgard Jul 13 '17 at 15:29

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.

• No idea what you are trying to communicate with that... – Dirk Jul 13 '17 at 9:15
• 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$). – Jyrki Lahtonen Jul 13 '17 at 9:32
• @Jyrki Lahtonen you are correct. – Newuser Jul 13 '17 at 9:36
• 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. – Dirk Jul 13 '17 at 9:54
• Please look carefully. I wrote all odd sequence. Because, $17,25...91$ at the same sequence too. – Newuser Jul 13 '17 at 10:02

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.

• Ohh, ı only find odd counterexample – Newuser Jul 13 '17 at 9:51
• 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? – Thomas Baruchel Jul 13 '17 at 9:54
• Oh ı am so sorry.Dear Thomas.No problem.dont delete – Newuser Jul 13 '17 at 9:59
• Thank you, for improve my question. @Thomas – Newuser Jul 13 '17 at 16:25

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

• 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. – Newuser Jul 13 '17 at 11:59
• 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. – Thomas Baruchel Jul 13 '17 at 12:19
• Yes and as I mentioned I tried up to $n=100000$ and no such examples exist. – Qidi Jul 13 '17 at 12:24
• @Qidi...Very good. Now, I know that if there is counterexample ıt must be $> 100000$ thank so much! $100000$ so big...perfect. – Newuser Jul 13 '17 at 13:02

maybe just use the reverse map:

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

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

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

• @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? – Newuser Jul 13 '17 at 15:41
• @Newuser : see update of my answer – Gottfried Helms Jul 13 '17 at 17:48
• Very good answer +1 – Newuser Jul 13 '17 at 17:56
• plase explain me, is $log_23$ mathematical argument or exact true? – Newuser Jul 13 '17 at 18:35
• @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). – Gottfried Helms Jul 13 '17 at 18:40