login
a(n) is the least Fibonacci number f such that f AND n = n (where AND denotes the bitwise AND operator).
3

%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