Consider the infinite polynomial series $A_G(x) = xG_1+x^2G_2+x^3G_3+\cdots$, where $G_k$ is the $k$th term of the second order recurrence relation $G_k=G_{k-1}+G_{k-2}$, $G_1=1$ and $G_2=4$; that is, $1,4,5,9,14,23, \dots$.

For this problem we shall be concerned with values of $x$ for which $A_G(x)$ is a positive integer.

The corresponding values of $x$ for the first five natural numbers are shown below.

$x$	$A_G(x)$
$\frac{\sqrt{5}-1}{4}$	1
$\frac{2}{5}$	2
$\frac{\sqrt{22}-2}{6}$	3
$\frac{\sqrt{137}-5}{14}$	4
$\frac{1}{2}$	5

We shall call $A_G(x)$ a golden nugget if $x$ is rational, because they become increasingly rarer; for example, the 20th golden nugget is 211345365.

Find the sum of the first thirty golden nuggets.

Consider the infinite polynomial series $A_F(x) = xF_1 + x^2F_2 + x^3F_3 + \dots$, where $F_k$ is the $k^{\text{th}}$ term in the Fibonacci sequence: 1, 1, 2, 3, 5, 8, …; that is, $F_k = F_{k-1} + F_{k-2}$, $F_1=1$ and $F_2=1$.

For this problem we shall be interested in values of $x$ for which $A_F(x)$ is a positive integer.

Surprisingly, \[\begin{aligned} A_F\left(\frac{1}{2}\right) &= \left(\frac{1}{2}\right)(1) + \left(\frac{1}{2}\right)^2(1) + \left(\frac{1}{2}\right)^3(2) + \left(\frac{1}{2}\right)^4(3) + \cdots \\ &= \frac{1}{2} + \frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \frac{5}{32} + \cdots \\ &= 2 \end{aligned}\]

The corresponding values of $x$ for the first five natural numbers are shown below.

$\mathbf{x}$	$\mathbf{A_F(x)}$
$\sqrt{2}-1$	1
$\frac{1}{2}$	2
$\frac{\sqrt{13}-2}{3}$	3
$\frac{\sqrt{89}-5}{8}$	4
$\frac{\sqrt{34}-3}{5}$	5

We shall call $A_F(x)$ a golden nugget if $x$ is rational, because they become increasingly rarer; for example, the 10th golden nugget is 74049690.

Find the 15th golden nugget.

The minimum number of cubes to cover every visible face on a cuboid measuring 3 x 2 x 1 is twenty-two.

If we then add a second layer to the solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring 5 x 1 x 1 also requires twenty-two cubes; similarly the first layer on cuboids measuring 5 x 3 x 1, 7 x 2 x 1, 11 x 1 x 1 all contain forty-six cubes.

We shall define $C(n)$ to represent the number of cuboids that contain $n$ cubes in one of its layers. So $C(22) = 2, C(46) = 4, C(78) = 5$, and $C(118) = 8$.

It turns out that 154 is the least value of $n$ for which $C(n) = 10$.

Find the least value of $n$ for which $C(n) = 1000$.

The radical of $n$, $\text{rad}(n)$, is the product of the distinct prime factors of $n$. For example, $504=2^3\times3^2\times7$, so $\text{rad}(504)=2\times3\times7=42$.

If we calculate $\text{rad}(n)$ for $1\leq n\leq 10$, then sort them on $\text{rad}(n)$, and sorting on $n$ if the radical values are equal we get:

Unsorted			Sorted
$\mathbf{n}$	$\textbf{rad}\mathbf{(n)}$		$\mathbf{n}$	$\textbf{rad}\mathbf{(n)}$	$\mathbf{k}$
1	1		1	1	1
2	2		2	2	2
3	3		4	2	3
4	2		8	2	4
5	5		3	3	5
6	6		9	3	6
7	7		5	5	7
8	2		6	6	8
9	3		7	7	9
10	10		10	10	10

Let $E(k)$ be the $k^{\text{th}}$ element in the sorted $n$ column; for example, $E(4) = 8$ and $E(6) = 9$.

If $\text{rad}(n)$ is sorted for $1\leq n \leq 100000$, find $E(10000)$.

A spider, S, sits in one corner of a cuboid room, measuring 6 by 5 by 3, and a fly, F, sits in the opposite corner. By travelling on the surfaces of the room the shortest “straight line” distance from S to F is 10 and the path is shown on the diagram.

However, there are up to three “shortest” path candidates for any given cuboid and the shortest route doesn’t always have integer length.

It can be shown that there are exactly 2060 distinct cuboids, ignoring rotations, with integer dimensions, up to a maximum size of $M$ by $M$ by $M$, for which the shortest route has integer length when $M=100$. This is the least value of $M$ for which the number of solutions first exceeds two thousand; the number of solutions when $M=99$ is 1975.

Find the least value of $M$ such that the number of solutions first exceeds one million.

The number 145 is well known for the property that the sum of the factorial of its digits is equal to 145: \[1! + 4! + 5! = 1 + 24 + 120 = 145\]

Perhaps less well known is 169, in that it produces the longest chain of numbers that link back to 169; it turns out that there are only three such loops that exist: \[\begin{aligned} & 169 \rightarrow 363601 \rightarrow 1454 \rightarrow 169 \\ & 871 \rightarrow 45361 \rightarrow 871 \\ & 872 \rightarrow 45362 \rightarrow 872 \end{aligned}\]

It is not difficult to prove that EVERY starting number will eventually get stuck in a loop. For example, \[\begin{aligned} & 69 \rightarrow 363600 \rightarrow 1454 \rightarrow 169 \rightarrow 363601\,(\rightarrow 1454) \\ & 78 \rightarrow 45360 \rightarrow 871 \rightarrow 45361\,(\rightarrow 871) \\ & 540 \rightarrow 145\,(\rightarrow 145) \end{aligned}\]

Starting with 69 produces a chain of five non-repeating terms, but the longest non-repeating chain with a starting number below one million is sixty terms.

How many chains, with a starting number below one million, contain exactly sixty non-repeating terms?

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Type	Formula	Series
Triangle	$P_{3,n}=\frac{1}{2}n(n+1)$	1, 3, 6, 10, 15, …
Square	$P_{4,n}=n^2$	1, 4, 9, 16, 25, …
Pentagonal	$P_{5,n}=\frac{1}{2}n(3n-1)$	1, 5, 12, 22, 35, …
Hexagonal	$P_{6,n}=n(2n-1)$	1, 6, 15, 28, 45, …
Heptagonal	$P_{7,n}=\frac{1}{2}n(5n-3)$	1, 7, 18, 34, 55, …
Octagonal	$P_{8,n}=n(3n-2)$	1, 8, 21, 40, 65

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with first).
2. Each polygonal type: triangle ($P_{3,127}=8128$), square ($P_{4,91}=8281$), and pentagonal ($P_{5,44}=2882$), is represented by a different number in the set.
3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.

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 is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

As $n$ increases, the proportion of bouncy numbers below $n$ increases such that there are only 12951 numbers below one-million that are not bouncy and only 277032 non-bouncy numbers below $10^{10}$.

How many numbers below a googol ($10^{100}$) are not bouncy?

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 is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a “bouncy” number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy. In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.

Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.