In the following equation $x$, $y$, and $n$ are positive integers. \[\frac{1}{x} + \frac{1}{y} = \frac{1}{n}\]

For $n=4$ there are exactly three distinct solutions: \[\begin{aligned} \frac{1}{5} + \frac{1}{20} &= \frac{1}{4} \\ \frac{1}{6} + \frac{1}{12} &= \frac{1}{4} \\ \frac{1}{8} + \frac{1}{8} &= \frac{1}{4} \end{aligned}\]

What is the least value of $n$ for which the number of distinct solutions exceeds one-thousand?

This problem is an easier verison of #110 - Diophantine reciprocals II; it is strongly advised that you solve this one first.

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way: \[28 = 2^2+2^3+2^4 \\ 33 = 3^2+2^3+2^4 \\ 49 = 5^2+2^3+2^4 \\ 47 = 2^2+3^3+2^4\]

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

Euler’s Totient function, $\phi(n)$ [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to $n$ which are relatively prime to $n$. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, $\phi(9)=6$. The number 1 is considered to be relatively prime to every positive number, so $\phi(1)=1$.

Interestingly, $\phi(87109)=79180$, and it can be seen that $87109$ is a permutation of $79180$.

Find the value of $n, 1<n<10^7$, for which $\phi(n)$ is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum.

Consider the following “magic” 3-gon ring, filled with numbers 1 to 6, and each line adding to nine.

Working clockwise, and starting from the group of three with the numerically lowest external node (4,3,2 in this example), each solution can be described uniquely. For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.

It is possible to complete the ring with four different totals: 9, 10, 11, and 12. There are eight solutions in total.

Total	Solution Set
9	4,2,3; 5,3,1; 6,1,2
9	4,3,2; 6,2,1; 5,1,3
10	2,3,5; 4,5,1; 6,1,3
10	2,5,3; 6,3,1; 4,1,5
11	1,4,6; 3,6,2; 5,2,4
11	1,6,4; 5,4,2; 3,2,6
12	1,5,6; 2,6,4; 3,4,5
12	1,6,5; 3,5,4; 2,4,6

By concatenating each group it is possible to form 9-digit strings; the maximum string for a 3-gon ring is 432621513.

Using the numbers 1 to 10, and depending on arrangements, it is possible to form 16- and 17-digit strings. What is the maximum 16-digit string for a “magic” 5-gon ring?

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.