It can be seen that the number, 125874, and its double 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, $x$, such that $2x,3x,4x,5x$ and $6x$, contain the same digits.

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 always a “best” way of writing a particular number.

For example, it would appear that there are at least six ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

However, according to the rules only XIIIIII and XVI are valid, and the last example is considered to be the most efficient, as it uses the least number of numerals.

The 11K text file, roman.txt (right click and ‘Save Link/Target As…’), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; see About… Roman Numerals for the definitive rules for this problem.

Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

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 characters; the expected reply would be: 317.

The text file, keylog.txt, contains fifty successful login attempts.

Given that the three characters are always asked for in order, analyze the file so as to determine the shortest possible secret passcode of unknown length.

The square root of 2 can be written as an infinite continued fraction. \[\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2+\dots}}}}\]

The infinite continued fraction can be written, $\sqrt{2}=[1;(2)]$, $(2)$ indicates that 2 repeats ad infinitum. In a similar way, $\sqrt{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 the convergents for $\sqrt{2}$. \[\begin{aligned} 1 + \frac{1}{2} &= \frac{3}{2} \\ 1 + \frac{1}{2 + \frac{1}{2}} &= \frac{7}{5} \\ 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} &= \frac{17}{12} \\ 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} &= \frac{41}{29} \end{aligned}\]

Hence the sequence of the first ten convergents for $\sqrt{2}$ are: \[1,\frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378}, \dots\]

What is most surprising is that the important mathematical constant, \[e=[2;1,2,1,1,4,1,1,6,1,\dots,1,2k,1,\dots]\]

The first ten terms in the sequence of convergents for $e$ are: \[2,3,\frac{8}{3},\frac{11}{4},\frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}, \frac{1264}{465}, \frac{1457}{536},\dots\]

The sum of digits in the numerator of the $\text{10}^\text{th}$ convergent is $1+4+5+7=17$.

Find the sum of digits in the numerator of the $100^\text{th}$ convergent of the continued fraction for $e$.

All square roots are periodic when written as continued fractions and can be written in the form: \[\sqrt{N}=a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3+\dots}}}\]

For example, let us consider $\sqrt{23}$: \[\sqrt{23}=4+\sqrt{23}-4=4 + \frac{1}{\frac{1}{\sqrt{23} - 4}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}\]

If we continue we would get the following expansion: \[\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \dots}}}}\]

The process can be summarized as follows: \[\begin{aligned} a_0 &= 4, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_1 &= 1, \frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\ a_2 &= 3, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_3 &= 1, \frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\ a_4 &= 8, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_5 &= 1, \frac{7}{\sqrt{23}-3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\ a_6 &= 3, \frac{1}{\sqrt{23}-4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\ a_7 &= 1, \frac{7}{\sqrt{23}-4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \end{aligned}\]

It can be seen that the sequence is repeating. For conciseness, we use the notation $\sqrt{23}=[4;(1,3,1,8)]$, to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representation of (irrational) square roots are: \[\begin{aligned} \sqrt{2} &= [1;(2)], \text{period=1} \\ \sqrt{3} &= [1:(1,2)], \text{period=2} \\ \sqrt{5} &= [2;(4)], \text{period=1} \\ \sqrt{6} &= [2;(2,4)], \text{period=2} \\ \sqrt{7} &= [2;(1,1,1,4)], \text{period=4} \\ \sqrt{8} &= [2;(1,4)], \text{period=2} \\ \sqrt{10} &= [3;(6)], \text{period=1} \\ \sqrt{11} &= [3;(3,6)], \text{period=2} \\ \sqrt{12} &= [3;(2,6)], \text{period=2} \\ \sqrt{13} &= [3;(1,1,1,1,6)], \text{period=5} \end{aligned}\]

Exactly four continued fractions, for $N\leq 13$, have an odd period.

How many continued fractions for $N\leq10\,000$ have an odd period?

In the card game poker, a hand consists of five cards and are ranked, from lowest to highest, in the following way:

• High Card: Highest value card.
• One Pair: Two cards of the same value.
• Two Pairs: Two different pairs.
• Three of a Kind: Three cards of the same value.
• Straight: All cards are consecutive values.
• Flush: All cards of the same suit.
• Full House: Three of a kind and a pair.
• Four of a Kind: Four cards of the same value.
• Straight Flush: All cards are consecutive values of the same suit.
• Royal Flush: Ten, Jack, Queen, King, Ace, in same suit.

The cards are valued in the order: 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, Ace.

If two players have the same ranked hands then the rank made up of the highest value wins; for example, a pair of eights beats a pair of fives (see example 1 below). But if two ranks tie, for example, both players have a pair of queens, then highest cards in each hand are compared (see example 4 below); if the highest cards tie then the next highest cards are compared, and so on.

Consider the following 5 hands dealt to two players:

Hand	Player 1	Player 2	Winner
1	5H 5C 6S 7S KD Pair of Fives	2C 3S 8S 8D TD Pair of Eights	Player 2
2	5D 8C 9S JS AC Highest card Ace	2C 5C 7D 8S QH Highest card Queen	Player 1
3	2D 9C AS AH AC Three Aces	3D 6D 7D TD QD Flush with Diamonds	Player 2
4	4D 6S 9H QH QC Pair of Queens Highest card Nine	3D 6D 7H QD QS Pair of Queens Highest card Seven	Player 1
5	2H 2D 4C 4D 4S Full House with Three Fours	3C 3D 3S 9S 9D Full House with Three Threes	Player 1

The file, poker.txt, contains one-thousand random hands dealt to two players. Each line of the file contains ten cards (separated by a single space): the first five are Player 1’s cards and the last five are Player 2’s cards, You can assume that all hands are valid (no invalid characters or repeated cards), each player’s hands are in no specific order, and in each hand there is a clear winner.

How many hands does Player 1 win?

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, \[44\rightarrow 32\rightarrow 13\rightarrow 10\rightarrow\mathbf{1}\rightarrow\mathbf{1} \\ 85\rightarrow\mathbf{89}\rightarrow145\rightarrow 42\rightarrow20 \rightarrow4\rightarrow16\rightarrow37\rightarrow58\rightarrow\mathbf{89}\]

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

The prime 41, can be written as the sum of six consecutive primes: \[41=2+3+5+7+11+13\]

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

Note that we are looking for the longest sum, not the largest sum. Therefore, since we can generate a list of primes, we will start at 2, and keep adding terms consecutively. If we reach a prime, then we update the length of the sum. We keep going until our sum exceeds 1 million. Once we’re done starting our sum from 2, we then move to starting the sum with 3. However, since we have saved the longest sum length so far, we have to add that many terms i.e. If the longest sum starting with 2 is 200 digits long, then we start checking sums starting from 3 from 201 digits onward. Like this, we check through all the primes.

The following undirected network consists of seven vertices and twelve edges with a total weight of 243.

The same network can be represented by the matrix below.

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

However, it is possible to optimise the network by network by removing some edges and still ensure that all points on the network remain connected. The network which achieves the maximum saving is shown below. It has a weight of 93, representing a saving of 243 - 93 = 150 from the original network.

Using network.txt (right click and ‘Save Link/Target As…’), a 6K text file containing a network with forty vertices, and given in matrix form, find the maximum saving which can be achieved by removing redundant edges whilst ensuring that the network remains connected.

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers of are permutations of one another.

There are no arithmetic sequences made up 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?