Efficient exponentiation

Problem 122

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]:
val it : int * float = (1582, 0.0808332)

Ordered radicals

Problem 124

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]:
val it : int * float = (21417, 3.0745379)

Palindromic sums

Problem 125

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]:
val it : int64 * float = (2906969179L, 0.7995607)

In [ ]: