[seqfan] Re: Patterns of congruence classes modulo 2^n in reduced Collatz sequences

[David Wilson]

The short answer is "yes, this is well known".

The "standard" Collatz iterate is

f(n) = n/2 if n even, 3n+1 if n odd.

If n is odd, we see that the next two iterates will be 3n+1, which is even, followed by n/2.
Therefore, we can fold together the two iterates after an odd number, getting the "abbreviated" iterate:

g(n) = n/2 if n even, (3n+1)/2 if n odd.

The trajectory of g is exactly the trajectory of f, except omitting the even numbers that immediately follow an odd number.
If the trajectory of f on n eventually reaches 1, so does the trajectory of g on n, so they are equivalent in that sense.

It is well known that if you know n mod 2^k, then you know whether the trajectory of g reaches a number <= n within k steps.
For a given n, the number of elements mod 2^k that reach a smaller element within k iterations is A182137.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Bob
> Selcoe
> Sent: Thursday, April 23, 2015 7:54 PM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Patterns of congruence classes modulo 2^n in reduced
> Collatz sequences
> 
> Hi Seqfans,
> 
> I recently found (what I think are) some interesting patterns in reduced
> Collatz sequences (i.e. rows in A256598).  The patterns are not obvious, but
> they appear to be quite regular.  Namely, the starting terms (S) can be
> treated as unique members of congruence classes modulo 2^n.
> Membership determines how many steps it takes from S to reach the first
> term < its preimage (D), and how many halving steps it takes from that
> preimage to reach D.   There's an easy method for determining membership,
> and a way to streamline calculations.  The least residues are easily put into
> array and triangle forms for analysis.
> 
> This all may be well-understood (does any of this sound familiar??) or old hat;
> but even if so, I think the array is worth contributing to OEIS.  The problem is,
> there's a bit more information needed to describe how the residues are
> calculated and how to interpret them than easily fits into an OEIS entry.  I
> started to create the entry and ended up writing a brief outline of a paper
> (about 3 pages in Word) which I may be able to edit down, but it's still a bit
> much.  So, I was hoping there might be a way to put the outline on the OEIS
> somewhere, and use it as a linked reference.
> 
> Is that possible?  If so, how?  If not, are there any suggestions on how I might
> proceed?  Or, is anyone familiar with any papers that specifically discuss the
> main idea about this type of congruence relation, which might serve as a
> link??  I've done my best to decipher some online sources by  Jeff Lagarias
> and others, but I couldn't find anything on the subject (or perhaps I did and
> couldn't understand it!).   Anyway, I just want to contribute the entry, so any
> help is greatly appreciated.
> 
> Thanks in advance,
> Bob Selcoe
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/