Fibonacci numbers are generated by setting F0 = 0, F1 = 1, and then using the formula:

# Fn = Fn-1 + Fn-2

Your task is to efficiently calculate the **n**th element in the Fibonacci sequence and then count the occurrence of each digit in the number. Return a list of integer pairs sorted in **descending** order.

10 ≤ n ≤ 100000

## Examples
```
f(10) = 55  # returns [(2, 5)], as there are two occurances of digit 5

f(10000)    # returns:
  [(254, 3),
   (228, 2),
   (217, 6),
   (217, 0),
   (202, 5),
   (199, 1),
   (198, 7),
   (197, 8),
   (194, 4),
   (184, 9)]
```
If two integers have the same count, sort them in descending order.

Your algorithm must be efficient.

~~~if:javascript
Solving this Kata in Javascript requires the use of the bignumber.js library. I have included starter code to assist you with using the library. Thanks to `kazk` for assisting with the translation.
~~~

Difficulty: introductory

Starter code:

def fib_digits(n):
	

Solutions:
from collections import Counter

def fib_digits(n):
    a, b = 0, 1
    for i in range(n): a, b = b, a+b
    return sorted(((b, int(a)) for a, b in Counter(str(a)).items()), reverse=True)

from operator import itemgetter
def fib_digits(n):
    a,b = 1,1
    num=n
    num_int=int(num-2)
    for i in range (num_int):
        a,b=b,a+b
    print(b)
    num = b
    print(num)
    lst = list(map(int,str(num)))
    lst2 = []
    p = False
    i = 1
    lst2.append([1,lst[0]])
    while i < len(lst):
        d = 0
        while d < len(lst2):
            if lst[i] == lst2[d][1]:
                #lst2[d][0] += 1
                p = True
                break
            d+=1
        if p == True:
            lst2[d][0] += 1
        else:
            lst2.append([1,lst[i]])   
        i+=1
        p = False
    print(lst2)
    i = 0
    while i < len(lst2):
        lst2[i] = tuple(lst2[i])
        i+=1
    return(sorted((lst2), reverse=True))
            
            
                


from collections import Counter

def fib_digits(n):
    a = 0
    b = 1
    
    for i in range(2, n + 1):
        a, b = b, a + b
    
    c = Counter(str(b))
    res = sorted([(int(x[0]), int(x[1])) for x in zip(list(c.values()), list(c.keys()))], key = lambda m: (m[0], m[1]))[::-1]
    return res


from collections import Counter


def fib_digits(n):
    a,b = 0,1
    for i in range(n-1):
        a,b = b, a+b
    counts = Counter(str(b))
    return sorted(((count, int(digit)) for digit, count in counts.items()), reverse=True)

def fib_digits(n):
    d = str(fib(n))
    return sorted([(d.count(i), int(i)) for i in '0123456789' if d.count(i) > 0])[::-1]


def fib(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a



from collections import Counter

# https://stackoverflow.com/a/23462371
def fib(n):
    v1, v2, v3 = 1, 1, 0
    for rec in bin(n)[3:]:
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1': v1, v2, v3 = v1+v2, v1, v2
    return v2

def fib_digits(n):
    return sorted(((v, int(k)) for k,v in Counter(str(fib(n))).items()), reverse=True)

def fib(n1):
    fn_1=1
    fn_2=0
    f=0
    for i in range(1,n1):
        f=fn_1+fn_2
        fn_2=fn_1
        fn_1=f
    return f
    
def fib_digits(n):
    check=0
    num=''
    l=[]
    count=0
    x=str(fib(int(n)))
    while len(x)>1:
        for j in range(len(x)):
            if x[0]==x[j]:
                count+=1
        num+=x[0]
        l.append((count,int(x[0])))
        count=0
        x=x.replace(x[0],"")
    l.sort()
    return(l[::-1])

def fast_fib(n):
    def pos(n):
        if n == 0:
            return (0, 1)
        else:
            a, b = pos(n // 2)
            c = a * (b * 2 - a)
            d = a * a + b * b
            if n % 2 == 0:
                return (c, d)
            else:
                return (d, c + d)
    
    def fib(n):
        if n >= 0:
            return pos(n)[0]
    
        if n < 0:
            sign = -1 if n % 2 == 0 else 1
            return sign*pos(abs(n))[0]
    
    return fib(n)

def fib_digits(n):
    from collections import Counter
    cnt = Counter(str(fast_fib(n)))
    ret = [(v, int(k)) for k, v in cnt.items()]
    ret = sorted(ret, key=lambda x: (-x[0], -x[1]))
    
    return ret

def fib_digits(n):
    numCount = [[0,0], [0,1], [0,2], [0,3], [0,4], [0,5], [0,6], [0,7], [0,8], [0,9]] # 2d array of the amounts of each number
    a,b = 1,1
    for i in range(n-1): # calculate the fibonacci number of the entered digit
      a,b = b,a+b
    fib_list = list(str(a)) # create a list of the numbers (in string form), one number per item
    i = 0
    while i < len(fib_list):
      numCount[int(fib_list[i])][0] += 1 # if number is x, the number of x's is incremented
      i+=1
    i = 0
    while i < len(numCount):
      numCount[i] = tuple(numCount[i]) # convert each list item to tuple
      if numCount[i][0] == 0:
        numCount.pop(i) # if there aren't any of a specific number, remove it
      else:
        i+=1
    return sorted(numCount, key=lambda x: (x[0], x[1]), reverse=True) # return the sorted list

from collections import Counter
def fib_digits(n):
        first = 0
        second = 1
        for i in range(n-1):
            update = first+second
            first = second
            second = update
        return list(reversed(sorted([(v,k) for k,v in Counter([int(y) for y in str(update)]).items()])))