Home

Problem #115 concerns separating rows of blocks into red sections and black sections. The question reads: Project Euler Problem 115: Counting block combinations II NOTE: This is a more difficult version of Problem 114. A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks… Read more

Problem #114 concerns partitioning a row of blocks with contiguous red sections and contiguous grey sections. The question reads: My solution for this problem involves dynamic programming. Here’s my solution: Solution #1: Dynamic Programming Approach It suffices to recursively find the number of ways a row of n units can be filled such that the… Read more

Problem #113 concerns numbers whose digits are neither increasing nor decreasing. The question reads: Project Euler Problem 113: Non-bouncy numbers Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468. Similarly if no digit is exceeded by the digit to its right… Read more

Problem #112 concerns numbers which are neither increasing nor decreasing. The question reads: Project Euler Problem 112: Bouncy numbers Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468. Similarly if no digit is exceeded by the digit to its right it… Read more

Problem #111 concerns 10-digit primes with lots of repeated digits. The question reads: My solution to this problem can best be described as a brute force approach. Here’s my solution: Solution #1: Brute Force Approach We simply search for primes with each digit. Through brute force it is possible to check every possible position of… Read more

Problem #109 concerns checking out in a game of darts. The question reads: My solution for this problem is another example of the powers of brute force. Here’s my solution: Solution #1: Brute Force Approach We simply check every combination of dart scores that end in a double and count the ones with a total… Read more

Problem #108 concerns the Diophantine equation 1/x + 1/y = 1/n for arbitrary integers n. The question reads: Project Euler Problem 108: Diophantine reciprocals I In the following equation x, y, and n are positive integers. 1/x + 1/y = 1/n For n = 4 there are exactly three distinct solutions: 1/5 + 1/20 = 1/4 1/6 + 1/12 = 1/4… Read more

Problem #107 concerns determining the Minimum Spanning Tree for a weighted graph. The question reads: As it turns out, the formal term for this type of minimal network is the Minimum Spanning Tree of the graph. There are many well known algorithms for finding the minimum spanning tree of an arbitrary graph. I used Prim’s… Read more

Problem #105 concerns sets with ordered sums of all of their subsets. The question reads: Project Euler Problem 105: Special subset sums: testing Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the following… Read more

Problem #104 concerns Fibonacci numbers which contain each of the digits 1-9 in their leftmost and their rightmost digits. The question reads: Project Euler Problem 104: Pandigital Fibonacci ends The Fibonacci sequence is defined by the recurrence relation: Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1. It turns out that F541, which contains 113… Read more

Problem #103 concerns sets of integers with ordered sums of all possible subsets. The question reads: Project Euler Problem 103: Special subset sums: optimum Let S(A) represent the sum of elements in set A of size n. We shall call it a special sum set if for any two non-empty disjoint subsets, B and C, the… Read more

Problem #102 concerns determining whether a point is within the triangle formed by a triple of coordinates. The question reads: Project Euler Problem 102: Triangle containment Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed. Consider the following two triangles: A(-340,495), B(-153,-910),… Read more

Problem #101 concerns polynomials that approximate higher degree polynomials based on consecutive outputs. The question reads: Project Euler Problem 101: Optimum polynomial If we are presented with the first k terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model… Read more

Before I begin, I’d like to state that I will probably take a break from Project Euler for a little while. While writing these first 100 blog posts, I finally accomplished my goal of solving the first 100 problems on Project Euler. When I started, I never expected to make it this far. Writing a… Read more

Problem #99 concerns comparing large exponential numbers. The question reads: Project Euler Problem 99: Largest exponential Comparing two numbers written in index form like 211 and 37 is not difficult, as any calculator would confirm that 211 = 2048 < 37 = 2187. However, confirming that 632382518061 > 519432525806 would be much more difficult, as both numbers contain over three million… Read more

Problem #98 concerns searching for anagrams in a list of words. The question reads: Project Euler Problem 98: Anagramic squares By replacing each of the letters in the word CARE with 1, 2, 9, and 6 respectively, we form a square number: 1296 = 362. What is remarkable is that, by using the same digital… Read more

