# Euler Problem 29: Distinct Powers

Euler Problem 29 is another permutation problem that is quite easy to solve using brute force. The MathBlog site by Kristian Edlund has a nice solution using only pen and paper.

Raising a number to a power can have interesting results. The video below explains why this pandigital formula approximates $e$ to billions of decimals:

$(1 + 9^{-4^{6 \times 7}})^{3^{2^{85}}} \approx e$

## Euler Problem 29 Definition

Consider all integer combinations of: $a^b$ for $2 \leq a \leq 5$ and $\leq b \leq 5$.

$2^2=4, \quad 2^3 = 8,\quad 2^4 = 16,\quad 2^5 = 32$

$3^2 = 9,\quad 3^3 = 27,\quad 3^4 = 81,\quad 3^5 = 243$

$4^2 = 16,\quad 4^3 = 64,\quad 4^4 = 256, \quad 4^5 = 1024$

$5^2 = 25,\quad 5^3 = 125,\quad 5^4 = 625,\quad 5^5 = 3125$

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

$4, \ 8, \ 9, \ 16, \ 25, \ 27, \ 32, \ 64, \ 81, \ 125, \ 243, \ 256,\ 625, \ 1024, \ 3125$

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

## Brute Force Solution

This code calculates all powers from $2^2$ to $2^{100}$ and determines the number of unique values. Since we are only interested in their uniqueness and not the precise value, there is no need to use Multiple Precision Arithmetic.

target <- 100
terms <- vector()
i <- 1
for (a in 2:target) {
for (b in 2:target) {
terms[i] <- a^b
i <- i + 1
}
}
print(answer)

### 9 Replies to “Euler Problem 29: Distinct Powers”

1. […] article was first published on The Devil is in the Data, and kindly contributed to […]

2. Gregor Thomas July 6, 2017 at 5:14 pm

Ack! No vectorization and growing an object in a loop! You know 99 * 99 elements, so initialize it to that length! And then ^ is vectorized so you only need one for loop,

 a^(2:target) 

will calculate 99 terms at once. Or skip the loops entirely and use this:

length(unique(as.vector(outer(2:100, 2:100, FUN = "^"))))
1. Hi Gregor,

Thanks for the lesson, I did not know the outer command.

Your one-line solution is much faster 🙂

Peter

1. Gregor Thomas July 7, 2017 at 2:20 am

You’re quite welcome 🙂

Really though, avoid growing objects in loops. Compare:

[code language=”r”]
n = 1e7
x1 = numeric()
for (i in 1:n) x1[i] &lt;- 1

x2 = numeric(n)
for(i in 1:n) x2[i] &lt;- 1
[/code]

Initializing the object to the correct length is *much* faster than extending its length every time. With a vector, it’s pretty quick either way, but with a data frame the difference is huge:

[code language=”r”]
ndf = 3e4
d1 = data.frame(x = numeric())
for (i in 1:ndf) d1 = rbind(d1, data.frame(x = 1))

d2 = data.frame(x = numeric(ndf))
for (i in 1:ndf) d2\$x[i] &lt;- 1
[/code]

Just form the good habit of always pre-allocating and you’ll avoid a common, needless bottleneck.

3. Euler Problem 29: Distinct Powers – Mubashir Qasim July 6, 2017 at 5:25 pm

[…] article was first published on The Devil is in the Data, and kindly contributed to […]

4. […] numbers to the power of five. Two other Euler problems dealt with raising numbers to a power. The previous problem looked at permutations of powers and problem 16 asks for the sum of the digits […]

5. […] numbers to the power of five. Two other Euler problems dealt with raising numbers to a power. The previous problem looked at permutations of powers and problem 16 asks for the sum of the digits of […]

6. […] Problem 32 returns to pandigital numbers, which are numbers that contain one of each digit. Like so many of the Euler Problems, these […]

7. […] Problem 32 returns to pandigital numbers, which are numbers that contain one of each digit. Like so many of the Euler Problems, these […]

This site uses Akismet to reduce spam. Learn how your comment data is processed.