Considering 4-digit primes containing repeated digits it is clear that they cannot all be the same: 1111 is divisible by 11, 2222 is divisible by 22, and so on. But there are nine 4-digit primes containing three ones:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111
We shall say that M(n, d) represents the maximum number of repeated digits for an n-digit prime where d is the repeated digit, N(n, d) represents the number of such primes, and S(n, d) represents the sum of these primes.
So M(4, 1) = 3 is the maximum number of repeated digits for a 4-digit prime where one is the repeated digit, there are N(4, 1) = 9 such primes, and the sum of these primes is S(4, 1) = 22275. It turns out that for d = 0, it is only possible to have M(4, 0) = 2 repeated digits, but there are N(4, 0) = 13 such cases.
In the same way we obtain the following results for 4-digit primes.
For d = 0 to 9, the sum of all S(4, d) is 273700.
Find the sum of all S(10, d).
In [ ]:
A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
|
|
|
||||||||||||||||||||||
In [1]:
open Euler
let p114() =
let n = 50
let cache = Array.init (n+1) (fun i -> if i=3 then 1L else 0L)
let rec count(gap) =
if gap<3 then 0L
else
if cache.[gap] = 0L then
let total = ref 0L
for len in 3..gap do
let maxpos = gap - len + 1
total := !total + int64 maxpos
for pos in 0..maxpos do
total := !total + count(gap - len - pos - 1)
cache.[gap] <- !total
cache.[gap]
1L + count(n)
Euler.Timer(p114)
Out[1]:
NOTE: This is a more difficult version of problem 114.
A row measuring n units in length has red blocks with a minimum length of m units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square.
Let the fill-count function, F(m, n), represent the number of ways that a row can be filled.
For example, F(3, 29) = 673135 and F(3, 30) = 1089155.
That is, for m = 3, it can be seen that n = 30 is the smallest value for which the fill-count function first exceeds one million.
In the same way, for m = 10, it can be verified that F(10, 56) = 880711 and F(10, 57) = 1148904, so n = 57 is the least value for which the fill-count function first exceeds one million.
For m = 50, find the least value of n for which the fill-count function first exceeds one million.
In [4]:
open Euler
let p115() =
let m = 50
let maxN = pown 10 6
let cache = Array.zeroCreate maxN
cache.[m] <- 1
let rec count(gap) =
if gap<m then 0
else
if cache.[gap]=0 then
let total = ref 0
for len in m..gap do
let maxpos = gap - len + 1
total := !total + maxpos
for pos in 0..maxpos do
total := !total + count(gap - len - pos - 1)
cache.[gap] <- !total
cache.[gap]
let answer = ref 50
while (1+count(!answer)) <= maxN do
incr answer
!answer
Euler.Timer(p115)
Out[4]:
A row of five black square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).
If red tiles are chosen there are exactly seven ways this can be done.
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
If green tiles are chosen there are three ways.
|
|
|
|
||||||||||||||||
And if blue tiles are chosen there are two ways.
|
|
|
||||||||||
Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the black tiles in a row measuring five units in length.
How many different ways can the black tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?
In [1]:
open Euler
let p116() =
let tiles = 50
let getSolutions i =
let cache = Array.zeroCreate(tiles+1)
let rec loop m =
if (i > m) then 0L
else
if cache.[m] = 0L then
cache.[m] <- [0..m-i] |> Seq.sumBy(fun s -> 1L + loop (m-s-i))
cache.[m]
loop tiles
[2..4] |> Seq.sumBy getSolutions
Euler.Timer(p116)
Out[1]:
Using a combination of black square tiles and oblong tiles chosen from: red tiles measuring two units, green tiles measuring three units, and blue tiles measuring four units, it is possible to tile a row measuring five units in length in exactly fifteen different ways.
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||
How many ways can a row measuring fifty units in length be tiled?
In [2]:
open Euler
let p117() =
let n = 50
let m = [2..4]
let cache = Array.init (n+1) (fun i -> if i=m.[0] then 1L else 0L)
let rec count(gap) =
if gap<m.[0] then 0L
else
if cache.[gap] = 0L then
let total = ref 0L
for len in m do
let maxpos = gap - len + 1
total := !total + int64 maxpos
for pos in 0..maxpos do
total := !total + count(gap - len - pos)
cache.[gap] <- !total
cache.[gap]
1L + count(n)
Euler.Timer(p117)
Out[2]:
In [ ]: