Hailstone numbers producing a specific number of rises and falls

Question

How can I find a Hailstone number (from the Collatz sequence), such that it produces a sub-sequence containing $n$ rises and $m$ falls? The rises and falls can be in an arbitrary order. Here a rise step takes $x$ to $(3x+1)/2$, while a fall step takes $x$ to $x/2$.

Answer 1

There is a very general solution for this problem.

I write the Collatz-orbit in terms of the powers of $2$ as $$ b = T(a, [A_1,A_2,A_3,...A_N]) $$ where the $A_k$ denote the exponents of the powers of $2$ meaning $$ b = T(a,[A]) \overset{def}{:=} b= {3 a +1 \over 2^A } $$ and $$ b = T(a,[A_1,A_2]) \overset{def}{:=} b= {{3 a +1 \over 2^{A_1} } \cdot 3+1 \over 2^{A_2} }$$ and so on.

Then the function tfind(K) with the "key" $K=[A_1,A_2,...,A_N]$ defines the trajectory with $N$ odd steps $3x+1$ and $S=\sum_{k=1}^N A_k$ the number of even steps $x/2$ .

Then if you want $m$ odd steps (increasing) and $n$ even steps with the transformation rules $(3x+1)/2$ and $x/2$ , you write [a,b]=tfind([1,1,1...,1,1+n]) with $m-1$ the numbers of $1$ and $1+n$ as obvious.

The function tfind(K) in Pari/GP goes this way:

mkQ(Key)=my(a);a=0;for(k=1,#Key,a=(3*a+1)/2^Key[k]);a 

and

{tfind(Key,idx=0) = my(a,b,q,S,N,S2,N3);
  S=vecsum(Key);N=#Key; S2 = 2^S; N3=3^N; 
  q=mkQ(Key) * S2;      \\ in testphase: check sanity: print(q);
  a = (-q/N3 ) % S2;
  b = ( q/S2 ) % N3;    \\ it might occur that b is even, then
                        \\ a correction step is required:
  if(b % 2 ==0 ,a += S2; b += N3);
  if(idx<>0 , a += 2*idx*S2; b += 2*idx*N3 );
  return([a,b]); }

This gives for instance

tfind([1,2])
%53 = [11, 13]

which in the $(3x+1)/2$ and $x/2$ notation gives $2$ odd (=increasing) steps and $2-1=1$ additional decreasing ($x/2$) steps and is performed by $$b = T(a,[1,2])$$ transformation.

The optional parameter idx allows to select further solutions $[a,b]$ :

[a,b]=tfind([1,2],0)  \\ gives: [a,b] = [11, 13]
[a,b]=tfind([1,2],1)  \\ gives: [a,b] = [27, 31]
[a,b]=tfind([1,2],2)  \\ gives: [a,b] = [43, 49]
[a,b]=tfind([1,2],3)  \\ gives: [a,b] = [59, 67]
 ...

Note that all $a_k$ are in the same residue class of $2 \cdot 2^S$ where $S$ is the sum of all exponents (here $S=3$), and $b_k$ are in the same residue class of $2 \cdot 3^N$ where $N$ is the number of odd steps (here: $N=2$)

If one wants the smallest solution of $m=6$ odd steps and $n=4$ additional even steps (in terms of the $(3x+1)/2$ and $x/2$ transformation) then one calls

[a,b]=tfind([1,1,1,1,1,5])  \\ gives: [a,b] = [1599, 1139]

---

This is all in Pari/GP and this software allows large $N$ (in the millions) and $S$ accordingly.

---

A nice application is then to find a pair of $[a,b]$ which forms a "glide" (term coined by Eric Roosendaal, I think ) where the trajectory is always increasing, but very slow:

[a,b]=tfind([2]) \\ gives:%196 = [1, 1]   equality, trivial cycle
[a,b]=tfind([1]) \\ gives:%198 = [3, 5]   increasing: ok
[a,b]=tfind([1,3]) \\ gives:%*** = [19,11]   decreasing: exponent too large!!
[a,b]=tfind([1,2]) \\ gives:%200 = [11, 13]   increasing: ok
[a,b]=tfind([1,2,3]) \\ gives:%*** = [11, 5]   decreasing: exponent too large!!
[a,b]=tfind([1,2,2]) \\ gives:%202 = [43, 37]   decreasing: exponent too large!!
[a,b]=tfind([1,2,1]) \\ gives:%204 = [27, 47]   increasing: ok
[a,b]=tfind([1,2,1,3]) \\ gives:%206 = [187, 119]   decreasing: exponent too large!!
[a,b]=tfind([1,2,1,2]) \\ gives:%208 = [123, 157]   increasing: ok
[a,b]=tfind([1,2,1,2,2]) \\ gives:%210 = [379, 361]   decreasing: exponent too large!!
[a,b]=tfind([1,2,1,2,1]) \\ gives:%212 = [251, 479]   increasing: ok
[a,b]=tfind([1,2,1,2,1,3]) \\ gives:%214 = [1531, 1091]      decreasing: exponent too large!!
[a,b]=tfind([1,2,1,2,1,2]) \\ gives:%216 = [1019, 1453]   increasing: ok
[a,b]=tfind([1,2,1,2,1,2,2]) \\ gives:%218 = [3067, 3277]   increasing: ok
[a,b]=tfind([1,2,1,2,1,2,2,2]) \\ gives:%220 = [11259, 9019]   decreasing: exponent too large!!
[a,b]=tfind([1,2,1,2,1,2,2,1]) \\ gives:%222 = [7163, 11477]   increasing: ok

(Note that this is only a simple synthetic/schematic way. There are possibilities for other exponent-sequences which spit out smoother solutions for $[a,b]$ - meaning that the final $b$ is nearer to the initial $a$)

Answer 2

Ah I think I got it. I believe $(2^n-1)*2^m$ will have $m$ falls followed by $n$ rises.

Answer 3

From this I would say $$2^n(3^{-n}\mod 2^m)-1$$

EDIT:

To make a parallel with Gottfried answer (also using rational modulo), here is what we would have if we limit tfind to cases with n increases and m decreases (as the question stated), and allow to land on even numbers (not specified in the question, but mentioned by Gottfried). Since a path is cyclic in a Collatz sequence, I also included Gottfried index.

tfind($n$,$m$,$idx$) = [$2^n(3^{-n}\mod 2^m)-1+idx\cdot2^{m+n}$,$\frac{3^n(3^{-n}\mod2^m)-1}{2^m}+idx\cdot3^n$]

PARI/GP code

tf(n,m,idx)=print("[",2^n*(3^-n%2^m)-1+idx*2^(m+n),",",(3^n*(3^-n%2^m)-1)/2^m+idx*3^n,"]")

Note that the second value can be simplified to $(-2^{-m}\mod 3^n)+idx\cdot 3^n$