Solutions to Project Euler 29: How many distinct terms are in the sequence generated by a^b?

Project Euler 29: Distinct Powers

Peter Prevos

Peter Prevos |

266 words | 2 minutes

Share this content

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

Euler 29 Definition

Consider all integer combinations of: $a^b$ for $2 \leq a \leq 5$ and $b \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$ ?

Proposed Solution

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

  ## Project Euler 29: Distinct Powers
  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)

Share this content

You might also enjoy reading these articles

Project Euler 35: Circular Primes below One Million

Project Euler 144: Laser Beams and Elliptical Billiards

Project Euler 33: Digit Cancelling Fractions