.
Randomly choose one Fibonacci number.
Will its leftmost digit more likely belong to the set {1, 4, 8, 9} or to the set {2, 3, 5, 6, 7}?
I didn't know about that alleged information. I went to this list of the first 300 Fibonacci numbers just
to quickly look at the leading 1's starting at n = 2 for F(2).
The first 300 Fibonacci numbers, factored
n
-------
2
2 + 67 = 69
69 + 67 = 136
136 + 67 = 203
203 + 67 = 270
F(n) corresponding to these have leftmost digits of 1.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Possible open hint: Consider the distribution in Benford's Law.
If you look at the leftmost digit of $F(n+67)$, apparently, it is extremely similar to the leftmost digit of $F(n)$. It is the same something like 97% of the time. Although, IIRC, that was a heuristic approach that discovered that, and I am not sure if it has been proven yet. It was true for the first thousand or so terms.
This graph does a good job of showing how similar they are:
http://www.wolframalpha.com/input/?i...g%5B10%5D))%5D
Yes, one can look at the distribution of Benford's Law at this site: https://en.wikipedia.org/wiki/Benford%27s_law
The Java Programming Code is given below. For 10, 20 and 40 numbers probability for Set 1 and Set 2:
The probability of set1 is: 4/10
The probability of set2 is: 6/10
The probability of set1 is: 9/20
The probability of set1 is: 11/20
The probability of set1 is: 19/40
The probability of set1 is: 21/40
Here's the source code for Java code. It will work as long as what the long integer variable can contain. Sorry can't give the comments.
Code:import java.util.Arrays; //Fibonacci Series using Recursion public class fibonacci { public static int fib(int n) { if(n == 0) return 0; else if(n == 1) return 1; else return fib(n - 1) + fib(n - 2); } public static void main (String args[]) { long[] fibs = new long[40]; for(int idx = 0; idx < fibs.length; ++idx) { fibs[idx] = fib(idx + 2); } long[] left1 = new long[]{1, 4, 8, 9}; long[] left2 = new long[]{2, 3, 5, 6, 7}; int count1 = 0; long rem1 = 0; long rem2 = 0; int count2 = 0; String ch; char ch1; long val; String val2; for(int i = 0; i < fibs.length; ++i) { val = fibs[i]; ch = String.valueOf(val); ch1 = ch.charAt(0); val2 = String.valueOf(ch1); rem1 = Long.parseLong(val2); if (Arrays.binarySearch(left1, rem1) >= 0) { ++count1; } if(Arrays.binarySearch(left2, rem1) >= 0) { ++count2; } } System.out.println("The probability of set1 is: " + count1 + "/" + fibs.length); System.out.println("The probability of set2 is: " + count2 + "/" + fibs.length); } }
You can calculate the probability of any factorial with the following java programming code. For anyone wants to know. change the variable j in the source code to get the total number of Fibonacci numbers. It's wayyy faster.
set1 is:
[1,4,8, 9]
set2 is:
[2,3,5,6,7]
The output:
>javac Fibo.java
>java Fibo
The probability of set1 is: 227/500
The probability of set2 is: 253/500
The probability of set1 is: 683/1500
The probability of set2 is: 756/1500
Code:import java.math.*; import java.util.*; public class Fibo{ private static Map<Integer, BigInteger> memo = new HashMap<>(); public static BigInteger fibonacci3(int n) { if (n == 0 || n == 1) { return BigInteger.ONE; } if (memo.containsKey(n)) { return memo.get(n); } BigInteger v = fibonacci3(n - 2).add(fibonacci3(n - 1)); memo.put(n, v); return v; } public static void main(String args[]) { int anInt; long num = 100; BigInteger temp; String s; BigInteger t; //input to print Fibonacci series up to how many numbers // System.out.println("Enter number up to which Fibonacci series to print: "); BigInteger i = BigInteger.valueOf(num); char ch; //BigInteger numb; String numb2; int[] left1 = new int[]{1,4,8, 9}; int[] left2 = new int[]{2,3,5,6,7}; //long i; int j = 1500; long count1 = 0; long count2 = 0; int rem1 = 0; int rem2 = 0; BigInteger val; for(int r=0; r < j;++r){ t = fibonacci3(r); temp = t; while(temp.compareTo(BigInteger.valueOf(10))>0){ temp=temp.divide(BigInteger.valueOf(10));} anInt = temp.intValue(); if(Arrays.binarySearch(left1, anInt)>=0) ++count1; if(Arrays.binarySearch(left2, anInt) >= 0) ++count2; } System.out.println("The probability of set1 is : " + count1 + "/" + j); System.out.println("The probability of set2 is : " + count2 + "/" + j); } }