[seqfan] Re: Binary Complement Sequences

[Tom Duff]

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/
>>>>>>
>>>>>