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.

View the code below or download latest version of this code on GitHub.

target <- 100
terms <- vector()
i <- 1
    for (a in 2:target) {
    for (b in 2:target) {
        terms[i] <- a^b
        i <- i + 1
    }
}
answer <- length(unique(terms))
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 […]

    Reply

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

    Reply

    1. Hi Gregor,

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

      Your one-line solution is much faster 🙂

      Peter

      Reply

      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.

        Reply

  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 […]

    Reply

  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 […]

    Reply

  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 […]

    Reply

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

    Reply

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

    Reply

Leave a Reply

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