login
A370730
a(n) is the least Fibonacci number f such that f AND n = n (where AND denotes the bitwise AND operator).
3
0, 1, 2, 3, 5, 5, 55, 55, 8, 13, 987, 987, 13, 13, 17711, 17711, 21, 21, 55, 55, 21, 21, 55, 55, 89, 89, 987, 987, 1597, 1597, 1836311903, 1836311903, 34, 55, 34, 55, 55, 55, 55, 55, 233, 233, 17711, 17711, 1597, 1597, 17711, 17711, 55, 55, 55, 55, 55, 55, 55
OFFSET
0,3
COMMENTS
This sequence is well defined:
- for any n >= 0, let w be such that n < 2^(w+1),
- the Fibonacci sequence mod 2^(w+1) is (3*2^w)-periodic,
- let p = 3*2^w,
- A000045(p) mod 2^(w+1) = A000045(0) mod 2^(w+1) = 0,
- A000045(p+1) mod 2^(w+1) = A000045(1) mod 2^(w+1) = 1,
- A000045(p-1) = A000045(p+1) - A000045(p), so A000045(p-1) mod 2^(w+1) = 1,
- A000045(p-2) = A000045(p) - A000045(p-1), so A000045(p-2) mod 2^(w+1) = -1,
- in other words, the binary expansion of A000045(p-2) ends with w+1 1's,
- and A000045(p-2) AND n = n, so a(n) <= A000045(p-2).
FORMULA
a(n) >= n with equality iff n is a Fibonacci number.
a(n) = A000045(A370731(n)).
a(a(n)) = a(n).
a(A000045(k)) = A000045(k) for any k >= 0.
MATHEMATICA
A370730[n_] := Block[{k = -1}, While[BitAnd[Fibonacci[++k], n] != n]; Fibonacci[k]]; Array[A370730, 100, 0] (* Paolo Xausa, Mar 01 2024 *)
PROG
(PARI) a(n) = { for (k = 0, oo, my (f = fibonacci(k)); if (bitand(f, n)==n, return (f); ); ); }
CROSSREFS
Cf. A000045, A007283, A295609 (analog for prime numbers), A370731, A370744.
Sequence in context: A095296 A256301 A226609 * A157260 A336017 A291486
KEYWORD
nonn,base
AUTHOR
Rémy Sigrist, Feb 28 2024
STATUS
approved