Problem #97 concerns finding the last ten digits of a large Mersenne Prime. The question reads: Project Euler Problem 97: Large non-Mersenne prime 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,… Read more

Problem #96 concerns solving Sudoku grids. The question reads: I must confess, this is one of the problems where I’m not really sure why my solution is as efficient as it is. It took me a lot of troubleshooting to find a solution which could solve all of the grids in a reasonable amount of… Read more

Problem #95 concerns chains formed by repeatedly replacing a number with the sum of its proper factors. The question reads: Project Euler Problem 95: Amicable chains The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As… Read more

Problem #94 concerns triangles that are nearly equilateral and have integer area. The question reads: Project Euler Problem 94: Almost equilateral triangles 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… Read more

Problem #93 concerns the values that can be obtained by evaluating arithmetic expressions with specific sets of digits. The question reads: Project Euler Problem 93: Arithmetic expressions By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and… Read more

Problem #92 concerns the results when numbers are repeatedly replaced by the square of their digits. The question reads: Project Euler Problem 92: Square digit chains A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. For example,… Read more

Problem #91 concerns right triangles whose vertices lie on lattice points. The question reads: My solution for this problem involves a bit of brute force. Here’s my solution: Solution #1: Brute Force Casework Approach We have several cases to consider. The first is if the right angle is either at the origin or on one… Read more

Problem #90 concerns pairs of dice that can be rearranged to form all of the 2-digit square numbers. The question reads: My solution for this problem is very brute force-heavy, so I may come back to this problem to look for a more efficient solution. Here is my solution: Solution #1: Brute Force Approach We… Read more

Problem #89 concerns the number of characters in Roman numerals. The question reads: Project Euler Problem 89: Roman numerals For a number written in Roman numerals to be considered valid there are basic rules which must be followed. Even though the rules allow some numbers to be expressed in more than one way there is… Read more

Problem #88 concerns numbers which can be expressed as both the sum and the product of the numbers in the same set of numbers. The question reads: Project Euler Problem 88: Product-sum numbers A natural number, N, that can be written as the sum and product of a given set of at least two natural… Read more

Problem #87 concerns numbers which can be written as the sum of a perfect square, a perfect cube, and a perfect fourth power of prime numbers. The question reads: Project Euler Problem 87: Prime power triples The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28.… Read more

Problem #86 concerns the surface area diagonal of rectangular prisms. The question reads: My solution for this problem definitely falls into the category of brute force. Here is my solution: Solution #1: Brute Force Approach Let F(M) be the number of cuboids with this property ignoring rotations with dimensions less than or equal to M.… Read more

Problem #85 concerns finding the number of rectangles with sides along a lattice grid. The question reads: This problem is very well known among those who participate in math competitions. Here is my solution: Solution #1: Combinatorial Approach We can observe that in a grid with m horizontal lines and n vertical lines, any rectangle… Read more

Problem #84 concerns simulations of the game Monopoly. The question reads: I apologize for not embedding this problem in WordPress. I felt it would be much simpler if I just added a screenshot due to the long list of instructions. Regardless, this is one of the more intimidating early questions of Project Euler. My solution… Read more

Problem #83 is a more complex version of Problems #81 and #82. The question reads: Project Euler Problem 83: Path sum: four ways In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and… Read more

Problem #82 is a more complex version of Problem #81. The question reads: Project Euler Problem 82: Path sum: three ways The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down,… Read more

Problem #81 concerns finding the minimum weighted path along the rows and columns of a grid. The question reads: Project Euler Problem 81: Path sum: two ways In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated… Read more

Problem #80 concerns the digits of the decimal expansions of irrational square roots. The question reads: Project Euler Problem 80: Square root digital expansion 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… Read more

Problem #79 concerns finding the shortest string with given substrings. The question reads: Project Euler Problem 79: Passcode derivation A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th… Read more

Problem #78 is yet another problem which involves partitions. The question reads: Project Euler Problem 78: Coin partitions Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7. OOOOO OOOO   O OOO   OO OOO … Read more