# Project Euler 100
Write-ups on the first 100 Project Euler problems.
I do not want to break policy, so I am only publicly posting the first 100.
# Euler 0001
### The Problem:
Listing all multiples of 3 and 5 under 1000.
**Given:** 3,5,6,9 are all multiples of 3 and 5 below 10.
### Considerations:
We could iterate through every multiple of these numbers but there is going to be overlap when their multiples are divisible by both of them. Such examples would be 15 or 30. In these cases we don't want to add these numbers to the totals twice. This is what we need to watch out for in the code.
### The Approach:
1. Keep iterating through all the multiples of 3 and 5
2. Add each number to a set, or a list with a not in conditional
3. Sum the set or list
### The Code:
```python
target_under = 1000
multiples = [3,5]
found = []
#go through each of our multiples
for multiple in multiples:
#set the running total equal to the first multiple
running_total = multiple
#keep incrementing until we go over the target, then go to the next multiple
while running_total < target_under:
#add the running total to the list if it is not already in it.
if running_total not in found:
found += [running_total]
running_total += multiple
```
- We need to generate the Fibonacci sequence up to 4,000,000.
- We only need to keep every other number in the sequence.
### Considerations:
Time-space considerations and decisions to be made:
- We could choose to store 0 numbers and recursively generate all numbers up to 4,000,000.
- This spends both a lot of time although it doesn't use a large permanent space.
- We could generate all of the Fib. numbers up to 4,000,000 and store them in a list, good for referencing later, and will reduce redundancy.
- We could keep only the last 2 Fib. numbers and keep dropping the last one when we get a new one.
### The Code:
```python
fib_1 = 1
fib_2 = 2
limit = 4000000
#running total set to 2 because it is odd
running_total = 2
#keep going until fib_1 and fib_2 totaled > limit
while fib_1 + fib_2 < limit:
fib = fib_1 + fib_2
fib_1 = fib_2
fib_2 = fib
#add to the running total if it is even.
if fib % 2 == 0:
running_total += fib
```
```python
upper_limit = 6009515658416
#upper_limit = 20023110541 #, good to use to double check. Is 2 [2,2],3,167
current_upper_limit = upper_limit
prime_factors = []
#we are going to hardcode 2 and 3 for looping sake
if upper_limit % 2 == 0:
while current_upper_limit % 2 == 0:
current_upper_limit = current_upper_limit/2
prime_factors += [2]
if upper_limit % 3 == 0:
while current_upper_limit % 3 == 0:
current_upper_limit = current_upper_limit/3
prime_factors += [3]
current = 6
#go up to the upper limit of numbers, add 2 for edge case (I'm not sure that part is correct)
while current < current_upper_limit + 2:
#print(prime_factors, current_upper_limit)
#print(prime_factors, current_upper_limit)
#check the numbers before and after the increment of 6
#add them to the prime factors as many times as necessary
#keep dividing the new number to use.
if current_upper_limit % (current - 1) == 0:
while current_upper_limit % (current - 1) == 0:
current_upper_limit = current_upper_limit/(current-1)
prime_factors += [current-1]
if current_upper_limit % (current + 1) == 0:
while current_upper_limit % (current + 1) == 0:
current_upper_limit = current_upper_limit/(current+1)
prime_factors += [current+1]
current += 6
print(prime_factors)
```
```python
import math
upper_limit = 600951565841652
#upper_limit = 20023110541 #, good to use to double check. Is [2,2,3,167]
current_upper_limit = upper_limit
sqrt_limit = math.sqrt(upper_limit)
prime_factors = []
#we are going to hardcode 2 and 3 for looping sake
if upper_limit % 2 == 0:
while current_upper_limit % 2 == 0:
current_upper_limit = current_upper_limit/2
prime_factors += [2]
if upper_limit % 3 == 0:
while current_upper_limit % 3 == 0:
current_upper_limit = current_upper_limit/3
prime_factors += [3]
current = 6
#go up to the square root
while current < sqrt_limit:
#print(prime_factors, current_upper_limit)
#check the numbers before and after the increment of 6
#add them to the prime factors as many times as necessary
#keep dividing the new number to use.
if current_upper_limit % (current - 1) == 0:
while current_upper_limit % (current - 1) == 0:
current_upper_limit = current_upper_limit/(current-1)
prime_factors += [current-1]
if current_upper_limit % (current + 1) == 0:
while current_upper_limit % (current + 1) == 0:
current_upper_limit = current_upper_limit/(current+1)
prime_factors += [current+1]
current += 6
#if we looped beyond the square root limit and the number
#we are left with isn't 1, then it is the final prime factor.
if current_upper_limit != 1:
prime_factors += [current_upper_limit]
print(prime_factors)
```
```python
largest_palindrome = 0
def palindrome(number):
return str(number) == str(number)[::-1]
for i in range(1000,1,-1):
for j in range(1000,1,-1):
if palindrome(i*j) and i*j > largest_palindrome:
largest_palindrome = i*j
print(largest_palindrome)
```
```python
import math
smallest_multiple = []
upper_limit = 20
def prime_factors(upper_limit):
#upper_limit = 20023110541 #, good to use to double check. Is [2,2,3,167]
current_upper_limit = upper_limit
sqrt_limit = math.sqrt(upper_limit)
prime_factors = []
#we are going to hardcode 2 and 3 for looping sake
if upper_limit % 2 == 0:
while current_upper_limit % 2 == 0:
current_upper_limit = current_upper_limit/2
prime_factors += [2]
if upper_limit % 3 == 0:
while current_upper_limit % 3 == 0:
current_upper_limit = current_upper_limit/3
prime_factors += [3]
current = 6
while current < sqrt_limit:
#print(prime_factors, current_upper_limit)
if current_upper_limit % (current - 1) == 0:
while current_upper_limit % (current - 1) == 0:
current_upper_limit = current_upper_limit/(current-1)
prime_factors += [current-1]
if current_upper_limit % (current + 1) == 0:
while current_upper_limit % (current + 1) == 0:
current_upper_limit = current_upper_limit/(current+1)
prime_factors += [current+1]
current += 6
if current_upper_limit != 1:
prime_factors += [current_upper_limit]
return prime_factors
#start from 2 and go to the number we want to find
for i in range(2,upper_limit + 1,1):
current_pf = prime_factors(i)
new_smallest_multiple = []
#look at all of the numbers between our current set and what we just factorized
for number in set(smallest_multiple).union(set(current_pf)):
#add that many prime factors to the current smallest multiple
for j in range(max(smallest_multiple.count(number),current_pf.count(number))):
new_smallest_multiple += [number]
smallest_multiple = new_smallest_multiple
print(smallest_multiple)
print(math.prod(smallest_multiple))
```
Which means that the final formula is (n(n+1)/2)^2 - n(n+1)(2n+1)/6
Which by hand:
\- (100(101)/2)^2 - 100(101)(201)/6
\- 25502500 - 338350
\- 25164150
```python
prime_count = 10001
prime_factors = [2,3] #we can just start with 2 and 3, because we already know them
#simple prime checker
def add_if_prime(number, primes):
is_prime = True
#check through all the primes we have gathered so far.
for prime in primes:
if number % prime == 0:
is_prime = False
break
if is_prime:
primes += [number]
return primes
#actual loop to iterate through
current = 6
while len(prime_factors) < prime_count:
add_if_prime(current-1, prime_factors) #check the number before
add_if_prime(current+1, prime_factors) #check the number after
current += 6 #loop through incrementing by 6
print(prime_factors[prime_count-1])
```
```python
import math
large_number = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
window_size = 13
best_index = 0
best_index_value = math.prod([int(x) for x in large_number[0:window_size]])
for i in range(1,len(large_number) - window_size):
if int(large_number[i-1]) < int(large_number[i+window_size-1]):
current_value = math.prod([int(x) for x in large_number[i:i+window_size]])
if current_value > best_index_value:
best_index_value = current_value
best_index = i
print("newly found at ", best_index, best_index_value)
print(large_number[best_index:best_index+window_size])
```
```python
import math
number_to_find = 1000
a = 0
b = 0
c = 0
#we will never reach the end, but it to prevent it from going infinite
for i in range(1,number_to_find):
for j in range(i,number_to_find): #we can start from i because we technically already calculated the reverse of the pair
c = math.sqrt(i**2 + j**2)
if int(c) == c: #if it is actually an integer, we will continue
if i + j + c > number_to_find:
break
elif i + j + int(c) == number_to_find:
a = i
b = j
break #don't forget this break, it's crucial, lol
if a != 0: #we can break out if we found the triple
break
print(a,b,c)
print(a+b+c)
print(a*b*c)
print(a**2+b**2, c**2)
```
```python
prime_threshold = 2000000
number_list = list(range(2, prime_threshold+1)) #initiating the sieve. Lot's of space here on startup being used
prime_list = []
current = 0
total_iteration = 0
while current < len(number_list): #while we haven't iterated through the whole sieve yet
if number_list[current] != -1: #find the next number that isn't marked
prime = number_list[current]
prime_list += [prime] #add it to our prime list, because it is prime.
increment = current + prime
while increment < len(number_list): #and go through the rest of the sieve marking numbers with it
number_list[increment] = -1
increment += prime
total_iteration += 1
current += 1
print(len(prime_list)) #look at the length of the prime list, this is the number of primes under prime_threshold
print(total_iteration) #the amount of iterations that we made, much better than recalculating primes for each number
print(sum(prime_list)) #the answer
```
```python
import numpy
from enum import Enum
class Direction(Enum): #not necessary to the solution, but helps me as a human visualize where the solution is at
DOWN = "DOWN"
RIGHT = "RIGHT"
LEFT_DIAG = "LEFT_DIAG"
RIGHT_DIAG = "RIGHT_DIAG"
best_index = [0,0]
best_dir = Direction.DOWN
best_product = 0
length = 4
grid = numpy.genfromtxt("numbers", delimiter=" ") #using numpy to read in the file to a grid for us
for i in range(len(grid)): #go through every row in the grid
for j in range(len(grid[i])): #go through every column in the grid
#print(i,j)
#check right
if j < len(grid)-(length-1):
current_prod = 1
for k in range(length):
current_prod *= grid[i,j+k]
if current_prod >= best_product:
best_index = [i,j]
best_dir = Direction.RIGHT
best_product = current_prod
#check down
if i < len(grid)-(length-1):
current_prod = 1
for k in range(length):
current_prod *= grid[i+k,j]
if current_prod >= best_product:
best_index = [i,j]
best_dir = Direction.DOWN
best_product = current_prod
#check down right
if i < len(grid)-(length-1) and j < len(grid)-(length-1):
current_prod = 1
for k in range(length):
current_prod *= grid[i+k,j+k]
if current_prod >= best_product:
best_index = [i,j]
best_dir = Direction.RIGHT_DIAG
best_product = current_prod
#check down left
if i < len(grid)-(length-1) and j > (length-1):
current_prod = 1
for k in range(length):
current_prod *= grid[i+k,j-k]
if current_prod >= best_product:
best_index = [i,j]
best_dir = Direction.LEFT_DIAG
best_product = current_prod
print(best_index, best_dir, best_product) #prints out the best position, the direction it points, and the product
```
```python
import math
#This is a modification of the prime factor finder
def calculate_divisors(number):
upper_limit = number
current_upper_limit = upper_limit
sqrt_limit = math.sqrt(upper_limit)
current_divisors = 1
#we are going to hardcode 2 and 3 for looping sake
if upper_limit % 2 == 0:
current_div = 1
while current_upper_limit % 2 == 0:
current_upper_limit = current_upper_limit/2
current_div += 1
current_divisors *= current_div
if upper_limit % 3 == 0:
current_div = 1
while current_upper_limit % 3 == 0:
current_upper_limit = current_upper_limit/3
current_div += 1
current_divisors *= current_div
current = 6
while current < sqrt_limit:
#print(prime_factors, current_upper_limit)
if current_upper_limit % (current - 1) == 0:
current_div = 1
while current_upper_limit % (current - 1) == 0:
current_upper_limit = current_upper_limit/(current-1)
current_div += 1
current_divisors *= current_div
if current_upper_limit % (current + 1) == 0:
current_div = 1
while current_upper_limit % (current + 1) == 0:
current_upper_limit = current_upper_limit/(current+1)
current_div += 1
current_divisors *= current_div
current += 6
return current_divisors
bailout = 100000 #keep checking up to a bailout number
triangle = 1
for i in range(2,bailout):
triangle += i
if calculate_divisors(triangle) >= 500:
break
print(i, triangle)
```
```python
numbers_file = open("numbers.txt", "r")
total = 0
for number in numbers_file:
total += int(number)
print(str(total)[:10])
```
```python
highest_starting = 1000000
lengths_dict = {1:1}
max_length = 1
length_key = 1
#the recursive function to generate collatz.
#Base case is satisfied by the lengths_dict above already having 1 initialized.
def update_lengths(number, lengths):
#print(number)
if lengths.get(number) == None:
if number % 2 == 0:
one_down = number/2
else:
one_down = number*3 + 1
lengths = update_lengths(one_down, lengths)
lengths[number] = lengths[one_down] + 1
return lengths
for i in range(1,highest_starting + 1):
if lengths_dict.get(i) == None:
lengths_dict = update_lengths(i, lengths_dict)
if lengths_dict.get(i) > max_length:
length_key = i
max_length = lengths_dict.get(i)
print(length_key, max_length)
```
```python
pascal_rows = 41
def generate_pascals_last_row(rows):
last_row = [1]
#we have already generated row 1
for i in range(rows-1):
#take the first number (hint, it's 1)
current_row = [1]
#add up all the numbers and put them in between
for j in range(0, len(last_row) - 1):
current_row += [last_row[j] + last_row[j+1]]
#take the last number (hint, it's 1)
current_row += [1]
last_row = current_row
return last_row
print(max(generate_pascals_last_row(pascal_rows)))
```
```python
power = 1000
number = 2**power
total_sum = 0
for digit in str(number):
total_sum += int(digit)
print(total_sum)
```
```python
number_dict = {1:3,2:3,3:5,4:4,5:4,6:3,7:5,8:5,9:4,10:3,11:6,12:6,13:8,14:8,15:7,16:7,17:9,18:8,19:8,20:6,30:6,40:5,50:5,60:5,70:7,80:6,90:6}
number_end = 1000
total_sum = 0
for i in range(1,number_end + 1):
construction = ""
hundred = False
if int(i / 1000) > 0:
total_sum += number_dict[int(i / 1000)] #thousands place number
#print(i,int(i / 1000))
total_sum += 8 #the word thousand
if int((i % 1000) / 100) > 0:
#print(i,int((i % 1000) / 100))
total_sum += number_dict[int((i % 1000) / 100)] #hundreds place number
total_sum += 7 #the word hundred
hundred = True
construction += str(int((i % 1000) / 100)) + "hundred"
if int((i % 100)) > 0:
tens = int((i % 100)/10)*10
ones = int((i % 100))
ones_true = int(i%10)
if hundred:
construction += " and "
total_sum += 3 #the word and
if tens >= 20: #numbers greater than 20
construction += str(tens)
total_sum += number_dict[tens]
if ones > 9 and tens < 20: #10 through 19
construction += str(ones)
total_sum += number_dict[ones]
if ones_true > 0 and (ones < 10 or ones > 19): #ten through 19 are weird
construction += str(ones_true)
total_sum += number_dict[ones_true]
#print(construction)
print(total_sum)
```
```python
triangle_file = open("triangle", "r")
class Node:
def __init__(self, value):
self.l_node = None
self.r_node = None
self.value = value
self.l_sum = -1
self.r_sum = -1
self.best = -1
#not necessarily the prettiest way to construct a tree... but oh well.
#there is a lot by reference here.
top_triangle = int(triangle_file.readline())
triangle_tree = Node(top_triangle)
past_line = [triangle_tree]
for line in triangle_file:
current_line = [Node(int(x)) for x in line.split()]
for i in range(len(past_line)):
past_line[i].l_node = current_line[i]
past_line[i].r_node = current_line[i+1]
past_line = current_line
#make a function to populate the sums
def pop_sums(node : Node):
if node.l_node is None:
node.l_sum = node.value
node.r_sum = node.value
node.best = node.value
else:
#make sure both below are populated
if node.l_node.best == -1:
pop_sums(node.l_node)
if node.r_node.best == -1:
pop_sums(node.r_node)
node.l_sum = node.l_node.best + node.value
node.r_sum = node.r_node.best + node.value
node.best = node.l_sum if node.l_sum > node.r_sum else node.r_sum
pop_sums(triangle_tree)
print(triangle_tree.best)
```
```python
import calendar
year = 1901
end_year = 2000
sunday_first_days = 0
for i in range(year, end_year + 1):
this_year = calendar.Calendar().yeardayscalendar(i,12)
for year in this_year:
for month in year:
for week in month:
if week[6] == 1:
sunday_first_days += 1
print(sunday_first_days)
```
```python
import math
factorial = 100
number = sum([int(x) for x in str(math.factorial(factorial))])
print(number)
```
```python
import math
#generating the primes beforehand is incredibly helpful, since we really don't need to re-brute force these
def generate_primes(upper):
prime_threshold = upper
number_list = list(range(2, prime_threshold+1))
prime_list = []
current = 0
total_iteration = 0
while current < len(number_list):
if number_list[current] != -1:
prime = number_list[current]
prime_list += [prime]
increment = current + prime
while increment < len(number_list):
number_list[increment] = -1
increment += prime
total_iteration += 1
#print(number_list)
#print(prime_list)
current += 1
return prime_list
def divisor_finder(number, primes):
upper_limit = number
#upper_limit = 20023110541 #, good to use to double check. Is [2,2,3,167]
current_upper_limit = upper_limit
sqrt_limit = math.sqrt(upper_limit)
prime_factors = []
#we are going to hardcode 2 and 3 for looping sake
i = 0
while primes[i] < sqrt_limit and i < len(primes):
while current_upper_limit % primes[i] == 0:
current_upper_limit = current_upper_limit/primes[i]
prime_factors += [primes[i]]
i += 1
if current_upper_limit != 1:
prime_factors += [current_upper_limit]
#print(prime_factors)
prime_counts = [[prime_factors[0], prime_factors.count(prime_factors[0])]]
#print(prime_counts,prime_counts[-1][0],prime_factors[1])
for i in range(1,len(prime_factors)):
#print(prime_counts[-1][0],prime_factors[i])
if prime_counts[-1][0] != prime_factors[i]:
prime_counts += [[prime_factors[i], prime_factors.count(prime_factors[i])]]
#print(prime_counts)
divisors = [1]
counters = [x[1] for x in prime_counts]
#print(counters)
while sum(counters) > 0:
new_divisor = 1
for i in range(len(counters)):
#print(prime_counts[i][0],counters[i], new_divisor)
new_divisor *= prime_counts[i][0]**counters[i]
divisors += [new_divisor]
counters[0] -= 1
for i in range(len(counters)):
if counters[i] == -1:
counters[i] = prime_counts[i][1]
if i != len(counters) - 1:
counters[i+1] -= 1
else:
break
divisors.sort()
return divisors[:-1]
upper = 10000
prime_list = generate_primes(upper)
#print(prime_list)
all_amicables = []
number_sums = {}
for y in range(2,upper):
number_sums[y] = sum(divisor_finder(y,prime_list))
if number_sums[y] in number_sums:
if number_sums[y] != y:
if number_sums[number_sums[y]] == y:
all_amicables += [number_sums[y], y]
# print(divisor_finder(220), divisor_finder(284))
# print(sum(divisor_finder(220)), sum(divisor_finder(284)))
print(number_sums[220],number_sums[284])
print(all_amicables)
print(sum(all_amicables))
```
```python
names = open("names.txt", "r")
name_list = sorted([x[1:-1] for x in names.readline().split(",")])
names_score = 0
for i in range(len(name_list)):
current_name = name_list[i]
current_score = 0
for letter in current_name:
#print(letter, ord(letter) - 64)
current_score += ord(letter) - 64
names_score += current_score*(i+1)
print(name_list[i], (i+1)*current_score, names_score)
print(len(name_list))
```
```python
import math
def generate_primes(upper):
prime_threshold = upper
number_list = list(range(2, prime_threshold+1))
prime_list = []
current = 0
total_iteration = 0
while current < len(number_list):
if number_list[current] != -1:
prime = number_list[current]
prime_list += [prime]
increment = current + prime
while increment < len(number_list):
number_list[increment] = -1
increment += prime
total_iteration += 1
#print(number_list)
#print(prime_list)
current += 1
return prime_list
def divisor_finder(number, primes):
upper_limit = number
#upper_limit = 20023110541 #, good to use to double check. Is [2,2,3,167]
current_upper_limit = upper_limit
sqrt_limit = math.sqrt(upper_limit)
prime_factors = []
#we are going to hardcode 2 and 3 for looping sake
i = 0
while primes[i] < sqrt_limit and i < len(primes):
while current_upper_limit % primes[i] == 0:
current_upper_limit = current_upper_limit/primes[i]
prime_factors += [primes[i]]
i += 1
if current_upper_limit != 1:
prime_factors += [current_upper_limit]
#print(prime_factors)
prime_counts = [[prime_factors[0], prime_factors.count(prime_factors[0])]]
#print(prime_counts,prime_counts[-1][0],prime_factors[1])
for i in range(1,len(prime_factors)):
#print(prime_counts[-1][0],prime_factors[i])
if prime_counts[-1][0] != prime_factors[i]:
prime_counts += [[prime_factors[i], prime_factors.count(prime_factors[i])]]
#print(prime_counts)
divisors = [1]
counters = [x[1] for x in prime_counts]
#print(counters)
while sum(counters) > 0:
new_divisor = 1
for i in range(len(counters)):
#print(prime_counts[i][0],counters[i], new_divisor)
new_divisor *= prime_counts[i][0]**counters[i]
divisors += [new_divisor]
counters[0] -= 1
for i in range(len(counters)):
if counters[i] == -1:
counters[i] = prime_counts[i][1]
if i != len(counters) - 1:
counters[i+1] -= 1
else:
break
divisors.sort()
return divisors[:-1]
upper_limit = 28124
prime_list = generate_primes(upper_limit)
abundant_nums = []
for i in range(12, upper_limit-12):
divisors = divisor_finder(i, prime_list)
if sum(divisors) > i:
#print(i,sum(divisors), divisors)
abundant_nums += [i]
print(abundant_nums)
abundant_sum_nums = []
for num1 in abundant_nums:
for num2 in abundant_nums:
number = num1 + num2
if number < upper_limit:
abundant_sum_nums += [number]
else:
break
print(len(abundant_nums))
remove = set(abundant_sum_nums)
keep = [x for x in range(1,upper_limit)]
for number in remove:
keep.remove(number)
print(len(keep))
```
```python
import itertools
#Sorry that the next few lines don't look pythonic, I adjusted them for comment clarity sake
#The line should actually just read sorted(itertools.permutations(list(range(10))))[999999]
#We sort
sorted(
#all the permutations
itertools.permutations(
#of the numbers 0-9
list(range(10))
)
#and then we grab out the millionth permutation
)[999999]
```
```python
fib_1 = 1
fib_2 = 2
digits_to_find = 1000
#Start at index of 4 because we already have 1,1,2
running_count = 4
#keep going until the next fib digit length is greater than or equal to the digit to find.
while len(str(fib_1 + fib_2)) < digits_to_find:
fib = fib_1 + fib_2
fib_1 = fib_2
fib_2 = fib
running_count += 1
print(running_count)
```
```python
#This generates primes up to a threshold using sieving.
#I've used this sieve generator in many of my problems.
prime_threshold = 2*(1000**2) + 1000
number_list = list(range(2, prime_threshold+1))
prime_list = []
current = 0
total_iteration = 0
while current < len(number_list):
if number_list[current] != -1:
prime = number_list[current]
prime_list += [prime]
increment = current + prime
while increment < len(number_list):
number_list[increment] = -1
increment += prime
total_iteration += 1
#print(number_list)
#print(prime_list)
current += 1
######
#convert the list into a dictionary of {int:True}
#so that .get will return hits or null/false (I don't remember what it does)
quick_prime_list = {}
for prime in prime_list:
quick_prime_list[prime] = True
#######
#Set up the variables
a = -999
b = -1000
longest_n = [a,b]
longest_n_length = 0
upper_stop_a = 1000
upper_stop_b = 1000 #b is inclusive
#increment a to the upper stop
while a < upper_stop_a:
#increment b to the upper stop inclusive
while b <= upper_stop_b:
n = 0
#if it is less than 2 then the first number isn't prime...
if a + b > 1:
#now we just keep incrementing n while checking the prime list
while quick_prime_list.get(n**2 + a*n + b):
n += 1
#is this the highest n that we have generated???
if n > longest_n_length:
longest_n_length = n
longest_n = [a,b]
b += 1
#reset the a loop
b = -1000
a += 1
#use as debug to check the status of the a (main) loop
#if a % 10 == 0:
# print(a)
```
```python
max_square = 1001
spiral = 1
square_size = 2
total = 1
while square_size + 1 <= max_square:
for i in range(4):
spiral += square_size
total += spiral
square_size += 2
print(total)
```
```python
lower_limit = 2
upper_limit = 100
#create a set
distinct = set()
#go through the inclusive ranges
for i in range(lower_limit, upper_limit + 1):
for j in range(lower_limit, upper_limit + 1):
#do the set addition operator for a^b
distinct.add(i**j)
#print how many distinct pairs that we created
print(len(distinct))
```
```python
upper_limit = 9**5
digit_count = 1
#find the upper limit
while len(str(upper_limit))/digit_count > 1:
upper_limit += 9**5
digit_count += 1
print(upper_limit, digit_count)
#calculate every number between here and there
digit_fifths = []
for i in range(2, upper_limit):
current_digit_sum = 0
for j in [int(x) for x in str(i)]:
current_digit_sum += j**5
if current_digit_sum == i:
digit_fifths += [i]
print(digit_fifths)
print(sum(digit_fifths))
```
```python
break_threshold = 1000000000 #just something comfy to break
cycles = 0
pands = set()
a = 1
b = 1
#only break if the len of the all the digits is greater than 9 (pigeonhole)
while cycles < break_threshold and len(str(a)) + len(str(b)) + len(str(a*b)) <= 9:
current_str = str(a) + str(b) +str(a*b)
#iterate b until the current string length exceeds 9
while len(current_str) <= 9:
if len(current_str) == 9:
#we don't accept 0s, we are looking for 1-9
if '0' not in current_str:
#all digits appear once so the sum of counts should be 9 (9 numbers)
if sum([current_str.count(x) for x in current_str]) == 9:
pands.add(a*b)
b += 1
current_str = str(a) + str(b) + str(a*b)
#increment the cycle
a += 1
b = a
cycles += 1
print(pands, cycles)
print(sum(pands))
```
```python
import math
upper_limit = 100
cycles = 0
non_trivial_den = []
non_trivial_num = []
#denominator and numerator
for denominator in range(11,100):
for numerator in range(11,denominator):
if denominator % 10 == 0 or numerator % 10 == 0:
pass
else:
#iterate through the denominator to find numbers that are equivalent
counter = 0
for den_index in range(len(str(denominator))):
for num_index in range(len(str(numerator))):
cycles += 1
if int(str(numerator)[num_index]) == int(str(denominator)[den_index]):
new_num = int(str(numerator)[:num_index] + str(numerator)[(num_index+1):])
new_den = int(str(denominator)[:den_index] + str(denominator)[(den_index+1):])
if numerator/denominator == new_num/new_den:
print(denominator, numerator, new_num, new_den)
non_trivial_den += [new_den]
non_trivial_num += [new_num]
print(cycles, math.prod(non_trivial_den), math.prod(non_trivial_num))
```
```python
import math
#find the upper limit
digits = 9
sum_digits = math.factorial(9)
while sum_digits > digits:
digits *= 10
digits += 9
sum_digits += math.factorial(9)
print(len(str(digits)), digits, sum_digits)
### part 2 since we now know the upper limit
upper_limit = 2540160
fact_nums = []
for i in range(3, upper_limit):
if i == sum([math.factorial(int(x)) for x in str(i)]):
fact_nums += [i]
print(fact_nums)
```
```python
import math
prime_threshold = 1000000
number_list = list(range(2, prime_threshold+1))
prime_list = []
current = 0
total_iteration = 0
while current < len(number_list):
if number_list[current] != -1:
prime = number_list[current]
prime_list += [prime]
increment = current + prime
while increment < len(number_list):
number_list[increment] = -1
increment += prime
total_iteration += 1
#print(number_list)
#print(prime_list)
current += 1
print(len(prime_list))
circ_primes = [2]
prime_list = [prime for prime in prime_list if '0' not in str(prime) and '2' not in str(prime) and '4' not in str(prime) and '6' not in str(prime) and '8' not in str(prime)]
print(len(prime_list))
iterations = 0
for prime in prime_list:
iterations += 1
circular = True
current = prime
for i in range(1,int(math.log(prime, 10))+1):
current = int(str(current)[-1] + str(current)[0:-1])
#print(prime, current)
#print(prime, current)
if current not in prime_list:
circular = False
break
if circular:
circ_primes += [prime]
if iterations % 10000 == 0:
print(iterations/len(prime_list))
#print(circ_primes)
print(len(circ_primes))
```