[seqfan] Re: Binary Complement Sequences

[Joshua Searle (larry)]

> Allan Wechsler 16 December 2022 at 21:38:07 GMT
> 
> When you start adding sequences to OEIS, please remember to add the
> underlying function (triple, then complement). I think it starts 0, 1, 6,
> 3, 0, 13, 10 ..., and is definitely not in OEIS already.

> "M. F. Hasler” 17 December 2022 at 18:27:51 GMT
> 
> The first sequence that should be submitted (if not already in OEIS) is the
> function itself,
> a(n) = binary complement of 3n,

I’ve submitted the sequence, its A359194. I hadn’t submitted a sequence before now so once I’ve got the format down I’ll do the iteration based sequences.

> "M. F. Hasler” 17 December 2022 at 18:27:51 GMT
> 
> 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

I could also add this sequence, which makes 10 total. This isn’t excessive is it?

> Tom Duff 17 December 2022 at 20:30:54 GMT
> 
> I have 425720 running on my desktop machine right now. It's been going for
> just under an hour and after 1,572,000,000 iterations it's working on a
> 125,000+ bit number. Graphing the length of the iterate vs the iteration
> number (see___) gives a fairly ragged
> curve, but it doesn't look like it's likely to come back down. Of course,
> in the absense of a proof, anything might happen.

Seems like 2-3x faster than my code. Should reach 10 billion in about a day if it scales the same way as mine. Since I’m replying 3 days after the fact, you may be at 20 odd billion or it may have terminated! Considering the jumps in step count between record holders, it is not improbable that it could reach 100 billion iterations before termination. Assuming it actually does of course.

Given n balanced 1d random walks of constant step size, how far would you expect the last path to go before returning to the “0” point? I have no idea if this has any relevance to this problem but perhaps it could be used as a measuring stick?


Joshua Searle

(I am using the weekly digest to prevent my inbox being swamped)