import itertools as it
def lexicographicPermutations():
	l=list(range(10))
	r=[''.join(map(str,x)) for x in list(it.permutations(l))]
	#print(len(r))
	print("Millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9: "+r[999999])
lexicographicPermutations()

"""
Explanation: Problem 24
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012   021   102   120   201   210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
End of explanation
"""


def fibonacciSequence():
	old=1
	current=1
	new=0
	i=2
	while True:
		i+=1
		new=old+current
		if checkLength(new):
			break
		old=current
		current=new
	return i

def checkLength(n):
	if len(str(n))==1000:
		return True
	else:
		return False

print("Index of the first term in the Fibonacci sequence to contain 1000 digits: "+str(fibonacciSequence()))

"""
Explanation: Problem 25
The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
End of explanation
"""


def cycleLength(n):
	res = 10
	j = 0
	while res != 10 or j < 1:
		res = (res % n) * 10
		j += 1
	return j

def Euler26():
	long = 0
	for i in range(2, 1000):
		if i%2 != 0 and i%5 != 0:
			length = cycleLength(i)
			if length > long:
				long = length
				res = i
	return res

print(Euler26())

"""
Explanation: Problem 26
A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:
1/2 =   0.5
1/3 =   0.(3)
1/4 =   0.25
1/5 =   0.2
1/6 =   0.1(6)
1/7 =   0.(142857)
1/8 =   0.125
1/9 =   0.(1)
1/10    =   0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.
Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
End of explanation
"""


