Let $p(n)$ represent the number of different ways in which $n$ coins can be separated into piles. for example, five coins can be separated into piles in exactly seven different ways, so $p(5)=7$. \[\bigcirc\bigcirc\bigcirc\bigcirc\bigcirc \\ \bigcirc\bigcirc\bigcirc\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\bigcirc\quad\bigcirc\bigcirc \\ \bigcirc\bigcirc\bigcirc\quad\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\quad\bigcirc\bigcirc\quad\bigcirc \\ \bigcirc\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc \\ \bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\quad\bigcirc\]
Find the least value of $n$ for which $p(n)$ is divisible by one million.
It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.
We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.
Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).
If we are presented with the first $k$ terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.
As an example, let us consider the sequence of cube numbers. This is defined by the generating function, $u_n=n^3: 1,8,27,64,125,216,\dots$.
Suppose we were only given the first two terms of this sequence. Working on the principle that “simple is best” we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.
By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles:
Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.
In the game, Monopoly, the standard board is set up in the following way:
Monopoly board
A player starts on the GO square and adds the scores on two 6-sided dice to determine the number of squares they advance in a clockwise direction. Without any further rules we would expect to visit each square with equal probability: 2.5%. However, landing on G2J (Go To Jail), CC (community chest), and CH (chance) changes this distribution.
In addition to G2J, and one card from each of CC and CH , that orders the player to go directly to jail, if a player rolls three consecutive doubles, they do not advance the result of their 3rd roll. Instead they proceed directly to jail.
At the beginning of the game, the CC and CH cards are randomly shuffled. When a player lands on CC or CH they take a card from the top of the respective pile and, after following the instructions, it is returned to the bottom of the pile. There are sixteen cards in each pile, but for the purpose of this problem we are only concerned with cards that order a movement; any instruction not concerned with movement will be ignored and the player will remain on the CC/CH square.
- Community Chest (2/16 cards):
- Chance (10/16 cards):
- Advance to GO
- Go to JAIL
- Go to C1
- Go to E3
- Go to H2
- Go to R1
- Go to next R (railway company)
- Go to next R
- Go to next U (utility company)
- Go back 3 squares
The heart of this problem concerns the likelihood of visiting a particular square. That is, the probability of finishing at that square after a roll. For this reason it should be clear that, with the exception of G2J for which the probability of finishing is zero, the CH squares will have the lowest probabilities, as 5/8 request a movement to another square, and it is the final square that the player finishes on that we are interested in. We shall make no distinction between “Just Visiting” and being to sent to JAIL, and we shall also ignore the rule about requiring a double to “get out of jail”, assuming they pay to get out on their next turn.
By starting on GO and numbering the squares sequentially from 00 to 39 we can concatenate these two-digit numbers to produce strings that correspond with sets of squares.
Statistically it can be shown that the three most popular squares, in order, are JAIL (6.24%) = Square 10, E3 (3.18%) = Square 24, and GO (3.09%) = Square 00. So these three most popular squares can be listed with the six-digit modal string: 102400.
If, instead of using two 6-sided dice, two 4-sided dice are used, find the six-digit modal string.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427. \[\begin{pmatrix} \color{red}{\mathbf{131}} & 673 & 234 & 103 & 18 \\ \color{red}{\mathbf{201}} & \color{red}{\mathbf{96}} & \color{red}{\mathbf{342}} & 965 & 150 \\ 630 & 803 & \color{red}{\mathbf{746}} & \color{red}{\mathbf{422}} & 111 \\ 537 & 699 & 497 & \color{red}{\mathbf{121}} & 956 \\ 805 & 732 & 524 & \color{red}{\mathbf{37}} & \color{red}{\mathbf{331}} \end{pmatrix}\]
Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and “Save Link/Target As…”), a 31K text file containing an 80 by 80 matrix.
It is possible to write five as a sum in exactly six different ways: \[\begin{aligned} &4 + 1 \\ &3 + 2 \\ &3 + 1 + 1 \\ &2 + 2 + 1 \\ &2 + 1 + 1 + 1 \\ &1 + 1 + 1 + 1 + 1 \end{aligned}\]
How many different ways can one hundred be written as a sum of at least two positive integers?
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.
The square root of two is 1.41421356237309504880…, and the digital sum of the first one hundred decimal digits is 475.
For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.
Euler’s Totient function, $\phi(n)$ [sometimes called the phi function], is used to determine the number of numbers less than $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$.
| $n$ | Relatively Prime | $\phi(n)$ | $n/\phi(n)$ |
|---|
| 2 | 1 | 1 | 2 |
| 3 | 1,2 | 2 | 1.5 |
| 4 | 1,3 | 2 | 2 |
| 5 | 1,2,3,4 | 4 | 1.25 |
| 6 | 1,5 | 2 | 3 |
| 7 | 1,2,3,4,5,6 | 6 | 1.1666… |
| 8 | 1,3,5,7 | 4 | 2 |
| 9 | 1,2,4,5,7,8 | 6 | 1.5 |
| 10 | 1,3,7,9 | 4 | 2.5 |
It can be seen that $n=6$ produces a maximum $n/\phi(n)$ for $n\leq 10$.
Find the value of $n\leq 1\,000\,000$ for which $n/\phi(n)$ is a maximum.
Consider the fraction, $n/d$, where $n$ and $d$ are positive integers. If $n<d$ and $HCF(n,d)=1$, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for $d\leq 8$ in ascending order of size, we get: \[\frac{1}{8},\frac{1}{7},\frac{1}{6},\frac{1}{5},\frac{1}{4},\frac{2}{7},\frac{1}{3},\frac{3}{8},\mathbf{\frac{2}{5}}, \frac{3}{7},\frac{1}{2},\frac{4}{7},\frac{3}{5},\frac{5}{8},\frac{2}{3},\frac{5}{7},\frac{3}{4},\frac{4}{5},\frac{5}{6},\frac{6}{7},\frac{7}{8}\]
It can be seen that $2/5$ is the fraction immediately to the left of $3/7$.
By listing the set of reduced proper fractions for $d\leq 1\,000\,000$ in ascending order of size, find the numerator of the fraction immediately to the left of $3/7$.
