[seqfan] Re: Binary Complement Sequences

[Tom Duff]

It took 684803 seconds (190 hours or 7.9 days) to count to 87037147316.
That's 127098 iterations per second, or 7.868 microseconds per iteration.

On Mon, Dec 26, 2022 at 8:09 PM Brendan McKay via SeqFan <
seqfan at list.seqfan.eu> wrote:

> Hi Tom, Congratulations on that nice achievement.  Can you estimate
> approximately how long it took for each step on average?
>
> Cheers, Brendan.
>
> On 27/12/2022 5:25 am, Tom Duff 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/
>