# Thread: Leftmost digit of a randomly chosen Fibonacci number

1. ## Leftmost digit of a randomly chosen Fibonacci number

.

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}?

2. ## Re: Leftmost digit of a randomly chosen Fibonacci number

Originally Posted by greg1313
.

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}?
IIRC, doesn't the leftmost digit have repetition? Something like it repeats every 67 numbers?

3. ## Re: Leftmost digit of a randomly chosen Fibonacci number

Originally Posted by SlipEternal
IIRC, doesn't the leftmost digit have repetition? Something like it repeats every 67 numbers?
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.

4. ## Re: Leftmost digit of a randomly chosen Fibonacci number

Originally Posted by greg1313
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

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

5. ## Re: Leftmost digit of a randomly chosen Fibonacci number

$\phi^{67}\approx 10^{14}$ is why the digits are so close.

Anyway, the split is almost 50/50 based on Bedford's law.

6. ## Re: Leftmost digit of a randomly chosen Fibonacci number

Originally Posted by SlipEternal

Anyway, the split is almost 50/50 based on Bedford's [sic] law.
Yes, one can look at the distribution of Benford's Law at this site: https://en.wikipedia.org/wiki/Benford%27s_law

7. ## Re: Leftmost digit of a randomly chosen Fibonacci number

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

}
}

8. ## Re: Leftmost digit of a randomly chosen Fibonacci number

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

}
}