Results 1 to 8 of 8
Like Tree1Thanks
  • 1 Post By SlipEternal

Thread: Leftmost digit of a randomly chosen Fibonacci number

  1. #1
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    227
    Thanks
    109

    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}?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Leftmost digit of a randomly chosen Fibonacci number

    Quote Originally Posted by greg1313 View Post
    .


    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?
    Last edited by SlipEternal; Jun 6th 2018 at 12:11 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    227
    Thanks
    109

    Re: Leftmost digit of a randomly chosen Fibonacci number

    Quote Originally Posted by SlipEternal View Post
    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.
    Last edited by greg1313; Jun 6th 2018 at 01:10 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    Re: Leftmost digit of a randomly chosen Fibonacci number

    Quote Originally Posted by greg1313 View Post
    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
    Last edited by SlipEternal; Jun 6th 2018 at 01:45 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,728
    Thanks
    1521

    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.
    Thanks from greg1313
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2016
    From
    Earth
    Posts
    227
    Thanks
    109

    Re: Leftmost digit of a randomly chosen Fibonacci number

    Quote Originally Posted by SlipEternal View Post

    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    354
    Thanks
    18

    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);
    
        }
    }
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    354
    Thanks
    18

    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);
    
    
    }
        }
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Randomly chosen family
    Posted in the Advanced Statistics Forum
    Replies: 13
    Last Post: Oct 12th 2011, 11:06 AM
  2. Replies: 7
    Last Post: Jul 25th 2010, 08:26 PM
  3. Replies: 2
    Last Post: Jun 1st 2010, 03:49 AM
  4. Replies: 3
    Last Post: Jan 26th 2010, 11:08 AM
  5. probability that a randomly chosen member
    Posted in the Statistics Forum
    Replies: 1
    Last Post: Nov 2nd 2009, 03:09 PM

/mathhelpforum @mathhelpforum