Project Euler Problem 29 Solution

Question

Consider all integer combinations of aba^b for 2a52 \leq a \leq 5 and 2b52 \leq b \leq 5:

22=423=824=1625=3232=933=2734=8135=24342=1643=6444=25645=102452=2553=12554=62555=3125\displaystyle \begin{aligned} & 2^2 = 4\text{, } 2^3 = 8\text{, } 2^4 = 16\text{, } 2^5 = 32 \\ & 3^2 = 9\text{, } 3^3 = 27\text{, } 3^4 = 81\text{, } 3^5 = 243 \\ & 4^2 = 16\text{, } 4^3 = 64\text{, } 4^4 = 256\text{, } 4^5 = 1024 \\ & 5^2 = 25\text{, } 5^3 = 125\text{, } 5^4 = 625\text{, } 5^5 = 3125 \end{aligned}

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

48916252732648112524325662510243125\displaystyle 4\text{, } 8\text{, } 9\text{, } 16\text{, } 25\text{, } 27\text{, } 32\text{, } 64\text{, } 81\text{, } 125\text{, } 243\text{, } 256\text{, } 625\text{, } 1024\text{, } 3125

How many distinct terms are in the sequence generated by aba^b for 2a1002 \leq a \leq 100 and 2b1002 \leq b \leq 100?

Haskell

import Data.List (nub)

main ::  IO ()
main = print $ length $ nub [a^n | a <- [2..100], n <- [2..100]]
$ ghc -O2 -o exponentComb exponentComb.hs
$ time ./exponentComb
real   0m0.496s
user   0m0.492s
sys    0m0.000s

Python

#!/usr/bin/env python
import itertools
print(len(set(a**b for a,b in itertools.product(list(range(2,101)), repeat=2))))
$ time python3 exponent-combinations.py
real   0m0.037s
user   0m0.028s
sys    0m0.008s

Ruby

#!/usr/bin/env ruby
puts (2..100).to_a.product((2..100).to_a).map { |a,n| a**n }.uniq.count
$ time ruby exponent-combinations.rb
real   0m0.064s
user   0m0.056s
sys    0m0.004s

Rust

use std::collections::HashSet;

fn main() {
    let mut seen = HashSet::new();
    for a in 2..101 {
        for b in 2..101 {
            let term = (a as f64).powf(b as f64);
            let bits: u64 = unsafe { std::mem::transmute(term) };
            seen.insert(bits);
        }
    }
    println!("{}", seen.len());
}
$ rustc -C target-cpu=native -C opt-level=3 -o exponents exponents.rs
$ time ./exponents
real   0m0.005s
user   0m0.004s
sys    0m0.000s