The most naive way of computing $n^{15}$ requires fourteen multiplications:
$$n × n × ... × n = n^{15}$$But using a "binary" method you can compute it in six multiplications:
$$n × n = n^2$$$$n^2 × n^2 = n^4$$$$n^4 × n^4 = n^8$$$$n^8 × n^4 = n^{12}$$$$n^{12} × n^2 = n^{14}$$$$n^{14} × n = n^{15}$$However it is yet possible to compute it in only five multiplications:
$$n × n = n^2$$$$n^2 × n = n^3$$$$n^3 × n^3 = n^6$$$$n^6 × n^6 = n^{12}$$$$n^{12} × n^3 = n^{15}$$We shall define $m(k)$ to be the minimum number of multiplications to compute $n^k$; for example $m(15) = 5$.
For $1 ≤ k ≤ 200$, find $∑ m(k)$.
In [1]:
open Euler
let p122() =
let limit = 200
let cost = Array.zeroCreate (limit + 1)
let path = Array.zeroCreate (limit + 1)
let rec Backtrack(power, depth) =
if power > limit || depth > cost.[power] then ()
else
cost.[power] <- depth
path.[depth] <- power
for i in depth .. -1 .. 0 do
Backtrack(power + path.[i], depth + 1)
let result = ref 0
for i = 0 to limit do
cost.[i] <- System.Int32.MaxValue
Backtrack(1, 0)
for i = 1 to limit do
result := !result + cost.[i]
!result
Euler.Timer(p122)
Out[1]:
The radical of $n$, $rad(n)$, is the product of the distinct prime factors of $n$. For example, $504 = 23 × 32 × 7$, so $rad(504) = 2 × 3 × 7 = 42$.
If we calculate $rad(n)$ for $1 ≤ n ≤ 10$, then sort them on $rad(n)$, and sorting on $n$ if the radical values are equal, we get:
Unsorted |
Sorted |
||||
n |
rad(n) |
n |
rad(n) |
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^{th}$ element in the sorted $n$ column; for example, $E(4) = 8$ and $E(6) = 9$.
If $rad(n)$ is sorted for $1 ≤ n ≤ 100000$, find $E(10000)$.
In [1]:
open Euler
let p124() =
let rad (n:int) = Math.FactorInteger(n) |> Seq.map fst |> Seq.fold ( * ) 1
seq { for i in 1..100000 -> i, rad i }
|> Seq.sortBy snd
|> Seq.nth (10000-1)
|> fst
Euler.Timer(p124)
Out[1]:
The palindromic number $595$ is interesting because it can be written as the sum of consecutive squares: $6^2 + 7^2 + 8^2 + 9^2 + 10^2 + 11^2 + 12^2$.
There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is $4164$. Note that $1 = 0^2 + 1^2$ has not been included as this problem is concerned with the squares of positive integers.
Find the sum of all the numbers less than $10^8$ that are both palindromic and can be written as the sum of consecutive squares.
In [2]:
open Euler
let p125() =
let maxN = pown 10L 8
let isPalindrome (n:int64) = Math.Reverse(n) = n
let sqrSum i j =
let acc = ref (0L)
for k = i to i + j - 1 do
acc := !acc + pown (int64 k) 2
!acc
set [ for i in 1 .. int(Math.ISqrt(maxN)) do
let j = ref 2
let next = ref (sqrSum i !j)
while !next < maxN do
if isPalindrome !next then yield !next
incr j
next := sqrSum i !j ]
|> Seq.sum
Euler.Timer(p125)
Out[2]:
In [ ]: