%I #17 Mar 02 2024 03:52:34
%S 0,1,2,3,5,5,55,55,8,13,987,987,13,13,17711,17711,21,21,55,55,21,21,
%T 55,55,89,89,987,987,1597,1597,1836311903,1836311903,34,55,34,55,55,
%U 55,55,55,233,233,17711,17711,1597,1597,17711,17711,55,55,55,55,55,55,55
%N a(n) is the least Fibonacci number f such that f AND n = n (where AND denotes the bitwise AND operator).
%C This sequence is well defined:
%C - for any n >= 0, let w be such that n < 2^(w+1),
%C - the Fibonacci sequence mod 2^(w+1) is (3*2^w)-periodic,
%C - let p = 3*2^w,
%C - A000045(p) mod 2^(w+1) = A000045(0) mod 2^(w+1) = 0,
%C - A000045(p+1) mod 2^(w+1) = A000045(1) mod 2^(w+1) = 1,
%C - A000045(p-1) = A000045(p+1) - A000045(p), so A000045(p-1) mod 2^(w+1) = 1,
%C - A000045(p-2) = A000045(p) - A000045(p-1), so A000045(p-2) mod 2^(w+1) = -1,
%C - in other words, the binary expansion of A000045(p-2) ends with w+1 1's,
%C - and A000045(p-2) AND n = n, so a(n) <= A000045(p-2).
%H Paolo Xausa, <a href="/A370730/b370730.txt">Table of n, a(n) for n = 0..3800</a>
%F a(n) >= n with equality iff n is a Fibonacci number.
%F a(n) = A000045(A370731(n)).
%F a(a(n)) = a(n).
%F a(A000045(k)) = A000045(k) for any k >= 0.
%t A370730[n_] := Block[{k = -1}, While[BitAnd[Fibonacci[++k], n] != n]; Fibonacci[k]]; Array[A370730, 100,0] (* _Paolo Xausa_, Mar 01 2024 *)
%o (PARI) a(n) = { for (k = 0, oo, my (f = fibonacci(k)); if (bitand(f, n)==n, return (f););); }
%Y Cf. A000045, A007283, A295609 (analog for prime numbers), A370731, A370744.
%K nonn,base
%O 0,3
%A _Rémy Sigrist_, Feb 28 2024