One prime past the square root of n.

For solving some PE problems sometimes we need to compute the primes up to the smallest prime past the \lfloor \sqrt{n} \rfloor. So, if we need a prime past \lfloor \sqrt{n} \rfloor, we could use the well known fact that there exists a prime  between a number (x) and its double (2x). So we could sieve all the primes between 1 and 2 \times \lfloor \sqrt{n} \rfloor. Or we could use the fact that the largest prime gap below a billion is 287. So we could just sieve primes in the interval [1, \lfloor \sqrt{n} \rfloor + 287].

Advertisements

Modular Multiplicative Inverse

The solution to the equation ax \equiv 1 (mod\ n) where gcd(a,n) = 1 is called the modular multiplicative inverse of a modulo n. The modular multiplicative inverse or modular inverse as it is sometimes called is a very important concept. This concept shows up in many Project Euler problems. One simple way of computing the modular inverse is to simply use the BigInteger.modInverse function in Java/Scala/Kotlin.

Open Source library to help solve Project Euler problems

Unless you want to solve PE problems with your own written code, it makes sense to Google for good libraries. PE problem solvers using Python use libraries like NumPy, SciPy and Sage.

If you want to solve Project Euler problems in Haskell, there is one very good library available: arithmoi. This library has a lot of the basic functions that are need to solve PE problems. Unfortunately, this library is only available in Haskell.

Data structures for Project Euler problems

Not all PE problems are based on mathematics alone, to solve some PE problems you need to have a good knowledge of data structures. Some data structures that help solve some PE problems are:

  1. HashSet or TreeSet – to remove duplicates
  2. PriorityQueue – to access elements in some well-defined order
  3. Union-Find – to keep track of the number of components while adding edges to a graph.
  4. Persistent Collections – There are some PE problems where immutable/persistent collections are needed to implement solutions efficiently, so take a look at Scala immutable/mutable collections. There are also some libraries available for Java: PCollections.

Square-free positive integers

A positive integer is square-free, if it is not divisible by any perfect square greater than one. That is, if we look at the prime factorization of n, n = p_{1}^{m_1} \times p_{2}^{m_2} \times \ldots \times p_{k}^{m_k}. For n to be square-free, we must have m_i = 1 for 1 \le i \le k. All positive integers n can be represented as n = x \times y, where x is a perfect square and y is square-free. The probability that a randomly picked number is square-free is \frac{6}{\pi^{2}}.

There are a few problems in Project Euler that deal with square-free positive integers. Just a few days ago I solved a PE problem in Kotlin, it took 325 seconds to solve the problem. While I was thinking about solving the problem quicker, I realized that if a certain number was square-free, I should be able to prune some computations. Since we know that about 60.8 percent of all numbers are square-free, I went ahead and added a check to my code. This reduced the running time to 260 seconds. A reasonable improvement.

Here is the actual snippet that makes the square-free check:

  val (sqr_pfs, sqr_free_pfs) = split_square_square_free_pfs(m_pfs)
  var of = Long.MAX_VALUE
  var c_min = 1L
  var skip = false
  for ((p, _) in sqr_free_pfs) {
    val p_long = p.toLong()
    if (p_long > of) {
      skip = true
      break
    }
    of = of / p_long
    c_min = c_min * p_long
    if (c_min >= n_long) {
      skip = true
      break
    }
  }
  if (skip == false) {
    val trplts_for_a = triplets_for_a(n, a, sqr_pfs)
    result = result + trplts_for_a
  }

How to compute ceiling(a/b) for positive integers a, b?

One way to compute \left \lceil \frac{a}{b} \right \rceil is to convert a, b to double and then use the ceil function on the ratio \frac{a}{b} and then convert the result back to an integer. This way may leave us with some uneasiness about using floating point operations for something that could be computed using integer operations. So here is a simple way to do it with just integer operations.

uint64_t x_next(uint64_t n, uint64_t x) {
  auto n_div_x = n / x;
  auto n_mod_x = n % x;
  auto ceil_n_over_x = 0ULL;
  if (n_mod_x == 0ULL) {
    ceil_n_over_x = n_div_x;
  } else {
    ceil_n_over_x = n_div_x + 1ULL;
  }
  return ceil_n_over_x;
}

An alternate way to compute the same thing using only integer operations is:

  uint64_t i_ceil(uint64_t n, uint64_t x) {
    if (x == 0) {
      throw std::invalid_argument("Check failed: x > 0.");
    } else {
      return (n + x - 1ULL) / x;
    }
  }