[seqfan] Re: Binary Complement Sequences

Mon Dec 26 22:01:29 CET 2022

I think we are all having a collective sigh of relief, here. Tom Duff, that
was magnificent work. Larry Searle, it was a really cool idea.

That graph sure looks like an unbiased random walk to me.

The fact that the low-order k bits cycle with period 2^k (somebody proved
this, right?) seems to me to contain the seed of a proof that there are no
cycles. I don't see the whole proof, but it's super-suggestive. Maybe
somebody out there can clinch the reasoning.

That would mean that the only chance of Searle's original convergence
conjecture being false would be a seed whose orbit diverged without limit.
This doesn't feel impossible to me: I envision some kind of engineering
approach, constructing a bit string of the form X A^j Y where you could
prove that in S steps the iterate would be X A^(j+1) Y. I could easily
imagine the magic values of X, A, and Y being each 10 or 20 bits long. That
would mean that it's plausible that the smallest provably divergent seed
might be 50 or 60 bits long, and we are still messing around with 15-20 bit
seeds.

I am sure, though, that we now have the wherewithal to prove that *almost*
all seeds converge.

On Mon, Dec 26, 2022 at 1:53 PM Joseph Myers <jsm at polyomino.org.uk> wrote:

> A heuristic argument that it should always converge to zero is to treat it
> as a random walk (where, if you consider a term as a power of 2 times a
> value uniformly distributed in [1,2), the length of the term goes up by 1
> bit with probability 2/3, down by n bits with probability 1/(3*2^n), so
> changes by 0 bits on average, and the theory of one-dimensional random
> walks then says what to expect in terms of the length always reaching 0
> and the distribution of the time taken to do so).  That probably doesn't
> give any more hope of proving it converges to zero than the similar,
> simpler argument for the Collatz process, however.
>
> --
> Joseph S. Myers
> jsm at polyomino.org.uk
>
> On Mon, 26 Dec 2022, Tom Duff wrote:
>
> > I didn't expect this. I really thought it would diverge. This seriously
> > indicates that it invariably converges to zero. That, not the computation
> > of more values, is the front on which we need progress, now.
> >
> > On Mon, Dec 26, 2022 at 10:25 AM Tom Duff <eigenvectors at gmail.com>
> wrote:
> >
> > > And it just finished! 425720 takes 87,037,147,316 steps to converge to
> 0.
> > > (Or my  computer glitched, or I have a bug. I seriously doubt the
> latter,
> > > because all my other results match what others have reported.)
> > >
> > > On Mon, Dec 26, 2022 at 8:23 AM Tom Duff <eigenvectors at gmail.com>
> wrote:
> > >
> > >> My run of 425720 has been going for almost 83 billion iterations. The
> > >> length of the current iterate is down to under 167000 bits (from a
> maximum
> > >> of roughly 595000 bits). Excitement reigns!
> > >>
> > >> On Fri, Dec 16, 2022 at 11:00 AM 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/
> > >>>
> > >>
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>