## Project Euler |

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.

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

listbe a list of all possible 3-digit sequences, where each one has the following properties:_{D}

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

Din the problem text, generatelist. That is:_{D}

list= {012, 014, 016, ... 984, 986}_{2}list= {012, 015, 018, ... 984, 987}_{3}list= {015, 020, 025, ... 980, 985}_{5}list= {014, 021, 028, ... 980, 987}_{7}list= {132, 143, 154, ... 957, 968}_{11}list= {013, 026, 039, ... 962, 975}_{13}list= {017, 034, 051, ... 952, 986}_{17}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 d

_{2}to d_{10}) as shown in the example. After filling in the missing first digit d_{1}, a 10-digit sequence is formed.Using this method of generating 10-digit sequences, one solution is:

- Let
sum= 0.- For each
xin_{2}list,_{2}xin_{3}list,_{3}xin_{5}list, etc.:_{5}

- 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.
x[0]=_{11}x[1] and_{7}x=_{11}[1]x[2] must both be true). If not, continue to the next element of the current list._{7}- Let
panbe an empty 10-digit sequence.- Populate the last 9 elements of
panlike so:{ _,x[0],_{2}x[1],_{2}x[2],_{2}x[0],_{7}x[1],_{7}x[2],_{7}x[0],_{17}x[1],_{17}x[2] }_{17}- If any digits repeat, then the sequence isn't pandigital. Continue.
- Otherwise, fill in the missing 1st digit. The sequence is now a valid 10-digit pandigital.
- Convert
paninto an integer and add it tosum.sum.

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.

- Create a list of numbers from 1 to an upper limit. Call this list
numbers.- By definition, all prime numbers have only 1 distinct prime factor. Therefore, we need only test terms which are nonprime. Split
numbersinto two lists: primes and nonprimes. Call these listsprimesandnonprimes.- 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 listconsec_nonprimes.When the upper limit is 500k, this reduces the list to 407k terms, improving run time by a fair amount.

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

- 56003
- 56113
- 56223
- 56333
- 56443
- 56553
- 56663
- 56773
- 56883
- 56993
anywherein 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.

- *42
- 9*2
- 94*
- **2
- 9**
- *4*
One approach is to use a boolean array to represent the swap positions for a number, in which the digits located at

trueindeces get swapped with 0-9 and those atfalseindeces remain the same. When applied to 942, the collection of boolean arrays is as follows:Incidentally, boolean arrays can be written as binary sequences, e.g. {

*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}true false true} = 101 = 5_{2}. 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 everyN-bit binary sequence for a number which consists ofNdigits, i.e. every 3-bit sequence for 942.Using binary sequences, one possible solution is:

- Create a list of primes from 1 to a certain limit (1 million is sufficient).
- For each
xon the list:

- Get the digits of
x.- Let
base= 1.- Get
base's binary sequence. If necessary, prepend 0s until it has as many bits asxhas digits.- If
base's binary sequence consists entirely of 1s, continue/skip to the nextx.- Perform digit swaps on
xin accordance to the binary sequence/boolean array.Exceptions:

- Skip if the index is 0 and the replacement digit is 0, as this would cause the resulting number to be 1 fewer digit in length.
- Skip if the index is the final one, as this would cause the resulting family to end with the digits 0-9; 5 members would be even and 5 would be odd. Since the goal is to find 8 primes and all primes but 2 are odd, this case is guaranteed to fail.
- If the digit swaps performed in the above step produced a family with 8 or more prime members, the problem is solved.
- Otherwise, increment
baseand repeat from step 3.

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 members
don'thave to be in any particular polygonal order, e.g. there can be a square member followed by an octagonal member.- The members
canhave more than one polygonal type, e.g. a member can be 8646, which is both triangular and hexagonal.- The members
cannothave leading zeros; each one must be between 1000 and 9999.- Each member forms a left-to-right cycle with
exactly oneother member (this is demonstrated, but not clarified, in the example). If 8646 is a member, then there isexactly onemember that begins with 46 andexactly onemember that ends with 86.The algorithm used in my solution is as follows:

- Create 6 separate lists representing the polygonal types (use only 4-digit numbers).
- Create a master list which contains every item in the above lists, without repeats.
- Create an empty list for storing 6-member sets. Call this list
solutions.- For each
xon the master list:

- Create an empty set which acts as an attempted solution. Call it
solution.- Append
xtosolution.- For each
itemon the master list:

- If
itemis insolution, skip it.- If the final member of
solutionforms a left-to-right cycle withitem(if the final member's last 2 digits are the same asitem's first 2 digits), then appenditemtosolution.- Reset the current loop (start again from index 0).
- If
solutiondoesn't have exactly 5 members at this point, it fails. Skip.- For each
yon the master list:

- If
ywould turnsolutioninto a cyclic set (ify's first 2 digits are the same as the final member's last 2 digits,andy's last 2 digits are the same as the first member's first 2 digits), appendytosolution. Break.- If
solutionhas 6 members, it's a possible solution! Append it tosolutions.- For each
solutioninsolutions:

- If
solutionhas 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's difficulty rating is 25%, the highest one yet.

The given Diophantine equation is:

x^{2}-Dy^{2}= 1The goal is to plug in every nonsquare

Dfrom 1 to 1000 and solve forxandy, wherexmust be as small as possible. Unfortunately, this problem can't be solved with brute force in a realstic amount of time because many values ofxend up being large integers which may take hours to compute (e.g.x= 159150073798980475849 whenD= 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:

- Create a list for storing integer pairs.
- For every
Dfrom 1 to 1000:

- If
Dis a perfect square, skip.- Let
N= 1.- Find the
Nth convergent of √D. Let the numerator bexand the denominator bey.- Plug
D,x, andyinto the equation.- If
D,x, andydon'tsatisfy the equation: incrementNand repeat from step 3.- Otherwise, append the current (
D,x) pair to the list.- Find the (
D,x) pair with the largestx.

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

or However, this solution is inefficient because it disregards the

orientationof 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 everynth 10-digit pandigital fromn= 1 ton= 10!, the same solution will be found 5 times as 5 different permutations. This can be circumvented by incrementingnby 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, orEhold 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:

- Create an empty list of bignums.
- For
n= 1 ;n<= 10! ;n+= 4:

- Generate the
nth 10-digit pandigital.- Replace 0 with 10.
- If 10 is
notlocated at index 0, 1, 2, 3, or 4, then this sequence won't form a final answer which is 16 digits long. Skip.- If the sequence satisfies the 5-gon ring equalities:

- Rewrite the sequence into the comma/semicolon format shown in the problem text. It must be ordered clockwise.
- Convert it into a bignum.
- Append the bignum to the list.
- Find the biggest element in the list.