Pagina's

2012/10/31

Consecutive zeros in Fibonacci numbers

// When I looked at the Fibonacci Sequence Binary Plot
// http://mathworld.wolfram.com/FibonacciNumber.html
// and the statement: F(2^n+2^(n+1)) ends in n+2 zeros.
// I wondered: Are there n+2 consecutive zeros for smaller indexes?
// Or: Indexes of Fibonacci numbers whose binary expansions have 
//     record numbers of consecutive zeros.
// It seems there are.
// Example: The first four records occur at 3, 6, 12, and 19:
// F(3)=10 2 (one zero)
// F(6)=1000 2 (three zeros)
// F(12)=10010000 2 (four zeros)
// F(19)=1000001010101 2 (five zeros)
//
//      Index  Zeros 
//          3    1  
//          6    3  
//         12    4  
//         19    5
//         38    6
//         42    7
//         68   12
//        243   13
//        384   14  
//        515   16
//        740   19
//       1709   24
//       5151   27
//      11049   28
//      45641   30
//      94729   31
//     185610   34
//     644593   35
//     726681   39
//    2296396   40
//    3098358   42
//    6178778   43
//   15743325   45
//   22436908   48
//
// In the program below, 
// the first loop "for (; zmax < 15; i++)" 
// searches for consecutive zerobits, bit by bit.
// As soon as 15 zeros are found, 
// the second loop "for (; i < int.MaxValue; i++)"
// searches for consecutive zerobytes, byte by byte,
// adding leading/trailing zerobits of the bytes before/after those zerobytes.
// It's much faster than searching bit by bit.

using System;
using Xint = System.Numerics.BigInteger; // Project>>Add Reference>>System.Numerics
class fibonacciRepeatingZeros
{
    static void Main()
    {
        Xint F0 = 1, F1 = 0, F2 = 0;
        int i = 1, z, zi = 0, zmax = 0; // z=zerobits,zi=maxzerobitsF(i)
        for (; zmax < 15; i++)
        {
            F2 = F1 + F0; F0 = F1; F1 = F2;
            z = 0;
            for (; !F2.IsOne; F2 /= 2)
            {
                if (F2.IsEven)
                {
                    if (zi < ++z) zi = z;
                }
                else z = 0;
            }
            if (zmax < zi)
            {
                zmax = zi;
                Console.WriteLine(i + " " + zi);
            }
        }
        byte[] b; int j, j0, bL; z = 0;
        for (; i < int.MaxValue; i++)
        {
            F2 = F1 + F0; F0 = F1; F1 = F2;
            b = F2.ToByteArray();
            bL = b.Length - 1;
            if (b[bL] == 0) bL--;
            j = 0;
            if (b[0] == 0)
            {
                z = 8;
                while (b[++j] == 0) z += 8; // add zerobits
                if (zi < z + 7)
                {
                    z += tz(b[j]);
                    if (zi < z) zi = z;
                }
                z = 0;
            }
            while (++j < bL)
            {
                if (b[j] == 0)
                {
                    j0 = j - 1;
                    z = 8;
                    while (b[++j] == 0) z += 8; // add zerobits
                    if (zi < z + 14)
                    {
                        z += lz(b[j0]);
                        if (zi < z + 7)
                        {
                            z += tz(b[j]);
                            if (zi < z) zi = z;
                        }
                    }
                    z = 0;
                }
            }
            if (zmax < zi)
            {
                zmax = zi;
                Console.WriteLine(i + " " + zi);
            }
        }
        Console.ReadLine();
    }
    private static int lz(byte b) // leading zeros, b > 0
    {
        return b < 1 << 4 ? b < 1 << 2 ? b < 1 << 1 ? 7 : 6 :
                                         b < 1 << 3 ? 5 : 4 :
                            b < 1 << 6 ? b < 1 << 5 ? 3 : 2 :
                                         b < 1 << 7 ? 1 : 0;
    }
    private static int tz(byte b) // trailing zeros
    {
        return 7 - lz((byte)(b & -(sbyte)b));
    }
}