Project Euler

Problem 24 - Lexicographic permutations

The task of problem 24 is to find the 1,000,000th permutation of the following set:

S = {0 1 2 3 4 5 6 7 8 9}

The set has 10 items, so its amount of total possible permutations is 10!, or ~3.6 million. The most straightforward method is to generate a list of all ~3.6 million permutations, sort it (if necessary), and pick the millionth one. However, it's possible to decrease the amount of required generations by guessing what the first few digits of the millionth permutation are.

Suppose that all 3,628,800 permutations are generated and stored in an array; the array's indeces range from 0 to 3628799 and the millionth permutation is at index 999999. Each permutation starts with one of 10 digits, so it can be said that 3628800÷10 = 362,880 permutations begin with the same first digit:

First item Index range
{0 _ _ _ _ _ _ _ _ _ } 0-362879
{1 _ _ _ _ _ _ _ _ _ } 362880-725759
{2 _ _ _ _ _ _ _ _ _ } 725760-1088639
{3 _ _ _ _ _ _ _ _ _ } 1088640-1451519
{4 _ _ _ _ _ _ _ _ _ } 1451520-1814399
{5 _ _ _ _ _ _ _ _ _ } 1814400-2177279
{6 _ _ _ _ _ _ _ _ _ } 2177280-2540159
{7 _ _ _ _ _ _ _ _ _ } 2540160-2903039
{8 _ _ _ _ _ _ _ _ _ } 2903040-3265919
{9 _ _ _ _ _ _ _ _ _ } 3265920-3628799

All permutations that exist between indeces 0-362879 begin with 0, all between 362880-725759 begin with 1, etc. Because the millionth permutation's index, 999999, falls within the third row, we know that it must begin with 2.

To find the next digit of the millionth permutation, we delve into this third row, divide it into further rows, and once again search for an index range in which the index 999999 lies. The first digit is 2, so the possibilities for the next digit are 0, 1, 3, 4, 5, 6, 7, 8, and 9. (1088640-725760)÷9 = 40,320 permutations that begin with the same second digit, and so:

First and second item Index range
{2 0 _ _ _ _ _ _ _ _} 725760-766079
{2 1 _ _ _ _ _ _ _ _} 766080-806399
{2 3 _ _ _ _ _ _ _ _} 806400-845719
{2 4 _ _ _ _ _ _ _ _} 846720-887039
{2 5 _ _ _ _ _ _ _ _} 887040-927359
{2 6 _ _ _ _ _ _ _ _} 927360-967679
{2 7 _ _ _ _ _ _ _ _} 967680-1007999
{2 8 _ _ _ _ _ _ _ _} 1008000-...

Now, our target at index 999999 lies within the seventh row. We delve into the seventh row and repeat.

This process repeats itself until the length of the solution set (currently 2) becomes equal to the length of the original set S.

Problem 43 - Sub-string divisibility

A naive solution to problem 43 is to generate every possible 10-digit pandigital, then test each one for the given divisibility requirements. Depending on how the pandigitals are generated, this may be a time-consuming process given that very few pandigitals satisfy the requirements; the vast majority of them (over 99% of them, in fact) would go to waste.

Let listD be a list of all possible 3-digit sequences, where each one has the following properties:

  1. Its integer form is divisible by D.
  2. It doesn't have repeating digits.
  3. It has exactly 3 digits, including a possible leading zero.

For every divisor D in the problem text, generate listD. That is:

Then, when traversing each list in a series of nested for-loops, one term from each can be combined into a 9-digit sequence (from d2 to d10) as shown in the example. After filling in the missing first digit d1, a 10-digit sequence is formed.

Using this method of generating 10-digit sequences, one solution is:

  1. Let sum = 0.
  2. For each x2 in list2, x3 in list3, x5 in list5, etc.:
    1. The first and second digits of the element from the current list must match the second and third digits of the element from the previous list (e.g. x11[0]=x7[1] and x11[1]=x7[2] must both be true). If not, continue to the next element of the current list.
    2. Let pan be an empty 10-digit sequence.
    3. Populate the last 9 elements of pan like so:
      { _, x2[0], x2[1], x2[2], x7[0], x7[1], x7[2], x17[0], x17[1], x17[2] }
    4. If any digits repeat, then the sequence isn't pandigital. Continue.
    5. Otherwise, fill in the missing 1st digit. The sequence is now a valid 10-digit pandigital.
    6. Convert pan into an integer and add it to sum.
  3. Print sum.

Problem 47 - Distinct primes factors

A brute force approach to solving problem 47 is to check every term from 1 to a large upper limit (500k is sufficient) until four consecutive terms, each of which has exactly four distinct prime factors, are found. The amount of terms to test can be reduced as follows.

  1. Create a list of numbers from 1 to an upper limit. Call this list numbers.
  2. By definition, all prime numbers have only 1 distinct prime factor. Therefore, we need only test terms which are nonprime. Split numbers into two lists: primes and nonprimes. Call these lists primes and nonprimes.
  3. From nonprimes, we need only check terms which are consecutive with at least 3 other terms before or after it. Remove all terms that do not satisfy this condition. Call this new list consec_nonprimes.

When the upper limit is 500k, this reduces the list to 407k terms, improving run time by a fair amount.

Problem 51 - Prime digit replacements

Problem 51 has a difficulty rating of 15% and is the first problem to be rated higher than 5% - an appropriate welcome to page 2 of the problem archive.

The number shown in the example is 56003, and with its swap positions being in the form 56**3, the following family is produced:

