3. PE Q51-#
%run PE_pre_running.py
3.1. PE 51#
3.2. PE 52#
#52 Permuted Multiples
def permuted(n):
listnum=list(map(int, str(n)))
listnum1=listnum[:]
listnum1.sort()
m=1
old=list_to_int(listnum)
while True:
n=old*(m+1)
test=list(map(int, str(n)))
test.sort()
if test!=listnum1:
break
m+=1
return m
def solve(m):
n=1000
while True:
num=permuted(n)
if num>=m:
break
n+=1
return n
print(solve(6))
3.3. PE 53#
# 53 Combinatoric Selections
def ncr(n, r):
return factorial(n)/(factorial(r)*factorial(n-r))
over_million=0
for n in range(22,101):
for r in range(3,n-1):
if ncr(n,r)>1000000:
over_million+=1
over_million
3.4. PE 55#
#55 Lychrel Numbers
MAX_ITERATIONS = 50
def isPalindrome(number):
return number == reverse(number)
def reverse(number):
reverse = 0;
while (number > 0):
remainder = number % 10
reverse = (reverse * 10) + remainder
number = int(number / 10)
return reverse
def isLychrel(number):
for i in range(MAX_ITERATIONS):
number+=reverse(number)
if (isPalindrome(number)):
return False
return True
num_lyc=0
for i in range(1, 10000):
if isLychrel(i)==True:
num_lyc+=1
num_lyc
3.5. PE 56#
#56 Powerful Digit Sum
sum_num=0
for i in range(1, 100):
for j in range(1, 100):
current_sum=0
power=i**j
list_power=list(map(int, str(power)))
for digit in list_power:
current_sum+=digit
if current_sum>sum_num:
sum_num=current_sum
sum_num
3.6. PE 57#
# 57 Square Root Convergents
def convergent_square_root2(term):
numerator=3
denominator=2
for _ in range(term-1):
denominator1=numerator+denominator
numerator=denominator+denominator1
denominator=denominator1
return [numerator,denominator]
def solve():
ans=0
for i in range(1,1001):
fraction=convergent_square_root2(i)
n=list(map(int,str(fraction[0])))
d=list(map(int,str(fraction[1]))) #separates number's digits into list
if len(n)>len(d):
ans+=1
return ans
solve()
3.7. PE 58#
# 58 Spiral Primes
# find quicker solution
from gmpy2 import is_prime
diagonal=[1]
n=1
x=2
spiral_percentage=100
for i in range(5000000):
print(spiral_percentage)
for i in range(4):
n+=x
diagonal.append(n)
while spiral_percentage>=10:
print(spiral_percentage)
for i in range(4):
n+=x
diagonal.append(n)
primes=0
for num in diagonal:
if is_prime(num):
primes+=1
spiral_percentage=100*primes/len(diagonal)
n
3.8. PE 62#
#62
import time
start = time.time()
cubes = []
i = 0
while True:
cube = sorted(list(str(i**3)))
cubes.append(cube)
if cubes.count(cube) == 5:
print((cubes.index(cube))**3)
break
i += 1
end = time.time()
print(end - start)
3.9. PE 63#
# 63 Powerful Digit Counts
num=0
for i in range(1,10):
for j in range(1,22):
if length(i**j)==j:
num+=1
num
3.10. PE 65#
#65 Convergents of e
def solve(N):
n=2
prev_n=1
fract=1
for k in range(2, N+1):
temp=prev_n
if (k % 3 == 0):
fract=2*int(k/3)
else:
fract=1
prev_n=n
n=fract * prev_n + temp
sum = digit_sum(n)
return sum
def digit_sum(num):
sum = 0
while num > 0:
sum = sum + (num % 10)
num = num // 10
return sum
#cal
solve(100)
(* 65 Convergents of e *)
3.11. PE 66#
see https://en.wikipedia.org/wiki/Pell’s_equation
#66 Diophantine Equation,
3.12. PE 69#
#69 Totient Maximum
def factors(n):
intnum=int(n**1/2)+1
num=[]
for i in range(1, intnum):
if n%i==0:
num.append(i)
for number in num:
if n/number not in num:
num.append(n/number)
return num
def prime1(n):
if len(factors(n))==2:
return True
return False
def smaller(mt, n):
if m<n:
return m
elif m>n:
return n
else:
return 'same'
def bcf(m, n):
fac=factors(m)
fac1=factors(n)
facs=fac+fac1
facs.sort()
facs.reverse()
for factor in facs:
if factor in fac and factor in fac1:
return factor
def coprime(m, n):
if m==1 or n==1:
return False
if prime(m)==True or prime(n)==True:
return True
if bcf(m, n)==1:
return True
else:
return False
def phi(n):
num=1
for i in range(2, n):
if coprime(i, n)==True:
num+=1
return num
def totient(n):
big=0
for i in range(2, n):
num=i/phi(i)
print(i)
if num>big:
big=num
return big
totient(50)
#69 FP 欧拉函数Euler's Totient Function
from sympy import totient
seq = [n / totient(n) for n in range(1, 1000000)] # Generate the sequence using the totient function
max_value = max(seq)
max_position = [i + 1 for i, value in enumerate(seq) if value == max_value]
max_position
(* 69 Totient Maximum, also called \phi function*)
(* seq = Table[ n/Length[Select[Range[n], CoprimeQ[#, n] == True &]]
, {n, 10}] ; pretty slow *)
seq = Table[ n/EulerPhi[n] , {n, 1000000} ];
Position[seq, Max[seq]]
Max[seq]
3.13. PE 71#
#71 Ordered Fractions
from math import floor
target = 3/7
pairs = [( floor(deno*target) , deno ) for deno in range(2, 1000000)]
fracs = [( n, deno ) for n, deno in pairs if (n/deno)<target] # Filter fractions < target
maxFrac = max(fracs, key=lambda frac: frac[0]/frac[1] )
maxFrac
(* 71 Ordered Fractions
Table[] gen [{numerator}, {denominator}]
Floor[] gen greatest integer <= d*target
Select[] and MaximalBy[], both are [list + function]
[[2]] the 2nd item, #[[2]] the 2nd input of the function
*)
target = 3/7;
MaximalBy[Select[ Table[ {Floor[d*target], d}, {d, 2, 1000000} ],
#[[1]]/#[[2]] < target & ],
#[[1]]/#[[2]] & ]
3.14. PE 74#
#74 Factorial Chains
def fact(n):
if n==0 or n==1:
return 1
elif n<0:
raise ValueError
else:
return n*fact(n-1)
factorials={i:fact(i) for i in range(10)}
num=0
for i in range(1,1000000):
n=i
lst=[]
while n not in lst:
lst.append(n)
n=list(map(int,str(n)))
n1=0
for j in n:
n1+=factorials[j]
n=n1
if len(lst)==60:
num+=1
print(num)
3.15. PE 75#
#75 Singular Integer Right Triangles
def sumPythagoreanTriplets(limits):
a, b, c, m = 0, 0, 0, 2
num=[]
nums=[]
for i in range(1,1000):
num.append(i)
d=a+b+c
while d<limits :
for n in range(1, m):
a=m*m-n*n
b=2*m*n
c=m*m+n*n
d=a+b+c
if d>limits:
break
print('Sum of triplet :', d)
nums.append(d)
if d==1000:
print('Special')
m+=1
return nums
sumPythagoreanTriplets(150)
3.16. PE 79#
#79 Passcode Derivation
73162890
3.17. PE 80#
#80 Square Root Digital Expansion
from re import findall
from math import sqrt
num=list(range(2,100))
num1=[]
num.remove(4)
num.remove(9)
num.remove(16)
num.remove(25)
num.remove(36)
num.remove(49)
num.remove(64)
num.remove(81)
for i in range(len(num)):
num[i]=sqrt(num[i])
for j in range(len(num)):
num2=num[j]*(10**99)
num.remove(num[j])
num2=int(num2)
num.append(num2)
for number1 in num:
dec = list(map(int, findall('\d', str(number1))))
num1.append(dec)
sum_digit=0
for list_num in num1:
for number2 in list_num:
sum_digit+=number2
print(num1)
print(sum_digit)
(* 80 Square Root Digital Expansion*)
numberDigits = RealDigits[Sqrt[2], 10, 100][[1]]
lst=Complement[Range[1, 99], Table[n^2, {n, 1, Floor[Sqrt[99]]}]];
totalNumberDigits=Table[RealDigits[Sqrt[i], 10, 100][[1]],{i,lst}];
lst1={{1,2,3,4,5},{6,7,8,9,10}};
Total[Total[lst1]]
Total[Total[totalNumberDigits]]
(* learn 3 functions:
RealDigits[] give a list of len digit
Complement[] after excluding the subsequent lists, the complement from the first list
Total[] *)
3.18. PE 92#
#92 Square Digit Chains
def chain(n):
while n!=1 and n!=89:
num=list(map(int, str(n)))
squared=0
for digit in num:
squared+=digit**2
n=squared
return n
num_89=0
for i in range(1, 10000000):
if chain(i)==89:
num_89+=1
if i%50000==0:
print(i)
num_89
3.19. PE 99#
# 99 Largest Exponential
import sys
import requests
# sys.set_int_max_str_digits(4000000)
response = requests.get("https://projecteuler.net/resources/documents/0099_base_exp.txt")
content = response.text # Read the content of the response
# Split the data into lines
lines = content.strip().split("\n")
column1 = []
column2 = []
for line in lines:
# Split the line by the comma and convert to integers
num1, num2 = map(int, line.split(","))
# Append the numbers to the respective lists
column1.append(num1)
column2.append(num2)
record=[1,1,0]
for i in range(1000):
if np.log(record[0])*record[1]<np.log(column1[i])*column2[i]:
record[0]=column1[i]
record[1]=column2[i]
record[2]=i+1
record[2]
(* 99 Largest Exponential
[[2]] denotes the 2nd item in {{1,2},{1,2}} *)
data = Import["https://projecteuler.net/resources/documents/0099_base_exp.txt", "CSV"];
new = Map[#[[2]] * Log[#[[1]]] &, data];
Position[new, Max[new]]
881418**505504>960290**502358
3.20. PE 104#
# 104 Pandigital Fibonacci Ends
# find quicker solution
import sys
sys.set_int_max_str_digits(1000000)
def fib_pandigital_front(n):
fib=list(map(int,str(fastFib(n))))
fib=fib[:9]
fib.sort()
if fib==[1,2,3,4,5,6,7,8,9]:
return True
return False
def fib_pandigital_back(n):
fib=list(map(int,str(fastFib(n))))
fib=fib[-9:]
fib.sort()
if fib==[1,2,3,4,5,6,7,8,9]:
return True
return False
n=89000
while True:
print(n)
if fib_pandigital_back(n) and fib_pandigital_front(n):
print(n)
KeyboardInterrupt()
n+=1
#112 Bouncy Numbers
from time import time
start=time()
def listint(num):
integer=''
for number in num:
integer=integer+str(number)
return int(integer)
def bouncy(n):
input=list(map(int, str(n)))
output=input[:]
output.sort()
if input==output:
return False
output.reverse()
if input==output:
return False
return True
def bouncy_percentage(n):
sum_bouncy=0
for i in range(1, n+1):
if bouncy(i)==True:
sum_bouncy+=1
ratio=sum_bouncy/n
return ratio*100
print(bouncy_percentage(1587000))
end=time()
print(end-start)
# ans - 1587000
(* 121 Disc Game Prize Fund
Person will have to pull out blue >=8 times*)
ncr[n_,r_]:=n!/(r!*(n-r)!) (*n choose r combinatorics function*)
blueChance[blues_]:=
lst=Table[blueChance[n]*ncr[15,n],{n,8,15}]
n=Floor[1/(Total[lst]/2^15)]
# 124 Ordered Radicals
# find quicker solution
def prime_factors(n):
factors=[]
for i in range(2,n):
if prime(i) and n%i==0:
factors.append(i)
return factors
def rad(n):
if n==1 or prime(n):
return n
fac=prime_factors(n)
ans=fac[0]
for i in range(1,len(fac)):
ans*=fac[i]
return ans
for i in range(2,3000):
rad(i)
(* 125 Palindromic Sums *)
(* add Boole[] to count number of times when <10^8 *)
(* learnt functions:
Accumulate[]
AnyTrue[{},test] true if any input passes the test
MemberQ[{},___] true if any element in list is ___
Module[]??? *)
isSumOfConsecutiveSquares[n_Integer] :=
Module[{maxK, sumsOfSquares},
maxK = Floor[Sqrt[n]];
(* Generate cumulative sums of consecutive squares starting from each k *)
sumsOfSquares = Table[
Accumulate[Table[(k + i)^2, {i, 0, maxK - k}]],
{k, 1, maxK}
];
(* Check if any sum sequence contains n with more than one term *)
AnyTrue[sumsOfSquares, MemberQ[#, n] && Length[#] > 1 &]
]
isSumSquaresPalindromic[n_Integer]:=isSumOfConsecutiveSquares[n]&&PalindromeQ[n]
lst=Table[isSumSquaresPalindromic[n],{n,2,9999}];
Count[lst,True]
(* 162 Hexadecimal Numbers *)
lst=Table[(n-1)*Factorial[n-1]/Factorial[n-3]*(14^(n-3)),{n,3,16}];
lst1=Table[(n-1)*Factorial[n-1]/Factorial[n-3]*(16^(n-3)),{n,3,16}];
n=(Total[lst1]-Total[lst])/2;
n=
BaseForm[Total[lst]+n,16]
# 179
def len_factors(n):
return len(factors(n))
num=1
for i in range(3, 10000000):
if prime(i)==True or prime(i+1)==True:
pass
else:
if len_factors(i)==len_factors(i+1):
num+=1
if i%10000==0:
print(i)
num
3.21. PE 187#
#187 FP way
from sympy import factorint
limit = 999999
count_two_prime_factors = sum(1 for n in range(3, limit ) if len(factorint(n)) == 2)
count_two_prime_factors
288725
(* 187 Semiprimes
Q: the code takes 11min, faster??? *)
Total[Table[
Boole[ Total[FactorInteger[n]][[2]] == 2 ]
, {n,3,99999999} ]
]
(* speed up but wrong answer ?? - add {{_,2}} *)
(* takes >11 min??? *)
Count[ FactorInteger /@ Range[3, 10^8-1]
,{{_, 1},{_, 1}} | {{_,2}}
]
lst=Table[
Boole[ Length[ FactorInteger[n] ]==2 ],
{n,3,30}]
lst={{2,5},{3,1}};
Total[lst][[2]]
3.22. PE 188#
7**7
823543
n=7
n=7**n % 1000000000
print(n)
823543
m=8123674
n=1798
math.floor(m/n)
n=1777;
For[i=0,i<1856,i++,n=Mod[1777^n,10000000]]
n
5962097
62097
62097
Mod[1777^1777,100000000]
00001777,87955697,70132343,33172343,65172343,5172343
# 243 Resilience
def resilient(n:int):
res=1
for i in range(2,n):
if coprime(i,n):
res+=1
return res/n
def solve():
n=24
while resilient(n)>(0.2):
print(n)
n+=1
return n
solve()
(* 345 *)
matrix = {
{7, 53, 183, 439, 863, 497, 383, 563, 79, 973, 287, 63, 343, 169, 583},
{627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913},
{447, 283, 463, 29, 23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743},
{217, 623, 3, 399, 853, 407, 103, 983, 89, 463, 290, 516, 212, 462, 350},
{960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350},
{870, 456, 192, 162, 593, 473, 915, 45, 989, 873, 823, 965, 425, 329, 803},
{973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326},
{322, 148, 972, 962, 286, 255, 941, 541, 265, 323, 925, 281, 601, 95, 973},
{445, 721, 11, 525, 473, 65, 511, 164, 138, 672, 18, 428, 154, 448, 848},
{414, 456, 310, 312, 798, 104, 566, 520, 302, 248, 694, 976, 430, 392, 198},
{184, 829, 373, 181, 631, 101, 969, 613, 840, 740, 778, 458, 284, 760, 390},
{821, 461, 843, 513, 17, 901, 711, 993, 293, 157, 274, 94, 192, 156, 574},
{34, 124, 4, 878, 450, 476, 712, 914, 838, 669, 875, 299, 823, 329, 699},
{815, 559, 813, 459, 522, 788, 168, 586, 966, 232, 308, 833, 251, 631, 107},
{813, 883, 451, 509, 615, 77, 281, 613, 459, 205, 380, 274, 302, 35, 805}
};
maxRowTotal = Max[Total /@ matrix]
maxColumnTotal=Max[Total /@ Transpose[matrix]]