Let $f(N)$ be the number of points with integer coordinates that are on a circle passing through $(0,0),(N,0),(0,N)$, and $(N,N)$.

It can be done shown that $f(10000)=36$.

What is the sum of all positive integers $N\leq 10^{11}$ such that $f(N)=420$?

A particular school offers cash rewards to children with good attendance and punctuality. If they are absent for three consecutive days or late on more than one occasion then they forfeit their prize.

During the $n$-day period a trinary string is formed for each child consisting of L’s (late), O’s (on time), and A’s (absent).

Although there are eight-one trinary strings for a 4-day period that can be formed, exactly forty-three strings would lead to a prize:

    OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA
OAOL OAAO OAAL OALO OALA OLOO OLOA OLAO OLAA AOOO
AOOA AOOL AOAO AOAA AOAL AOLO AOLA AAOO AAOA AAOL
AALO AALA ALOO ALOA ALAO ALAA LOOO LOOA LOAO LOAA
LAOO LAOA LAAO

How many “prize” strings exist over a 30-day period?

A positive integer $n$ is called squarefree, if no square of a prime divides $n$, thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12.

How many squarefree numbers are there below $2^{50}$?

Let $(a,b,c)$ represent the three sides of a right angle triangle with integral length sides. It is possible to place four such triangles together to form a square with length $c$.

For example, (3, 4, 5) triangles can be placed together to form a 5 by 5 square with a 1 by 1 hole in the middle and it can be seen that the 5 by 5 square can be tiled with twenty-five 1 by 1 squares.

However, if (5, 12, 13) triangles were used, then the hole would measure 7 by 7 and these could not be used to tile the 13 by 13 square.

Given that the perimeter of the right triangle is less than one-hundred million, how many Pythagorean triangles would allow such a tiling to take place?

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?