[seqfan] Re: Binary Complement Sequences

[Neil Sloane]

Interesting problem, and certainly it should be in the OEIS.
Once some of the sequences have been created, can someone post the
A-numbers here?

Best regards
Neil

Neil J. A. Sloane, Chairman, OEIS Foundation.
Also Visiting Scientist, Math. Dept., Rutgers University,
Email: njasloane at gmail.com



On Sat, Dec 17, 2022 at 1:28 PM M. F. Hasler <oeis at hasler.fr> wrote:

> (seeing Allen's reply I notice I forgot to send off the one I wrote
> yesterday... Widely agreeing with Allen.)
>
> I think this is definitely interesting.
> The first sequence that should be submitted (if not already in OEIS) is the
> function itself,
> a(n) = binary complement of 3n,
> And then, yes,
> b(n) = number of iterations of a(.) required to reach 0.
>
>  I think a key to understanding and proving that the sequence always
> terminates are the "max values" (your 1b), so these should also be listed,
> but maybe (also / rather) in increasing order without repetitions.  Define
> them as starting values that are the maximum of their orbit (or some other
> way to say that all subsequent values are smaller).
>
> Then, to prove that all values terminate, it is sufficient (and equivalent)
> that any starting values  eventually reaches such a max number".
> I think it should be possible to prove by considering the binary expansion,
> and in particular the initial digits of the numbers. My hunch is that it
> should be sufficient to distinguish a finite number of patterns for the
> initial digits, and what might possibly come after that.
>
> - Maximilian
>
> On Fri, Dec 16, 2022, 15:01 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.
> >
> >
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>