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
answer <- length(unique(terms))
print(answer)

5 thoughts on “Euler Problem 29: Distinct Powers

  1. Pingback: Euler Problem 29: Distinct Powers | A bunch of data

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

      • You’re quite welcome 🙂

        Really though, avoid growing objects in loops. Compare:

        n = 1e7
        x1 = numeric()
        for (i in 1:n) x1[i] <- 1
        
        x2 = numeric(n)
        for(i in 1:n) x2[i] <- 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] <- 1
        

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

  3. Pingback: Euler Problem 29: Distinct Powers – Mubashir Qasim

Leave a Reply