For marketers
who love technology
Home » » A list of things you should learn to solve project Euler's problems.

A list of things you should learn to solve project Euler's problems.

Leonhard Euler's signature (Swiss mathematician)
Leonhard Euler's signature (Swiss mathematician) (Photo credit: Wikipedia)
Leonhard Euler is widely considered one of the...
Leonhard Euler is widely considered one of the greatest mathematicians. (Photo credit: Wikipedia)
Euler's project is a challenge for programmers to solve smartly a set of problems designed to be difficultly solvable with the brute force approach. It is a great challenge and  I am very happy every time I finish a problem! If you have not started this challenge, frankly, you should because it is a lot of fun.

In this work in progress article (I am solving the problems one by one and extending this list progressively), you will NOT find the solutions to Euler's problem. However, you will find some tips and the key pieces of knowledge required to solve these problems the right way, that is: smartly!

List of things you should know:
English: Animation that visualizes the "S...
  • A number's (x) smallest prime factor is necessarily lower than x^(1/2).
  • The number of divisors of a number is necessarily 2 times its number of divisors smaller than x^(1/2)+1. 
    • For instance, 5!=120 has the following divisors: [1, 2, 3, 4, 5, 6, 8, 10, ||  120, 60, 40, 30, 24, 20, 15, 12], because 120 = 1* 120 = 120 * 1 = 2* 60 = 60 * 2 = ...
  • Logarithms (in short, if a^b = c; then log_a(c) = x)
  • The prime counting function:
    • "The prime counting function π(n) is defined as the number of primes not greater than n. For example π(11) = 5, since there are five primes less than or equal to 11. There are known algorithms to compute exact values of π(n) faster than it would be possible to compute each prime up to n. The prime number theorem states that π(n) is approximately given by
      \pi(n) \approx \frac n {\ln n},
    • So, in practice, if you are looking for the n-th prime number, you have very good chances to find it in [1:n*log n*1.2] interval
  • Definition of a composite number: it's simply a natural integer > 1 that is not prime.
  • Geometric series: \sum_(k=0)^(n) {q^k}= (1- q^n)/(1-q). Pay attention to the first index: it's 0 not 1. In particular, \sum_(k=0)^(n) {1/2^k}= (1- 1/2^n)/(1-1/2) => limit is equal to 2 when n tends to the infinity. But if the first index is 1, the limit is 2-(1/2^0) = 2-1 = 1
  • Arithmetic series:  \sum_(k=1)^(n) {k} = 1 + 2 + 3 + 4 + ... = n*(n+1)/2. 
    • The proof of this one was found by Gauss and is really simple: just write the terms of the series in increasing and decreasing order:
    • 1 +n     + 2 + n-1     + 3 + n-2 +....
    • = 1+n   + 1+n  + 1+n + ... 
    • = n * (1+n)
  • Symmetry... If there is any kind of symmetry in the problem, try to exploit it to avoid doing the work twice. 


About Gilles


Post a Comment