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 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 simply calculates all powers from $2^2$ to $2^{1000}$ 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.

# Initialisation
target <- 100
terms <- vector()
i <- 1
# Loop through values of a and b and store powers in vector
for (a in 2:target) {
for (b in 2:target) {
terms[i] <- a^b
i <- i + 1
}
}
# Determine the number of distinct powers


9 thoughts on “Euler Problem 29: Distinct Powers”

1. 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 = "^"))))

• Hi Gregor,

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

Your one-line solution is much faster 🙂

Peter

• You’re quite welcome 🙂

Really though, avoid growing objects in loops. Compare:

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


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:

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


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