Of this family, 7 members are prime (note that 56003 itself is a member). The goal is to find a similar number which produces a family that contains 8 prime members. The catch is that the swap positions can be anywhere in the number, not just adjacent to each other! The brute force approach is to check every possible combination of swap positions that can exist within a number, e.g. for the number 942:

Note that 942 itself and *** aren't considered. These swap positions could be hardcoded, but it would only be reasonable to do so for small numbers that are 2, 3, and perhaps 4 digits in length.

One approach is to use a boolean array to represent the swap positions for a number, in which the digits located at true indeces get swapped with 0-9 and those at false indeces remain the same. When applied to 942, the collection of boolean arrays is as follows:

*42 {true false false}
9*2 {false true false}
94* {false false true}
* *2 {true true false}
9* * {false true true}
*4* {true false true}
Incidentally, boolean arrays can be written as binary sequences, e.g. {true false true} = 101 = 52. Therefore, to generate every possible swap pattern for a number, we simply generate every binary sequence which is able to fit within the digit length of the number, or every N-bit binary sequence for a number which consists of N digits, i.e. every 3-bit sequence for 942.

Using binary sequences, one possible solution is:

Problem 61 - Cyclical figurate numbers

Problem 61 has a difficulty rating of 20%, which is the highest rating encountered thus far.

The goal is to create a 6-member set in which each mentioned polygonal type is present and each member forms a cycle (its last 2 digits are the same as another member's first 2 digits).

To clarify:

The algorithm used in my solution is as follows:

  1. Create 6 separate lists representing the polygonal types (use only 4-digit numbers).
  2. Create a master list which contains every item in the above lists, without repeats.
  3. Create an empty list for storing 6-member sets. Call this list solutions.
  4. For each x on the master list:
    1. Create an empty set which acts as an attempted solution. Call it solution.
    2. Append x to solution.
    3. For each item on the master list:
      • If item is in solution, skip it.
      • If the final member of solution forms a left-to-right cycle with item (if the final member's last 2 digits are the same as item's first 2 digits), then append item to solution.
      • Reset the current loop (start again from index 0).
    4. If solution doesn't have exactly 5 members at this point, it fails. Skip.
    5. For each y on the master list:
      • If y would turn solution into a cyclic set (if y's first 2 digits are the same as the final member's last 2 digits, and y's last 2 digits are the same as the first member's first 2 digits), append y to solution. Break.
    6. If solution has 6 members, it's a possible solution! Append it to solutions.
  5. For each solution in solutions:
    • If solution has at least 1 member from each polygonal set, the problem is solved.

An optional step is to ignore all terms whose third digit is 0, because they cannot form left-to-right cycles with 4-digit numbers. By doing so, the master list's length is reduced from 299 to 255. However, it doesn't make any noticeable difference in run time.

Problem 66 - Diophantine equation

Problem 66's difficulty rating is 25%, the highest one yet.

The given Diophantine equation is:

x2 - Dy2 = 1

The goal is to plug in every nonsquare D from 1 to 1000 and solve for x and y, where x must be as small as possible. Unfortunately, this problem can't be solved with brute force in a realstic amount of time because many values of x end up being large integers which may take hours to compute (e.g. x = 159150073798980475849 when D = 277).

The problem text doesn't mention that this is a special type of Diophantine equation, known as Pell's equation, which can be solved easily by using convergents, a topic which was introduced in the preceding problem (in turn, convergents are based on continued fractions, a topic which was introduced two problems prior).

One algorithm for solving this problem is:

Problem 68 - Magic 5-gon ring

Problem 68 is the second one to have a difficulty rating 25%.

To solve a magic 5-gon ring, each of the 10 nodes must be filled in so that each value from 1 to 10 appears exactly once. Similarly, earlier problems involved pandigital numbers, or numbers in which each digit from 0 to 9 appeared exactly once. In this case, we can simply reuse the pandigital functions from earlier problems and treat every 0 as a 10.

Let ABCDEFGHIJ be a 10-digit pandigital. Replace 0 with 10. The sequence is now a 5-gon ring solution if it satisfies the following equalities:
A+G+H = B+H+I = J+I+C = F+J+D = E+F+G


However, this solution is inefficient because it disregards the orientation of the graph: a pandigital that solves the left graph and one that solves the right graph will be considered two different solutions, even though they solve the same graph but rotated (there being 5 possible rotations). Therefore, when generating every nth 10-digit pandigital from n = 1 to n = 10!, the same solution will be found 5 times as 5 different permutations. This can be circumvented by incrementing n by 4 rather than by 1 after each iteration. I'm not exactly sure why this works, though. :)

Note that the problem requests a final answer which is 16 digits long. If none of the external nodes A, B, C, D, or E hold 10, then the final answer will end up being 17 digits long. Therefore, all potential solutions in which 10 isn't an external node (i.e. not one of the first 5 elements of the sequence) may be ignored.

My solution is:

  1. Create an empty list of bignums.
  2. For n = 1 ; n <= 10! ; n += 4:
    1. Generate the nth 10-digit pandigital.
    2. Replace 0 with 10.
    3. If 10 is not located at index 0, 1, 2, 3, or 4, then this sequence won't form a final answer which is 16 digits long. Skip.
    4. If the sequence satisfies the 5-gon ring equalities:
      1. Rewrite the sequence into the comma/semicolon format shown in the problem text. It must be ordered clockwise.
      2. Convert it into a bignum.
      3. Append the bignum to the list.
  3. Find the biggest element in the list.