# Project Euler Progress

Confidence: na
Importance: 1
Novelty: 2
Post #: 40
finished
Topics: personal, programming

Here are my solutions to some ProjectEuler.net problems for fun.

```""" Author: Evan Ward

Description: Solutions to some ProjectEuler.net problems for fun. """
from functools import reduce
import time, math

""" Problem 1: If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000. """
def prob1():
return sum(num for num in range(1000) if num%3==0 or num%5==0)
#print("Problem 1: "+str(prob1()))

def prob1a():

def arithmeticSum(start,end,step):
n = int(end/step)
a_1 = start - start%step + step
a_n = end - end%step
return n*(a_1+a_n)/2
start = 0
end = 999
return arithmeticSum(start,end,3) + arithmeticSum(start,end,5) - arithmeticSum(start,end,15)
#print("Problem 1 alternate: "+str(prob1a()))

""" #2 Each new term in the Fibonacci sequence is generated by adding the previous two terms.  By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms. """
def prob2():
total = 0
f = 1
g = 2
while f < 4000000:
if g%2 == 0:
total += g
f, g = g, f+g
#print("Problem 2: "+str(prob2()))

"""  #3 The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?  """
def prob3():
n = 600851475143
factors = []
for div in range(3,int(n**.5),2):
while n%div == 0:
factors.append(div)
n /= div
return factors[-1]
#print("Problem 3: "+str(prob3()))

""" #4 A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers. """
def prob4():
largest = 0
for x in range(999,100,-1):
y = x
while y >= 100:
candidate = x * y
if candidate < largest:
y = 0
elif str(candidate)[::-1] == str(candidate):
if candidate > largest:
largest = candidate
y = 0
else:
y -= 1
return largest
#print("Problem 4: "+str(prob4()))

""" #5  2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? """
def prob5():
def lcm(x,y):
return abs(x*y) // math.gcd(x, y)
return reduce(lambda x,y: lcm(x,y),[x for x in range(1,21)])
#print("Problem 5: "+str(prob5()))

def prob5a():
n = 19*17*13*11*7*5*3*2
m = 1
while True:
z = n*m
if z%20 == 0:
if z%18 == 0:
if z%16 == 0:
if z%14 == 0:
if z%12 == 0:
return z
m += 1
#print("Problem 5 alterate: "+str(prob5a()))

""" #6  The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385.  The square of the sum of the first ten natural numbers is,(1 + 2 + ... + 10)2 = 552 = 3025.
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.  """
def prob6():
return (101*50)**2 - sum(n**2 for n in range(101))
#print("Problem 6: "+str(prob6()))

""" #7 By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 1001st prime number? """
def sieve(n):
primes = [True]*n
primes = primes = False
for i in range(4,n,2):
primes[i] = False
for i in range(3,n,2):
if primes[i]:
for j in range(i*i,n,i):
primes[j] = False
return [i for i,v in enumerate(primes) if v==True]

def prob7():
import math
nth_Prime = 10001
n = int(math.log(nth_Prime)*nth_Prime) #use number theory insight to go to a minimal reasonable index.
while n/math.log(n) < nth_Prime:
n += 5000
return sieve(n)[nth_Prime]
#print("Problem 7: "+str(prob7()))

"""# 8  The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?"""
def prob8():
n = "".join(n.split())
max13 = 1
start = 0
while start < 987:
testNum = n[start:start+13]
product = 1
for dig in testNum:
product *= int(dig)
if product > max13:
max13 = product
start += 1
return max13
#print("Problem 8: "+str(prob8()))

""" #9 A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
"""
def prob9():
for a in range(1,500):
for b in range(a,500):
c = (a**2+b**2)**.5
if c%1 == 0:
if 1000%(a+b+c) == 0:
d = a+b+c
e = 1000/d
return int(a*b*c*e**3)
#print("Problem 9: "+str(prob3()))

""" #10 The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. """
def prob10():
return sum(p for p in sieve(2000000))
#print("Problem 10: "+str(prob10()))

"""# 11  In the 20×20 grid below, four numbers along a diagonal line have been marked in red. The product of these numbers is 26 × 63 × 78 × 14 = 1788696.
What is the greatest product of four adjacent numbers in the same direction
(up, down, left, right, or diagonally) in the 20×20 grid? """
def prob11():
grid = [8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8],[49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0],[81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65],[52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91],[22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],[24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50],[32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],[67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21],[24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],[21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95],[78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92],[16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57],[86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58],[19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40],[4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66],[88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69],[4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36],[20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16],[20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54],[1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48]
products = []
grid2=[*zip(*grid)]
for i in range(20):
for j in range(17):
products.append(reduce((lambda x,y: x*y),grid[i][j:j+4]))
products.append(reduce((lambda x,y: x*y),grid2[i][j:j+4]))
for i in range(17):
for j in range(3,20):
products.append(grid[i][j] * grid[i+1][j-1] * grid[i+2][j-2] * grid[i+3][j-3])
products.append(grid[i] * grid[i+1] * grid[i+2] * grid[i+3])
return max(products)
#print("Problem 11: "+str(prob11()))

""" #12 The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?"""
def prob12():
n = 10000 #true n is ~12375, so this isn't too unreasonable to start
while True:
t = n*(n+1)/2
if t%2 == 0:
d = 2
for num in range(2,int(t**.5)):
if t%num == 0:
d += 2
if d >= 500:
return int(t)
else:
n += 1
else:
n += 1
#print("Problem 12: "+str(prob12()))

""" #13 Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
~~huge list of numbers~~ """
def prob13():
total = sum(int(n[:11]) for n in nums)
return str(total)[:10]
#print("Problem 13: "+str(prob13()))

''' #14 The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms.
Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
'''
def prob14():
maxN = 0
maxC = 0
for a in range(999999,830000,-2): #yes, I stop the loop early to save time.
c = 0
i = a
while i !=1 :
while i%2 == 1:
i = (i*3+1)>>1
c += 2
while i%2 == 0:
i = i>>1
c += 1
if c > maxC:
maxC = c
maxN = a
return maxN
#print("Problem 14: "+str(prob14()))

''' #15 Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid? '''
def prob15():
n = 21
m = *n
for c in range(n):
m[c] = *n
for r in range(n):
m[r][n-1] = 1
for c in range(n):
m[n-1][c] = 1
for c in range(n-2,-1,-1):
for r in range(n-2,-1,-1):
m[c][r] = m[c+1][r]+m[c][r+1]
return int(m)
#print("Problem 15: "+str(prob15()))

"""#16  2**15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2**1000?"""
def prob16():
return sum(int(d) for d in str(2**1000))
#print("Problem 16: "+str(prob16()))

""" #17  If the numbers 1 to 5 are written out in words:
one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?"""
def num2word(n): #only works for 1-1000, doesn't add hyphens
word=''
ones=dict([(0,""),  (1,'one'),(2,'two'),(3,'three'),(4,'four'),(5,'five'),(6,'six'),(7,'seven'),(8,'eight'),(9,'nine'),
(10,'ten'),(11,'eleven'),(12,'twelve'),(13,'thirteen'),(14,'fourteen'),(15,'fifteen'),(16,'sixteen'),(17,'seventeen'),
(18,'eighteen'),(19,'nineteen')])
tens = dict([(20,'twenty'),(30,'thirty',),(40,'forty',),(50,'fifty'),(60,'sixty'),(70,'seventy'),(80,'eighty'),(90,'ninety')])
strN = str(n)
if len(strN) == 4:
return 'one thousand'

if len(strN)==3:
word += ones[int(strN[-3])]+' hundred'
if strN[-2] != '0' or strN[-1] != '0':
word += ' and '
strN = strN[1:]
else:
return word

if len(strN) == 2:
if int(strN[-2]) == 0:
word += ones[int(strN[-1])]
return word
if int(strN[-2]) == 1:
word += ones[10+int(strN[-1])]
return word
word += tens[int(strN[-2])*10]
if int(strN[-1]) == 0:
return word
else:
word += " "
strN = strN[1:]

if len(strN) == 1:
word += ones[int(strN[-1])]
return word

def prob17():
count = 0
for i in range(1001):
count += len(num2word(i).replace(" ",""))
return count
#print("Problem 17: "+str(prob17()))

""" #18  By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
3
7 4
2 4 6
8 5 9 3
That is, 3 + 7 + 4 + 9 = 23.
Find the maximum total from top to bottom of the triangle below:
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o) """
def prob18(): #answer is 1074. This is just an ugly monte carlo simulation,
#not guarenteed to output the right answer every time.
import random
triangle=[
,
[95,64],
[17,47,82],
[18,35,87,10],
[20,4,82,47,65],
[19,1,23,75,3,34],
[88,2,77,73,7,63,67],
[99,65,4,28,6,16,70,92],
[41,41,26,56,83,40,80,70,33],
[41,48,72,33,47,32,37,16,94,29],
[53,71,44,65,25,43,91,52,97,51,14],
[70,11,33,28,77,73,17,78,39,68,17,57],
[91,71,52,38,17,14,91,43,58,50,27,29,48],
[63,66,4,68,89,53,67,30,73,16,69,87,40,31],
[4,62,98,27,23,9,70,98,73,93,38,53,60,4,23]]
sums = []
for _ in range(10000):
i = 14
j = random.randint(0,14)
total = 0
while i > -1:
total += triangle[i][j]
i -= 1
j = j + random.randint(-1,0)
if j > i or j < 0:
j = i
sums.append(total)
return max(sums)
#print("Problem 18: "+str(prob18()))

""" #19  You are given the following information, but you may prefer to do some research for yourself.
1 Jan 1900 was a Monday.
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)? """
def prob19():
def sunday(day):
return day%7 == 6 #week starts on a monday
SundaysOnFirst = 0
day = 365%7 #we know 1 Jan 1900 was a Monday. One year later is 365%7
for year in range(1901,2001):
leapYear = False
if year%4 == 0:
leapYear = True
if year%100 == 0:
leapYear = False
if year%400 == 0:
leapYear = True
if leapYear == True:
months = [(1,31),(2,29),(3,31),(4,30),(5,31),(6,30),(7,31),(8,31),(9,30),(10,31),(11,30),(12,31)]
else:
months = [(1,31),(2,28),(3,31),(4,30),(5,31),(6,30),(7,31),(8,31),(9,30),(10,31),(11,30),(12,31)]
for month in months:
SundaysOnFirst += sunday(day)
day = (day+month)%7
return SundaysOnFirst
#print("Problem 19: "+str(prob19()))

""" #20  n! means n × (n − 1) × ... × 3 × 2 × 1
For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.
Find the sum of the digits in the number 100! """
def prob20():
n = reduce(lambda x,y:x*y,range(1,101))
return sum(int(d) for d in str(n))
#print("Problem 20: "+str(prob20()))

""" #21  Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000. """
def prob21():
def d(n):
total = 1
for i in range(2,int(n/2+1)):
if n%i == 0:
total += i
amicables = 0
for a in range(2,10000):
b = d(a)
if a != b and a == d(b):
amicables += a
return amicables
#print("Problem 21: "+str(prob21()))

""" #22 Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name,
multiply this value by its alphabetical position in the list to obtain a name score.
For example, when the list is sorted into alphabetical order,
COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file? """
def prob22():
names.sort()
score = dict([(v,i+1) for i,v in enumerate("ABCDEFGHIJKLMNOPQRSTUVWXYZ")])
total = 0
for i,name in enumerate(names):
total += (i+1)*sum(score[L] for L in name)
#print("Problem 22: "+str(prob22()))

"""#46 It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12
It turns out that the conjecture was false. What is the smallest odd composite that cannot be written as the sum of a prime and twice a square? """
def prob46():
L = 10000
P = set(sieve(L))
SQR = [2*i*i for i in range(1,int(L**.5)) if 2*i*i<L]
OC = [i for i in range(3,L,2) if i not in P]
while True:
for z in range(1,len(OC)):
c = 0
while OC[z]-SQR[c] not in P:
c += 1
if c >= len(SQR):
return OC[z]
#print("Problem 46: "+str(prob46()))

""" #47 https://projecteuler.net/problem=47 The first two consecutive numbers to have two distinct prime factors are:
14 = 2 × 7
15 = 3 × 5
The first three consecutive numbers to have three distinct prime factors are:
644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.
Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers? """
def prob47():
def factor(n):
factors = set()
for i in [2,3,5,7]:
if n%i == 0:
n /= i
while n%i == 0:
n /= i
if n == 1:
return len(factors)
lim = int(n)
for i in range(11,lim,6):
if n%i == 0:
n /= i
while n%i == 0:
n /= i
j = i+2
if n%j == 0:
n /= j
while n%j == 0:
n /= j
if n==1: return len(factors)
return len(factors)
i = 134000 #starts high to save time.  This isn't the fastest algorithm.
count = 0
while True:
while factor(i) == 4 and count < 4:
i += 1
count += 1
if count == 4: return i-4
else:
count = 0
i += 1
#print("Problem 47: "+str(prob47()))

""" #48 The series, 1**1 + 2**2 + 3**3 + ... + 10**10 = 10405071317. Find the last ten digits of the series, 1**1 + 2**2 + 3**3 + ... + 1000**1000."""
def prob48():
return sum((n**n)%10000000000 for n in range(1,1001))%10000000000
#print("Problem 48: "+str(prob48()))

""" #49  The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways:
(i) each of the three terms are prime, and,
(ii) each of the 4-digit numbers are permutations of one another.
There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.
What 12-digit number do you form by concatenating the three terms in this sequence? """
def largPerm(n):
nList = list(str(n))
output = ''
while len(nList)>0:
maxDig = 0
Idx = 0
for index,dig in enumerate(nList):
if int(dig)>maxDig:
maxDig = int(dig)
Idx = index
del nList[Idx]
output += str(maxDig)
return int(output)

def prob49():
primes = sieve(10000)[168:]
primeSet = set(primes)
for i in range(1061):
for j in range(i+1,1061):
if 2*primes[j]-primes[i] in primeSet:
#print(2*primes[j]-primes[i])
a,b,c = primes[i],primes[j],2*primes[j]-primes[i]
if largPerm(a) == largPerm(b) and largPerm(b) == largPerm(c):
if a != 1487:
return int(str(a)+str(b)+str(c))
#print("Problem 49: "+str(prob49()))

""" #50  The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?"""
def prob50():
L = 1000000
stop = 550 #sum(i for i in primes[:550])==1013507
primes = sieve(L)
primeSet = set(primes)
primeConsecDict = dict() #prime num, number of primes summed into it
i = 0
while i < stop:
j = i
primeConsecSum = primes[j]
while primeConsecSum < 1000000:
j += 1
primeConsecSum += primes[j]
if primeConsecSum < 1000000 and primeConsecSum in primeSet:
if primeConsecSum in primeConsecDict:
if j-i > primeConsecDict[primeConsecSum]:
primeConsecDict[primeConsecSum] = j-i
else:
primeConsecDict[primeConsecSum] = j-i
i += 1
return sorted([(k,v) for k,v in primeConsecDict.items()],key=lambda tup: tup)[-1]
#print("Problem 50: "+str(prob50()))

""" #56 A googol (10**100) is a massive number: one followed by one-hundred zeros; 100**100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.
Considering natural numbers of the form, a**b, where a, b < 100, what is the maximum digital sum? """
def prob56():
maxSum = 0
for a in range(50,100,-1): #start higher to save time and it's reasonable
for b in range(50,100,-1):
c = a**b
digSum = 0
for dig in str(c):
digSum += int(dig)
if digSum > maxSum:
maxSum = digSum
return maxSum
#print("Problem 56: "+str(prob56()))

""" #62 The cube, 41063625 (345**3), can be permuted to produce two other cubes: 56623104 (384**3) and 66430125 (405**3). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.
Find the smallest cube for which exactly five permutations of its digits are cube. """
def largestPerm(n):
nList = list(str(n))
output = ''
while len(nList)>0:
maxDig = 0
Idx = 0
for index,dig in enumerate(nList):
if int(dig) > maxDig:
maxDig = int(dig)
Idx = index
del nList[Idx]
output += str(maxDig)
return int(output)

def prob62():
lim = 10000
cubeDict = dict()
for i in range(1,lim):
i3 = i**3
largePerm = largestPerm(i3)
if largePerm in cubeDict:
cubeDict[largePerm] += [i]
if len(cubeDict[largePerm]) == 5:
return min(cubeDict[largePerm])**3
else:
cubeDict[largePerm] = [i]
#print("Problem 62: "+str(prob62()))

"""#63 The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power.
How many n-digit positive integers exist which are also an nth power? """
def prob63():
count = 0
for power in range(1,22):
for num in range(1,11):
if len(str(num**power)) == power:
count += 1
return count
#print("Problem 63: "+str(prob63()))

""" #66 Consider quadratic Diophantine equations of the form:
x2 – Dy2 = 1
For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1.
It can be assumed that there are no solutions in positive integers when D is square.
By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:
32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1
Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.
Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.
"""
"""
def prob66(): #not efficient enough yet to solve in reasonable time
maxX=0
maxD=0
for d in range(1,1001):
lim=int(d**.5)
if lim*lim!=d:
x=2
y=1
while x*x - 1 != d*y*y:
if y+1 < x:
y+=1
else:
x+=1
y=1
if x > maxX:
maxX=x
maxD=d
return maxD
print("Problem 66: "+str(prob66()))
"""

""" #75 It turns out that 12 cm is the smallest length of wire that can be bent to form
an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle,
and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form
exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1500000 can exactly one integer sided right
angle triangle be formed? """
def prob75():
lim = 1500000
sums = dict()
for m in range(1,867): #math for finding pythagorean triple sums at https://www.mathsisfun.com/numbers/pythagorean-triples.html
for n in range(m+1,867):
if (m+n)%2 == 1:
pSum = 2*n*n + 2*n*m
if pSum < lim:
a,b = m,n
while b:
a,b = b,a%b
if a == 1:
k = 1
while pSum*k < lim:
if pSum*k in sums:
sums[pSum*k] += 1
else:
sums[pSum*k] = 1
k += 1
count = 0
for key,val in sums.items():
if val == 1:
count += 1
return count
#print("Problem 75: "+str(prob75()))

""" #80 It is well known that if the square root of a natural number is not an integer, then it is irrational.
The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred
decimal digits for all the irrational square roots. """
from decimal import*
def prob80():
getcontext().prec = 100
total = 0
for i in range(2,101):
j = int(i**.5)
if j*j != i:
k = str(Decimal(i).sqrt())[2:]
for dig in k:
total += int(dig)
#print("Problem 80: "+str(prob80()))

"""
# 94 It is easily proved that no equilateral triangle exists with integral length sides and integral area.
However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal
and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths
and area and whose perimeters do not exceed one billion (1,000,000,000).
"""
def prob94(): #still to slow, I'd have to use more math to really get faster.
lim = 3333333
uniques = []#[16, 50, 196, 722, 10082, 37636, 94361512]
triangles = [] #tuples of sides
L = len(uniques)
for s in range(5,lim): #low= a,a,a+1  high= a,a+1,a+1
if s%2 == 1:
Lpossible = True
Rpossible = False
else:
Lpossible = False
Rpossible = True
i = 0
if Lpossible:
pL = s*3+1
while i < L:
if pL%uniques[i] == 0:
i = L
Lpossible = False
i += 1
if Lpossible:
p5 = pL*.5
areaL = int(p5*(p5-s)*(p5-s)*(p5-s-1))
sqrtAreaL = math.isqrt(areaL)
if sqrtAreaL*sqrtAreaL == areaL:
uniques.append(pL)
triangles.append((s,s,s+1))
L += 1
if Rpossible:
pR = s*3+2
while i < L:
if pR%uniques[i] == 0:
i = L
Rpossible = False
i += 1
if Rpossible:
p5 = pR*.5
areaR = int(p5*(p5-s)*(p5-s-1)*(p5-s-1))
sqrtAreaR = math.isqrt(areaR)
if sqrtAreaR*sqrtAreaR == areaR:
uniques.append(pR)
triangles.append((s,s+1,s+1))
L += 1
total = 0
for p in uniques:
n = int((lim-p)/p)
total += n*(n*p+p)*.5
#print(uniques)
#print(triangles)
#prob94()
#print("Problem 94: "+str(prob94()))

""" #97 The first known prime found to exceed one million digits was discovered in 1999,
and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits.
Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1.

Find the last ten digits of this prime number. """
def prob97():
a = 2
for b in range(7830456):
a = (2*a)%10000000000
return (a*28433+1)%10000000000
#print("Problem 97: "+str(prob97()))

""" # 607 Frodo and Sam need to travel 100 leagues due East from point A to point B.
On normal terrain, they can cover 10 leagues per day,
and so the journey would take 10 days. However, their path is crossed by a long marsh
which runs exactly South-West to North-East, and walking through the marsh will
slow them down. The marsh is 50 leagues wide at all points, and the mid-point
of AB is located in the middle of the marsh. A map of the region is shown in
the diagram below:
~~diagram~~
The marsh consists of 5 distinct regions, each 10 leagues across,
as shown by the shading in the map. The strip closest to point A is relatively light marsh,
and can be crossed at a speed of 9 leagues per day. However, each strip becomes progressively
harder to navigate, the speeds going down to 8, 7, 6 and finally 5 leagues per day for
the final region of marsh, before it ends and the terrain becomes easier again,
with the speed going back to 10 leagues per day.

If Frodo and Sam were to head directly East for point B, they would travel exactly 100 leagues,
and the journey would take approximately 13.4738 days. However, this time can be shortened
if they deviate from the direct path.

Find the shortest possible time required to travel from point A to B, and give your
answer in days, rounded to 10 decimal places.
"""

def prob607():
import math
acoord = (0,0)
bcoord = (70.71067811865476,70.71067811865476)
xs = [0,10.355339059327378,10,10,10,10,10,10.355339059327378]
ys = [0,17.67766952966369,24.748737341529164,31.81980515339464,38.890872965260115,
45.96194077712559,53.033008588991066,70.71067811865476]
ysfloor = [0,17.67766952966369,24.748737341529164,31.81980515339464,38.890872965260115,
45.96194077712559,53.033008588991066,70.71067811865476]
speed = [0,10,9,8,7,6,5,10]
def travelTime(ys):
time = 0
for i in range(1,7):
time += math.sqrt((xs[i]-xs[i-1])**2+(ys[i]-ys[i-1])**2)/speed[i]
return time
#ys[i]-ys[i-1] < ys[i-1]-ys[i-2] for the marsh
minTime = 12.193987628259908
i = 0
# while ys[i] < ys[i+1] and ys[i]>ysfloor[i]:
print(travelTime(ys))
#print("Problem 607: "+str(prob607()))

def main():
import time
totalTime = time.time()
problems = [1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,21,22,
46,47,48,49,50,56,62,63,75,80,97]
for problem in problems:
t = time.time()
solution = eval("prob"+str(problem)+"()")
t = time.time()-t
print("Problem "+str(problem)+": "+str(solution),t)
print('Total time:',time.time()-totalTime,'for',len(problems),'problems')
main()

```