Fibonacci Number Analysis

The Fibonacci numbers F(n) are defined recursively as follows.

$F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2) \ (n \ge 2)$

Given an integer range [lo, hi], find every Fibonacci number that lies within the range (endpoints included) and, for each one, print the following information.

• The index n and the value F(n)
• Its base-2 logarithm lg, rounded to six decimal places
• Its prime factorization in ascending order, with each repeated prime printed as many times as it occurs

The following rules apply.

• 0 is the first Fibonacci number, but the logarithm of 0 is undefined, so print lg does not exist instead of a logarithm.
• 0 and 1 have no prime factors, so print No prime factors instead of a factorization.
• If the range contains no Fibonacci number, print No Fibonacci numbers in the range.

Fibonacci numbers with different indices but equal values, such as F(1) = 1 and F(2) = 1, are printed separately.

The input consists of several ranges. Each range is given on its own line as two non-negative integers lo and hi. Both numbers are written in hexadecimal with a 0x prefix; for example, 0x1a denotes 26.

Every integer fits in the signed 64-bit range. Input ends at end of file (EOF), or at the first line where lo ≥ hi. (The line that meets the termination condition is not processed.)

For each processed range, first print the header Range {lo} to {hi}: using the decimal values. Then, for each Fibonacci number in the range, print two lines in the following format.

• First line: Fib({n}) = {value}, lg is {log} (if the value is 0, print Fib({n}) = 0, lg does not exist)
• Second line: Prime factors: {factors} (if the value is 0 or 1, print No prime factors)

The base-2 logarithm (lg) is printed to six decimal places, and prime factors are separated by single spaces. Separate the output of different ranges with a single blank line.