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

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

Author

Rémy Sigrist, Feb 28 2024

Keywords

• nonn
• base

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).

Links

• Paolo Xausa, Table of n, a(n) for n = 0..3800

Crossrefs

Cf. A000045, A007283, A295609 (analog for prime numbers), A370731, A370744.

Programs

Mathematica

A370730[n_] := Block[{k = -1}, While[BitAnd[Fibonacci[++k], n] != n]; Fibonacci[k]]; Array[A370730, 100,0] (* Paolo Xausa, Mar 01 2024 *)

PARI

a(n) = { for (k = 0, oo, my (f = fibonacci(k)); if (bitand(f, n)==n, return (f););); }

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.