본문 바로가기

Euler Project

Problem 66 - Investigate the Diophantine equation x2 − Dy2 = 1. 링크 Consider quadratic Diophantine equations of the form: x2 – Dy2 = 1 For example, when D=13, the minimal solution in x is 6492 – 131802 = 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 – 222 = 1 22 – 312 = 1 92 – 542 = 1 52 – 622 = 1 82 – 732 = 1 Hence, by considering .. 더보기
Problem 66 - Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e. 링크 The square root of 2 can be written as an infinite continued fraction. 2 = 1 + 1 2 + 1 2 + 1 2 + 1 2 + ... The infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)]. It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider.. 더보기
Problem 64 - How many continued fractions for N ≤ 10000 have an odd period? 링크 All square roots are periodic when written as continued fractions and can be written in the form: N = a0 + 1 a1 + 1 a2 + 1 a3 + ... For example, let us consider 23: 23 = 4 + 23 — 4 = 4 + 1 = 4 + 1 1 23—4 1 + 23 – 3 7 If we continue we would get the following expansion: 23 = 4 + 1 1 + 1 3 + 1 1 + 1 8 + ... The process can be summarised as follows: a0 = 4, 1 23—4 = 23+4 7 = 1 + 23—3 7 a1 = 1, 7.. 더보기
Problem 63 - How many n-digit positive integers exist which are also an nth power? 링크 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? python sum(len(str(a**b)) == b for a in range(1, 10) for b in range(1, 22)) 더보기
Problem 62 - Find the smallest cube for which exactly five permutations of its digits are cube. 링크 The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). 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. python p = {} l = {} seed = 1 while True: n = seed**3 k = "".join(sorted(str(n))) if p.has_ke.. 더보기
Problem 61 - Find the sum of the only set of six 4-digit figurate numbers with a cyclic property. 링크 Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae: Triangle P3,n=n(n+1)/2 1, 3, 6, 10, 15, ... Square P4,n=n2 1, 4, 9, 16, 25, ... Pentagonal P5,n=n(3n1)/2 1, 5, 12, 22, 35, ... Hexagonal P6,n=n(2n1) 1, 6, 15, 28, 45, ... Heptagonal P7,n=n(5n3)/2 1, 7, 18, 34, 55, ... Octagonal P8,n=n(3n2.. 더보기
Problem 60 - Find a set of five primes for which any two primes concatenate to produce another prime. 링크 The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property. Find the lowest sum for a set of five primes for which any two primes concatenate.. 더보기
Problem 59 - Using a brute force attack, can you decrypt the cipher using XOR encryption? 링크 Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107. A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR functio.. 더보기
Problem 58 - Investigate the number of primes that lie on the diagonals of the spiral grid. 링크 Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed. 37 36 35 34 33 32 31 38 17 16 15 14 13 30 39 18 5 4 3 12 29 40 19 6 1 2 11 28 41 20 7 8 9 10 27 42 21 22 23 24 25 26 43 44 45 46 47 48 49 It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers.. 더보기
Problem 57 - Investigate the expansion of the continued fraction for the square root of two. 링크 It is possible to show that the square root of two can be expressed as an infinite continued fraction. 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213... By expanding this for the first four iterations, we get: 1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379... The next three expansions are 99/70, 2.. 더보기

티스토리툴바