// 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)); } }
C# , System.Numerics, Multiplication, Karatsuba, Toom Cook, Division, Burnikel, Ziegler, Factorial, Luschny, Square Root, Zimmermann, Choose, Binomial Coefficient, Permutation, Combination, Eratosthenes, Primes, Fibonacci, Lucas, Pell, Catalan, Fast Random Number Generator, Overton
2012/10/31
Consecutive zeros in Fibonacci numbers
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment