Project Euler Q1-50

11. Project Euler Q1-50#

To solve PE problems so far, I include three approaches:

Python OOP
Python FP
MMA (FP primarily)

Pre-running Python functions:

After I solved many questions using Python, I found some functions were repeated, like Prime-Check, Fibonacci. Then I built this part to store these functions for pre-running.

%run _static/PE_pre_running.py

11.1. PE 1#

#1 Multiples of 3 or 5
sum_num=0
list_num=[]
for i in range(1, 999//3):
    m=i*3
    list_num.append(m)
for i in range(1, 999//5):
    m=i*5
    if m not in list_num:
        list_num.append(m)
    else:
        pass
for num in list_num:
    sum_num+=num
sum_num

11.2. PE 2#

#2 Even Fibonacci Numbers
num=0
sum_num=0
list_fib=[]
for i in range(3000000):
    num=fastFib(i)
    list_fib.append(num)
for num in list_fib:
    if num//2==num/2:
        sum_num+=num
sum_num

11.3. PE 4#

#4 Largest Palindrome Product
m=999
n=999
list_palin=[]
for i in range(900):
    for i in range(900):
        print(m*n)
        n-=1
        if palindrome(m*n):
            print('Palindrome')
            list_palin.append(m*n)
    m-=1
    n=999
max(list_palin)

11.4. PE 5#

#5 Smallest Multiple
2520*11*13*17*19*2

11.5. PE 6#

# 6 Sum Square Difference
nums=[]
sums=0
n=1
for i in range(100):
    nums.append(n)
    n+=1
for num in nums:
    sums+=num
sums**2

# 6 Sum Square Difference
nums=[]
sums=0
n=1
for i in range(100):
    nums.append(n)
    n+=1
for num in nums:
    sums+=num**2
sums

#6 results
25502500-338350

11.6. PE 7#

#7 10001st Prime
fd_prime(1)

11.7. PE 8#

#8 Largest Multiple In a Series
num=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450
output=list(map(int, str(num)))
nums=[0, 12]
list_num=[]
maxval=0
val=1
while nums[1]<=999:
    num0=nums[0]
    num1=nums[1]
    n=num0
    while n<=num1:
        list_num.append(output[n])
        n+=1
    for i in range(13):
        val*=list_num[i]
    if val>maxval:
        maxval=val
    val=1
    nums[0]+=1
    nums[1]+=1
    list_num=[]
maxval

11.8. PE 9#

#9 Special Pythagorean Triplet
pythagoreanTriplets(750)

11.9. PE 10#

#10 Summation of Primes
sum_prime=0
for i in range(2,2000000):
    if prime(i):
        sum_prime+=i
print(sum_prime)

11.10. PE 11#

#11 Largest Product in a Grid
87*97*94*89

11.11. PE 12#

#12 Highly Divisible Triangular Number
seq=triangular_seq(12375)
facs=[]
for triangular in seq:
    facs.append(num_fac(triangular))
    if facs[-1]>=500:
        print(len(facs))
        break
max(facs)
print(len(facs))
max(seq)

11.12. PE 13#

#13 Large Sum
import requests
from bs4 import BeautifulSoup
response = requests.get("https://projecteuler.net/problem=13")  # Send a GET request to the URL
soup = BeautifulSoup(response.content, "html.parser")   # Parse the HTML content
numbers = soup.find("div", class_="problem_content").text.strip()  # Find the content of interest (in this case, the numbers)

numbers_list = numbers.split('\n')  # Split the numbers into a list, assuming each number is separated by a newline character
numbers_list = [num for num in numbers_list if num] # Filter out any empty strings or irrelevant text
numbers_list = numbers_list[1:101] # Ensure that we only take the first 100 numbers

sum_num=0
sets = [int(num) for num in numbers_list]  # Convert the numbers from strings to integers and store them in a list
for num in sets:
    sum_num+=num
print(sum_num)

11.13. PE 14#

#14 Longest Collatz Sequence
n=1
max_len=1
for i in range(1000000):
    culen=collatz_length(n)
    if culen==525:
        print(n)
    if culen>max_len:
        max_len=culen
    n+=1

11.14. PE 15#

#15 Lattice Paths
n = 20
result = paths(n)
print(result)

11.15. PE 16#

#16 Power Digit Sum
num=[10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376]
output=list(map(int, str(num[0])))
sum_num=0
for number in output:
    sum_num+=number
sum_num

11.16. PE 17#

#17 Number Letter Counts
solve(1000)

11.17. PE 18#

#18 Maximum Path Sum I
l1=[75]
l2=[95, 64]
l3=[17, 47, 82]
l4=[18, 35, 87, 10]
l5=[20, 4, 82, 47, 65]
l6=[19, 1, 23, 75, 3, 34]
l7=[88, 2, 77, 73, 7, 63, 67]
l8=[99, 65, 4, 28, 6, 16, 70, 92]
l9=[41, 41, 26, 56, 83, 40, 80, 70, 33]
l10=[41, 48, 72, 33, 47, 32, 37, 16, 94, 29]
l11=[53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14]
l12=[70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57]
l13=[91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48]
l14=[63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31]
l15=[4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
triangle=[l1, l2, l3, l4, l5, l6, l7, l8, l9, l10, l11, l12, l13, l14, l15]
for i in range(len(triangle) - 2, -1, -1):
    for j in range(len(triangle[i])):
        triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])
max_total = triangle[0][0]
print(max_total)

11.18. PE 19#

#19 Counting Sundays
import datetime
count=0
for year in range(1901, 2001):
    for month in range(1, 13):
        if datetime.date(year, month, 1).weekday()==6:
            count+=1
print(count)

11.19. PE 20#

#20 Factorial Digit Sum
num=fact(100)
output=list(map(int, str(num)))
sum_num=0
for number in output:
    sum_num+=number
sum_num

11.20. PE 21#

# 21 Amicable Numbers
amic=[]
for i in range(1,10000):
    if amicable(i):
        amic.append(i)
sum(amic)

11.21. PE 22#

#22 Names Scores
import requests
response = requests.get("https://projecteuler.net/resources/documents/0022_names.txt")   # Send a GET request to the URL
content = response.text     # Read the content of the response
names = [name.strip('"') for name in content.split(',')]  # Split the content by comma and remove double quotes
names.sort()

value={'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
tot_score=0
place=1
for name in names:
    score=0
    for letter in name:
        score+=value[letter]
    score*=place
    tot_score+=score
    place+=1
tot_score

def factors(n):
    facs = {1}
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            facs.add(i)
            facs.add(n // i)
    return facs
def abundant(n):
    return sum(factors(n)) > n
def sum_abundant(n, abundant_numbers):
    for ab in abundant_numbers:
        if (n - ab) in abundant_numbers:
            return True
    return False
abundant_numbers = {i for i in range(12, 28124) if abundant(i)}
non_abundant_sums = [i for i in range(1, 28124) if not sum_abundant(i, abundant_numbers)]
result = sum(non_abundant_sums)
print(result)

11.22. PE 23#

# 23 Non-Abundant Sums
def factors(n):
    facs=[1]
    for i in range(2,int(n**0.5)+1):  # 非常耗时，缩小范围
        if n%i==0:
            facs.append(i)
            facs.append(n//i)
    return facs

def abundant(n):
    return sum(factors(n))>n

def sum_abundant(n,abundant_numbers):
    for ab in abundant_numbers:
        if (n - ab) in abundant_numbers:
            return True
    return False
abundant_numbers = {i for i in range(12, 28124) if abundant(i)}
non_abundant_sums = [i for i in range(1, 28124) if not sum_abundant(i, abundant_numbers)]

sum(non_abundant_sums) # Error: smaller by 258348

11.23. PE 24#

#24 Lexicographic Permutations
import itertools
permutations = list(itertools.permutations(range(10)))
millionth_permutation = int(''.join(map(str, permutations[999999])))
millionth_permutation

11.24. PE 25#

#25 1000 Digit Fibonacci Number
fastFib(4781)
length(1731403589222002957294429346518895723709506082039860786521776201969997425190002580820509546929820263058457975554718584767897610032505496877507394744099980978096953962557220579370143960032185044755214925165471985133186165562568372954212266775160479690961083330407371040988504455586839093910684051542272860673487922394300583546141201071181523567766482697651998576131907383462584505182933770187893410602855362990044627645611957937480375221691136281665191108770486046208365987457152897898978151032624598781944378501953255407873508942191356136619446735012761729556373994129675990036580541567079157500214451848590106380276929004769735246144938528628285344388350842365138183068393693524442382719001304601982880025898373942014814103022093332575900147730351419594078092359452500825422173232850278854098501036548721303293491571977471641513836658780413653798660841910284032061829208989654332339843602086914702633919395534251088908273898020000096184168171559429402858006596531459999394154832243826895270097988797)

11.25. PE 26#

def pythagoreanTriplets3(limits) : 
	a, b, c, m = 0, 0, 0, 2
	triplet_sums=[]
	while a+b+c < limits : 
		for n in range(1, m) : 
			a = m * m - n * n 
			b = 2 * m * n 
			c = m * m + n * n
			if a+b+c > limits : 
				break
			triplet_sums.append(a+b+c)
			# print(a, b, c)
		m = m + 1
	print(triplet_sums)

# functions 26-50
def pythagoreanTriplets2(limits):
	a, b, c, m = 0, 0, 0, 2
	triplet_sums=[]
	while a+b+c < limits:
		a=2*m
		b=m**2-1 
		c=m**2+1 
		if a+b+c > limits: 
			break
		triplet_sums.append(a+b+c)
		# print(a,b,c)
		m+=1
	print(triplet_sums)

(* 26 *)
(* learn 4 functions: 
    Association[]
    Module[]
    KeyExistsQ[]
    Mod[] *)
cycleLength[d_] := Module[{rems = Association[], num = 1, pos = 1},
  While[! KeyExistsQ[rems, num] && num != 0,
    rems[num] = pos;
    num = Mod[10 num, d];
    pos++   ];
  If[num == 0, 0, pos - rems[num]]];

SortBy[Range[888, 999], cycleLength]
cycleLength[983]

{900, 960, 990, 888, 925, 999, 909, 984, 896, 910, 924, 936, 945, 962, 975, 956, 902, 
 
>   948, 954, 930, 992, 935, 891, 912, 950, 988, 920, 968, 949, 959, 972, 928, 957, 964, 
 
>   898, 927, 996, 889, 903, 946, 980, 890, 979, 940, 918, 952, 963, 944, 915, 976, 897, 
 
>   938, 966, 906, 942, 951, 978, 913, 955, 970, 985, 995, 981, 943, 993, 904, 986, 908, 
 
>   931, 973, 987, 969, 894, 907, 914, 921, 926, 933, 997, 895, 905, 965, 901, 923, 994, 
 
>   892, 916, 932, 934, 958, 939, 967, 917, 893, 899, 911, 919, 922, 989, 929, 961, 947, 
 
>   974, 982, 991, 998, 937, 941, 953, 971, 977, 983}

11.26. PE 27#

#27 Quadratic Primes
def sieveEratosthenes(num):
    isPrime = [True] * (num + 1)
    isPrime[0] = False
    isPrime[1] = False
    primes = []
    for i in range(2, (num + 1)):
        if isPrime[i]:
            primes.append(i)
            for j in range(2 * i, (num + 1), i):
                isPrime[j] = False
    return primes
    
def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    
    return True

def equation(n, a, b):
    return n ** 2 + a * n + b

b = sieveEratosthenes(1000)
del b[0]

maxA = 0
maxB = 0
maxCount = 0

for y in b:
    for x in range(-y, 1000, 2):
        c = 0
        while isPrime(equation(c, x, y)):
            c += 1
        if maxCount < c:
            maxA = x
            maxB = y
            maxCount = c
            
print(maxA * maxB)

11.27. PE 28#

#28 Number Spiral Diagonals
s=1
n=1
# diagonal numbers included in n
# 1001-1+2=1002
for i in range(2,1002,2):
    for j in range(4):
        n+=i
        s+=n
s

669171001

11.28. PE 29#

#29 Distinct Powers
list_num=[]
for i in range(99):
    n=i+2
    for j in range(99):
        m=j+2
        num=n**m
        if num not in list_num:
            list_num.append(num)
list_num.sort()
len(list_num)

11.29. PE 30#

#30 Digit Fifth Powers
def fifth(num):
    n=[num]
    output=list(map(int, str(n[0])))
    for number in output:
        power=number**5
        num-=power
    if num==0:
        return True
    else:
        return False
list_num=[]
sum_num=0
for i in range(1000000):
    n=i+2
    if fifth(n):
        list_num.append(n)
for num in list_num:
    sum_num+=num
sum_num

#30 FP way
def fifth1(num):
    return num == sum(int(digit) ** 5 for digit in str(num))

sum_num1 = sum(n for n in range(2, 1000000) if fifth1(n))
sum_num1

11.30. PE 31#

# 31 Coin Sums: use graph traversal (DFS) with memoization
from functools import lru_cache
valid_coins = [1, 2, 5, 10, 20, 50, 100, 200] 
@lru_cache(None)  # memoizes the function to avoid redundant calculations
def graph_search_ways(n, max_coin):
    if n == 0:
        return 1
    return sum(
        graph_search_ways(n - coin, coin) # Recursive but not loop
        if coin <= max_coin and coin <= n else 0
        for coin in valid_coins
    )

graph_search_ways(200,200)

(* 31 Coin Sums: use graph traversal (DFS) with memoization*)
(* learn functions:
    ClearAll[] 
    Memoization(:= ... =): store results to avoid recalculating for the same pair
    Table[]: loop over each coin in validCoins *)
ClearAll[graphSearchWays];
validCoins = {1, 2, 5, 10, 20, 50, 100, 200};
graphSearchWays[n_, maxCoin_] := graphSearchWays[n, maxCoin] =
  If[n == 0, 
          1, 
   Total[Table[If[coin <= maxCoin && coin <= n 
                  , graphSearchWays[n - coin, coin]
                  , 0], {coin, validCoins}] ]];

graphSearchWays[200, 200] (*calculate n of total pairs*)
TreeForm[ (*see logic structure*)
  If[n == 0, 1, 
  Total[Table[If[coin <= maxCoin && coin <= n, 
              graphSearchWays[n - coin, coin], 
              0], {coin, validCoins}]]]]

11.31. PE 32#

Math easy, coding hard.

memoization use (:= … )
gen number from digits using string, all possible combinations of digits where each digit be used only once
I tried numerically way, but computing time doubled
IntegerString[], Characters[]
Flatten[], flatten nested lists
Apply[] -> @@

#32 Pandigital Products
def checkPandigital(b, n):
	if (len(n) < b):
		return 0
	hash = [0] * b
	for i in range(len(n)):
		if (n[i] >= '0' and n[i] <= '9'):
			hash[ord(n[i]) - ord('0')] = 1
		else:
			if (ord(n[i]) - ord('A') <= b - 11):
			    hash[ord(n[i]) - ord('A') + 10] = 1
	for i in range(b):
		if (hash[i] == 0):
			return 0
	return 1
#cal
b = 13
n = "1298450376ABC"
if (checkPandigital(b, n)):
	print("Yes")
else:
	print("No")

Yes

(* 32 Pandigital Products *)
(* Check if the concatenation of x, y, product forms a 1-9 pandigital number stringly*)
pandigitalQ[x_, y_, xy_] := 
  StringLength[ str=IntegerString[x] <> IntegerString[y] <> IntegerString[xy] ] == 9 && 
  Sort[Characters[str]] == Characters["123456789"] ; 

(* List all valid xy then sum *)
pandigitalProducts = DeleteDuplicates[
    Select[ Flatten[ Table[{x, y, x*y}, {x, 1, 99}, {y, 1, 9999}], 1 ]
          , pandigitalQ @@ # & ]
          [[All, 3]] ]

Total[pandigitalProducts]

{6952, 7852, 5796, 5346, 4396, 7254, 7632}

11.32. PE 33#

Methods & Process

check for 2 digit numerators and denominators 49/98=4/8, 3 left to go
must have at least one common digit between numerator and denominator

(* 33 Digit Cancelling Fractions *)

11.33. PE 34#

#34 Digit Factorials
def spefact(num):
    n=[num]
    output=list(map(int, str(n[0])))
    for number in output:
        fac=factorial(number)
        num-=fac
    if num==0:
        return True
    else:
        return False
list_num=[]
sum_num=0
for i in range(1850000):
    n=i+1
    if spefact(n):
        list_num.append(n)
        print(i)
for num in list_num:
    sum_num+=num
sum_num-=3
sum_num

#34 FP way
from math import factorial

factorials = {str(d): factorial(d) for d in range(10)} # Precompute factorials for digits 0-9
def is_digit_factorial(num):
    return num == sum(factorials[digit] for digit in str(num))

sum_num = sum(n for n in range(10, 1850000) if is_digit_factorial(n))
sum_num

11.34. PE 35#

#35 Circular Sums
def list_to_int(lst):
    n=''
    for item in lst:
        n=n+str(item)
    return int(n)

def circular_prime1(n):
    if prime(n)==False:
        return False
    else:
        list_prime=[]
        while len(list_prime)<length(n):
            output = list(map(int, str(n)))
            list_prime.append(n)
            if prime(n)==False:
                return False
            else:
                first=output[0]
                output.remove(first)
                output.append(first)
                n=list_to_int(output)
        for prime1 in list_prime:
            if prime(prime1)==False:
                return False
        return True

#cal
list_circ=[]
for i in range(999998):
    if i%100==0:
        print(i)
    n=i+2
    if circular_prime1(n)==True:
        list_circ.append(n)
list_circ

#35 FP
from sympy import isprime  # how can we use Jonny-defined function here? 

def rotations(num):  # Function to get all rotations of a number
    s = str(num)
    return [int(s[i:] + s[:i]) for i in range(len(s))]

def is_circular_prime(num):
    return all(isprime(rot) for rot in rotations(num))

circular_primes = [n for n in range(2, 999999) if is_circular_prime(n)]
circular_primes 

(*35 Circular Sums*) 
rotations[n_Integer] := Module[{digits = IntegerDigits[n]},
  FromDigits /@ NestList[RotateLeft, digits, Length[digits] - 1]]

isCircularPrime[n_Integer] := AllTrue[rotations[n], PrimeQ] (*if all rotations of a number are prime*)
circularPrimes = Select[Range[2, 999999], isCircularPrime]

{2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331}

11.35. PE 36#

#36 Double Base Palindromes
def binary(num):
    return int(bin(num)[2:])
list_num=[]
for i in range(1000000):
    if palin(i) and palin(binary(i)):
        list_num.append(i)
sum_num=0
for number in list_num:
    sum_num+=number
sum_num

---------------------------------------------------------------------------

NameError                                 Traceback (most recent call last)

Cell In[8], line 6

      4 list_num=[]

      5 for i in range(1000000):

----> 6     if palin(i) and palin(binary(i)):

      7         list_num.append(i)

      8 sum_num=0

NameError: name 'palin' is not defined

11.36. PE 37#

#37 Truncatable Primes
def truncatable(num):
    input=list(map(int, str(num)))
    inp=list_to_int(input)
    if prime(num)==True:
        while length(num)>1:
            if prime(num)==True and num!=1:
                output=list(map(int, str(num)))
                output.remove(output[0])
                num=list_to_int(output)
            else:
                return False
        while length(inp)>1:
            if is_prime(inp)==True and num!=1:
                output=list(map(int, str(inp)))
                output.remove(output[-1])
                inp=list_to_int(output)
            else:
                return False
        return True
    else:
        return False
#cal
list_trun=[]
n=10
while len(list_trun)<=10:
    if truncatable(n)==True:
        list_trun.append(n)
    n+=1
list_trun

---------------------------------------------------------------------------

NameError                                 Traceback (most recent call last)

Cell In[9], line 27

     25 n=10

     26 while len(list_trun)<=10:

---> 27     if truncatable(n)==True:

     28         list_trun.append(n)

     29     n+=1

Cell In[9], line 4, in truncatable(num)

      2 def truncatable(num):

      3     input=list(map(int, str(num)))

----> 4     inp=list_to_int(input)

      5     if prime(num)==True:

      6         while length(num)>1:

NameError: name 'list_to_int' is not defined

11.37. PE 38#

Methods & Process

Already presented (1,2,3) and (1,2,3,4,5)->918273645, (1,2,3,4,5,6,7,8,9)->123456789, calculated 3 options and n>1 left 2 options: (1,2,3,4,5,6,7) (1,2,3,4,5,6,7,8)
When multiplied by 1 and 2, the numbers will be 4-digit and 5-digit,
when multiplied by 1, 2, 3 and 4, the numbers will be 2-digit for the first 3 and 3-digit for the last number,
when multiplied by 1, 2, 3, 4, 5 and 6, the number will be 1-digit for the first 3 and 2-digit for the last 3 numbers.
(1,2,3,4,5,6,7) and (1,2,3,4,5,6,7,8) not possible because too many numbers to multiply by. 9352*2=18704, 935218704 contains 0 is not answer

Conclusion

The biggest number in the lists is 9352, 9352*2=18704, but 935218704 is not 1 to 9 pandigital
The next biggest number in the lists is 9327, 9327*2=18654, 932618654 is 1 to 9 pandigital. Thus the answer should be 932618654.

(* 38 Pandigital Multiples *)

lst=Select[Range[5000, 9999], 
  Function[n, 
    Length[Union[IntegerDigits[n], IntegerDigits[2 n]]] == 9 && 
    1000 <= 2 n < 100000
  ]
];
lst[[-2;;]] (*cannot contain 5 in number unless number afterwards is 6 or bigger*)

{9327, 9352}

11.38. PE 39#

#39 Integer Right Triangles
# Ans:LCM(70,120)=840
pythagoreanTriplets2(1000)
pythagoreanTriplets3(1000)

11.39. PE 40#

# 40 Champernonwne's Constant
constant=[]
n=1
while len(constant)<1000000:
    d=list(map(int,str(n)))
    for num in d:
        constant.append(num)
    n+=1
ans=constant[0]*constant[9]*constant[99]*constant[999]*constant[9999]*constant[99999]*constant[999999]
ans

11.40. PE 41#

#41 Pandigital Primes
import itertools

def isPrime(num):
    if num <= 1:
        return False
    elif num == 2 or num == 3:
        return True
    if num % 2 == 0 or num % 3 == 0:
        return False
    if not(num % 6 == 1) and not(num % 6 == 5):
        return False
    i = 5
    while i * i <= num:
        if num % i == 0 or num % (i + 2) == 0:
            return False
        i += 6
    return True

p = list(map("".join, itertools.permutations('1234567')))

max = 0
for n in p:
    if prime(int(n)) and max < int(n):
        max = int(n)

print(max)

11.41. PE 42#

#42 Coded Triangle Numbers
import requests
response = requests.get("https://projecteuler.net/resources/documents/0042_words.txt")   # Send a GET request to the URL
content = response.text     # Read the content of the response
words = [name.strip('"') for name in content.split(',')]  # Split the content by comma and remove double quotes

def triangle(word):
    value=0
    values={'A':1, 'B':2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15, 'P':16, 'Q':17, 'R':18, 'S':19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}
    for letter in word:
        value+=values[letter]
    seq=triangular_seq(40)
    if value in seq:
        return True
    else:
        return False
tri_words=0
for word in words:
    if triangle(word):
        tri_words+=1
tri_words

11.42. PE 45#

(* 45 Triangular, Pentagonal, and Hexagonal 
    what I can learn?
    1) defining series 
    2) finding common items in lists using set theory: Intersection and Union*)
n=99999;
Tri = #(# + 1)/2 &  /@ Range[n];
Pen = #(3# - 1)/2 & /@ Range[n];
Hex = #(2# - 1) &   /@ Range[n];
Intersection[Tri,Pen,Hex]

  File "C:\Users\tangc\AppData\Local\Temp/ipykernel_12260/2372868435.py", line 1

    (* 45 Triangular, Pentagonal, and Hexagonal

          ^

SyntaxError: invalid syntax

11.43. PE 46#

#46 Goldbach's Other Conjecture
import time
start=time.time()
# Define a function that tests if an odd composite integer can be represented as the sum of a prime and twice a square
def other_conjecture(n):
    """Assume n is an odd composite integer"""
    for i in range(3, n-1, 2):
        num=n-i
        number=num/2
        sqrt_num=int(number**1/2)+1
        if prime(i)==True:
            for j in range(1, sqrt_num):
                if i+2*(j**2)==n:
                    return True
    return False
# calculation
n=9
while True:
    if prime(n)==True:
        n+=2
    else:
        if other_conjecture(n)==True:
            n+=2
        else:
            break
print(n)
end=time.time()
print(end-start)

9
0.0

11.44. PE 47#

(* 47 Distinct Primes Factors*)
lst=Table[FactorInteger[n],{n,134040,134050}];
lst1=Length/@lst;
ans=Select[Range[Length[lst1]],lst1[[#]]==4&];
ans1=Select[Range[3,Length[ans]],ans[[#]]==ans[[#-3]]+3&]
ans
(* learn 5 functions:
    Table[]
    Length[]
    FactorInteger[]
    Select[]
    Range[]*)

11.45. PE 48#

#48 Self Powers
n=1
sum_num=0
for i in range(1000):
    power=n**n
    sum_num+=power
    n+=1
sum_num

1000368199144695177095375011227646795567793680622934654583760988100234910747716194381428659099527845945869942643191290894720342979906407679647259860434238468038326040809691037615370376237713648510063115732951461774246705584266865759601815843666442832284556880313114548151539190975398485496645576513465858582712336401166221956188173449531674102688908321764663020306699770408625340766091595022791379368098369306375602813856646358773751558775213460225796579846583334007349358624342339332981334571237888809283103348760261360175950815609179464026871005243652109980863552142014242903434068560936573231079342194031864413918101238151056509267393515760392842472501391594073463001521843811073767021711026307504695733467897821866906648469828346607412967395801797791683609834722432241952845352564681868240369569566192825555323558078061997527689983848863374786789331581565252059172614339424600986143259233167583371070362625554531852054166117148858229508581589614337594463277554380518380921301218836327102231407332201109740102580216469298331766920619646083790732807627360614428085171565006289728508688964226799647192582924058589530750674578385365561878559589685756225692348914746922810913915619834754117648358035814128670294158565669942087736286390942241547226015004471330630113072042704288905042142628193771918594574302202147201188486345913190833752307476966010547423928871063118783026036381319039052008252072057933666712918946233312793697094074224187872045970976444309242782187738320257490080824330074991698698239561125811127607863900355221737846690567707344074494145266662103839812840216303448476913957072355732716627098372245223046792919747259113157425824064858331415400943278213042954635053574045209984512221264241903550178416824551412548637590007779082539288247751653566899882749594405895102587985539527709493510049546445427265617478399107188238681771215904234119392247489751079085948055945098805617963722928469554263782217625160428008228845552540344494860195267115187092227766195753907211126646150140614744233974765273475619964311852858614167819668340124730487710162006793529985758820653677274379563313495454526632718723482339494825759821076401694316043456512117937935456463521463021197726694983558929132357576188594977516630734212863869456164205525536767311298137182511494649463663073759219213056823561667776093739425742883930712609962163464088038826569132032160692637206183085942987973684584276491784843115472077900401692595694119273553511025991265446039366288921743581333200083717105241171504606883543418862024047552177055263424469501298905901938158245938633694105024815166679813689156668341197713475094389904887126794468901893850475050011205225742455555625750560213230387910337983950333245020653238989115507013882956277763880795687210857196493893142656713105966275422144605988058939600603604226921401402096519294250488670297983396353279460453142375542267881989197481789780678955093763193658603690898474826976906544473978017455720367929981796023041785852626797271283465789498383642350667978127819110846700

def primes():
    """Generate a list of 4-digit prime numbers excluding the known sequence."""
    num = []
    for i in range(1001, 9998, 2):
        if prime(i):
            num.append(i)
    # Exclude the specific prime sequence
    excluded = {1487, 4817, 8147}
    num = [n for n in num if n not in excluded]
    return num

def permutations(lst):
    """Find primes that have the same digit permutations."""
    # Sort digits of each number
    sorted_lst = [''.join(sorted(str(num))) for num in lst]
    
    # Dictionary to store primes by their sorted digit permutation
    perm_dict = {}
    for i, num in enumerate(lst):
        perm = sorted_lst[i]
        if perm in perm_dict:
            perm_dict[perm].append(num)
        else:
            perm_dict[perm] = [num]
    
    # Return only those lists with more than one permutation
    return {k: v for k, v in perm_dict.items() if len(v) > 1}

# Get primes and permutations
prime_list = primes()
permutations_dict = permutations(prime_list)

print(permutations_dict)

11.46. PE 49#

# 49 Prime Permutations
def primes():
    num=[]
    for i in range(1001,9998,2):
        if prime(i)==True:
            num.append(i)
    num.remove(1487)
    num.remove(4817)
    num.remove(8147)
    return num

def permutations(lst):
    for i in range(len(lst)):
        lst[i]=list(map(int,str(lst[i])))
        lst[i].sort()
    lst.sort()
    for i in range(len(lst)):
        print(lst[i])
    for i in range(1,len(lst)):
        if lst[i]!=lst[i-1]:
            lst.remove(lst[i-1])
    lst.remove(lst[-1])
    return lst

print(permutations(primes()))
print(primes())

Project Euler Q1-50

Contents

11. Project Euler Q1-50#

11.1. PE 1#

11.2. PE 2#

11.3. PE 4#

11.4. PE 5#

11.5. PE 6#

11.6. PE 7#

11.7. PE 8#

11.8. PE 9#

11.9. PE 10#

11.10. PE 11#

11.11. PE 12#

11.12. PE 13#

11.13. PE 14#

11.14. PE 15#

11.15. PE 16#

11.16. PE 17#

11.17. PE 18#

11.18. PE 19#

11.19. PE 20#

11.20. PE 21#

11.21. PE 22#

11.22. PE 23#

11.23. PE 24#

11.24. PE 25#

11.25. PE 26#

11.26. PE 27#

11.27. PE 28#

11.28. PE 29#

11.29. PE 30#

11.30. PE 31#

11.31. PE 32#

11.32. PE 33#

11.33. PE 34#

11.34. PE 35#

11.35. PE 36#

11.36. PE 37#

11.37. PE 38#

11.38. PE 39#

11.39. PE 40#

11.40. PE 41#

11.41. PE 42#

11.42. PE 45#

11.43. PE 46#

11.44. PE 47#

11.45. PE 48#

11.46. PE 49#