cp's OEIS Frontend

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

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