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.
~~~

Source: codewars | Difficulty: EASY

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]:
				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


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

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]]
	(a, b) = (1, 1)
	for i in range(n - 1):
		(a, b) = (b, a + b)
	fib_list = list(str(a))
	i = 0
	while i < len(fib_list):
		numCount[int(fib_list[i])][0] += 1
		i += 1
	i = 0
	while i < len(numCount):
		numCount[i] = tuple(numCount[i])
		if numCount[i][0] == 0:
			numCount.pop(i)
		else:
			i += 1
	return sorted(numCount, key=lambda x: (x[0], x[1]), reverse=True)


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()])))