A359209 Numbers that under iteration of the map x->A359194(x) (binary complement of 3n) until 0 is reached never exceed the initial term.

0, 1, 2, 5, 10, 21, 39, 40, 42, 71, 72, 78, 85, 142, 150, 157, 163, 167, 168, 170, 285, 291, 300, 303, 311, 313, 315, 316, 317, 319, 320, 321, 322, 327, 328, 329, 331, 333, 334, 335, 336, 338, 339, 340, 341, 569, 571, 572, 573, 575, 576, 577, 578, 579

Offset: 1

Author

Joshua Searle, Dec 20 2022

Keywords

• nonn
• base

Comments

If it can be shown that all iterations of A359194 eventually reach one of the terms of this sequence, it would prove that all such trajectories are finite.

From M. F. Hasler, Dec 26 2022: (Start)

(1) If A359194(x) = a(k) for some a(k) < x, then x is also in the sequence.

(2) The orbit of any x under iterations of A359194 is finite if and only if it reaches a term of this sequence.

(3) No term has binary digits starting with '11...', i.e., all terms > 1 have binary digits starting '10...'.

(4) If the 3rd binary digit of a(n) is a '1', it cannot be followed by another bit 1, so all terms > 5 have a binary representation of the form '100...' or '1010...'

(5) A substring of '11', i.e., two consecutive bits 1, in a term of this sequence, is necessarily preceded by an earlier substring '00', i.e., two consecutive bits 0 to the left of the '11'. [This implies (3) and (4).] (End)

Examples

			40 is a term since its trajectory is 40 -> 7 -> 10 -> 1 -> 0, which never exceeds 40.
		

Crossrefs

Cf. A035327, A359194, A359207, A359208, A359255.

Programs

Maple

bc:= n -> 2^(1+ilog2(n))-1-n: bc(0):= 1:
filter:= proc(n) local x;
  x:= n;
  while x <> 0 do
    x:= bc3(x);
    if x > n then return false fi;
  od;
  true
end proc:
select(filter, [$0..1000]); # Robert Israel, Dec 22 2022

Mathematica

f[n_] := BitXor[3 n, 2^IntegerPart[Log2[3 n] + 1] - 1]; Select[Range[0, 200], Function[n, AllTrue[NestWhileList[f, n, # != 0 &], # <= n &]]] (* Michael De Vlieger, Dec 21 2022 *)

PARI

f(n) = if(n, bitneg(n, exponent(n)+1), 1); \\ A035327
isok(m) = my(km=m); while (m, m=f(3*m); if (m>km, return(0))); return(1); \\ Michel Marcus, Dec 21 2022

Python

def f(n): return 1 if n == 0 else (m:=3*n)^((1 << m.bit_length())-1)
def ok(n):
    i, fi, m = 0, n, n
    while fi != 0 and m <= n: i, fi, m = i+1, f(fi), max(m, fi)
    return m <= n
print([k for k in range(580) if ok(k)]) # Michael S. Branicky, Dec 20 2022