Looking for counter-examples in Collatz-like sequences

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

maybe just use the reverse map:

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

Answer 5

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

Answer 6

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