[seqfan] Re: Binary Complement Sequences

Fri Dec 16 22:38:07 CET 2022

I think this idea is charming. A little bit of thinking suggests that the
fractional part of the binary log of the seed should correlate in some way
with the trajectory length, especially for larger seeds. I've started doing
a little investigation myself, but I don't expect to have anything
interesting to report anytime soon.

With the Collatz function, at most two integers map to any given integer
(for example, 4 is preceded by 1 or 8). But with this
triple-then-ones-complement function, each value has (I think) an infinite
sequence of predecessors, unless it is equal to 2 modulo 3, in which case
it has none.. For example, the preimage of 0 is all integers of the form
(4^n - 1) / 3, (see A002450 <https://oeis.org/A002450>). Predecessors of 1
are all of the form 2(4^n - 1)/3.

With the Collatz function, a naive probabilistic argument immediately
suggests that there are a finite number of small limiting orbits (although
only experiment reveals that there is just one). The corresponding argument
for this function will involve the distribution of the fractional part of
the binary log. Given your experimental evidence, I guess it will reveal an
average growth rate less than 1. This won't constitute a proof of
convergence, any more than it does with the Collatz function, but it will
be suggestive.

As long as the iterates remain large, the low-order bits quickly enter
cycles, in which they remain until the number shrinks to the corresponding
order of magnitude. The low-order bit alternates between 1 and 0; the two
low-order bits read [0, 3, 2, 1] and repeat, and the low three bits read
[0, 7, 2, 1, 4, 3, 6, 5]. I don't know if there is always a single cycle of
length 2^n, but this is an obvious early question.

It would probably be instructive to try "solving" for various short cycle
lengths. Something about the way the bits oscillate suggests that (unlike
with the Collatz iteration), there may be a simple argument that rules out
cycles other than [0]; this, of course, will not rule out the possibility
of an exotic aperiodic orbit.

When you start adding sequences to OEIS, please remember to add the
underlying function (triple, then complement). I think it starts 0, 1, 6,
3, 0, 13, 10 ..., and is definitely not in OEIS already.

On Fri, Dec 16, 2022 at 2:00 PM Joshua Searle (larry) <jprsearle at gmail.com>
wrote:

> Hello,
>
> (In my enthusiasm, I sent this first time around before I got confirmation
> of being added to the mailing list so I don’t think anyone saw it, oops)
>
> I am looking for some help finding some more terms for a set of sequences
> I intend to add to the OEIS.
>
> It is a similar algorithm to that of the collatz algorithm, but instead of
> of multiplying by 3 and adding when odd, and dividing when even, it goes as
> follows:
>
> on any number:
> -multiply by 3
> -find the binary complement (if it is 1001010 in binary, the complement is
> 0110101). This is equivalent to subtracting from the next highest mersenne
> number.
>
> this is treated as all one step, so a seed of 2 produces the sequence
> [2,1,0]
> 3 produces the longer [3, 6, 13, 24, 55, 90, 241, 300, 123, 142, 85, 0].
>
> For lack of a better name I’ve called these binary complement sequences.
>
> While you might expect similar behaviour to the collatz algorithm (and it
> largely does), it turns out this can support sequences that are
> staggeringly long in length. The starting seed of 28 takes 7572 terms to
> terminate and I terminated my code after seed 425720 exceeded 10 billion
> terms! I do think all sequences terminate.
>
> The following sequences can be made from it:
>
> 1a) step length: (seed = term 0, natural numbers)
> 1 <= n <= 30
> 1, 2, 11, 12, 1, 10, 3, 4, 13, 2, 19, 80, 9, 2, 15, 16, 81, 14, 11, 12, 1,
> 6, 83, 8, 73, 22, 79, 7572, 5, 18…
>
> 1b) max value: (natural numbers)
> 1 <= n <= 20
> 1, 2, 300, 300, 5, 300, 10, 10, 300, 10, 300, 328536, 300, 21, 300, 300,
> 328536, 300, 300, 300…
>
> 2a) seeds with record step length:
> 1 <= n <= 25, all known terms.
> 1, 2, 3, 4, 9, 11, 12, 17, 23, 28, 33, 74, 86, 180, 227, 350, 821, 3822,
> 4187, 5561, 6380, 6398, 22174, 22246, 26494
>
> 2b) step lengths of 2a:
> 1 <= n <= 25, all known terms
> 1, 2, 11, 12, 13, 19, 80, 81, 83, 7572, 7573, 7574, 7578, 7580, 664475,
> 664882, 3180929, 3180930, 3180931, 3181981, 3181988, 3182002, 3182226,
> 120796790, 556068798
>
> 2c) max values of 2a:
> 1 <= n <= 25, al known terms, abbreviated for readability
> 1, 2, 300 (x4), 328536 (x3), ~1.23*10^53 (x5), ~3.26*10^552 (x2),
> ~2.03*10^933 (x7), ~9.38*10^8306, ~1.67*10^16667
>
> 3a) seeds with record step length and new maxima (excludes all the side
> sequences, new maxima are not necessarily larger than the previous):
> 1 <= n <= 12, all known terms
> 1, 2, 3, 12, 28, 227, 821, 22246, 26494, 103721, 204953, 425720
>
> 3b) step lengths of 3a
> 1 <= n <= 11, all known terms plus a lower bound for next one.
> 1, 2, 11, 80, 7572, 664475, 3180929, 120796790, 556068798, 572086533,
> 1246707529, 9999999999+
>
> 3c) max values of 3a
> 1 <= n <= 11, all known terms plus a lower bound for next one.
> 1, 2, 300 , 328536, ~1.23*10^53, ~3.26*10^552, ~2.03*10^933,
> ~9.38*10^8306, ~1.67*10^16667, ~2.42*10^14081, ~9.81*10^25580,
> >=2.09*10^114778
>
> Observations and questions:
> -The max value achieved by a sequence has roughly sqrt(step count) digits.
> -For how many terms can a sequence continually increase? I haven’t tracked
> it but even 3 has 6 consecutively increasing terms in its sequence.
> -The penultimate term of a sequence must be of the form [(2^3n-1)-1]/3. I
> haven’t tracked how often sequences fall into these.
> -What does a log plot look like of these sequences? They have had far too
> many data points for basic graphing software to handle!
> -And of course, does every sequence terminate? (probably unanswerable)
>
> Being able to terminate 425720 would be nice, despite several drastic
> speedups from my rickety initial coding effort, still took 67 hours to
> compute 10 billion terms of the sequence. I can provide a data file where I
> copy and pasted results from general searches if requested. For example, I
> can give you term 9,999,999,999 of seed 425720, or the step lengths/maxima
> of sequences up to 425720 that didn’t get caught by my side-sequence filter.
>
> I’m worrying that this is too long; I hope that at least someone reads
> until the end!
>
> Joshua Searle.
>
> Email: jprsearle at gmail.com <mailto:jprsearle at gmail.com> (if you want to
> request files)
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>