[seqfan] Re: Binary Complement Sequences

Thu Dec 29 00:03:18 CET 2022

Tom, is that the *earliest* convergence of the trajectories of 717657 and
820650? I find the similarity in the number of steps to be positively
eerie. To me that's a phenomenon that cries out for explanation. Could it
be that the two trajectories get "entrained" in some way before step
79617(56,11)? In particular, what does step 45 of the trajectory of 717657
look like? This number is a "cousin" of 820650, and it would be interesting
to compare their bit patterns.

These two seeds, in binary, are
10101111001101011001 and
11001000010101010000.

On Wed, Dec 28, 2022 at 12:01 PM Tom Duff <eigenvectors at gmail.com> wrote:

> Term 7961756, when starting from 717657 and term 7961711 when starting from
> 820650 are identical 2890 digit numbers.
>
> On Tue, Dec 27, 2022 at 9:51 PM Tom Duff <eigenvectors at gmail.com> wrote:
>
> > 819991 is the first iterate of 425720, duh. So it's # of steps is 1 less
> > than 425720.
> > 717657 and 820560 don't meet up in the first million iterations. I'll
> look
> > a little farther tomorrow.
> >
> > On Tue, Dec 27, 2022 at 9:16 PM Tom Duff <eigenvectors at gmail.com> wrote:
> >
> >> I have posted a plot of the # of steps for each starting number from 1
> to
> >> 820559 to reach zero at http://iq0.com/fate.png
> >> (Doesn't include 717657 and 819991, which are still running, as is
> >> 820560, with those having run 19.9B, 5.2B and 6.9B steps so far. Maybe
> >> they'll be done in a week or so.)
> >> Note that the y axis of the plot is logarithmic.
> >> The horizontal lines are the most obvious feature. Presumably they're
> >> mostly numbers that quickly converge
> >> to a common trajectory -- I haven't checked.
> >> But the vertical stripes are the interesting part. I have no idea what's
> >> going on there.
> >>
> >> Also, I posted a plot of iteration number vs iterate size (in bits) at
> >> http://iq0.com/iterations-vs-size.png that shows the progress of
> 425720,
> >> 819991, 717657 and 820560, plotted over top of one another in different
> >> colors. It's pretty clear that 819991 is following the trajectory of
> 425720
> >> and 820560 is following 717657. There's a legend in the upper right
> corner
> >> indicating the colors of each curve.
> >>
> >> On Mon, Dec 26, 2022 at 10:27 AM Tom Duff <eigenvectors at gmail.com>
> 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/
>