Code and Numbers

Here are two small probability puzzles. I believe the first one to be a ‘classical’ problem where a couple very different methods can be used. The second puzzle appears to be a natural extension of the first one, I don’t think I have ever seen any reference to it anywhere.

After hearing about it quite a few times, I finally took a couple hours to understand how to use the Fast Fourier Transform (FFT) to compute a convolution or the product of two arbitrary precision integers.

A permutation \(\sigma\) of \([1, n]\) is a bijective function from \([1, n]\) to \([1, n]\). There are \(n!\) different permutations of \([1, n]\), a random permutation is a random variable that can take as value any permutation with probability \(1/n!\).

A classical problem consists in counting the number of pairs of coprime integer below some limit \(n\). Let \(c(n)\) be this number of pairs:

Modular exponentiation consists in computing \(x^n(\textrm{mod}~ m)\) given \(x\), \(n\), and \(m\). The classical way to efficiently implement this is to use exponentiation by squaring.

In the previous post, we detailed a Pythagorean triple generator. The technique we used to prove it can be generalized to obtain generators solving other Diophantine equations. Let us illustrate this by giving a unique characterization of primitive triples (a, b, c) such that \(2a^2 + b^2 = c^2\).

A few posts back, we saw how to generate Pythagorean triples. We used the following parametrization: primitive triples are uniquely generated by the following equations,

In the previous post, we used Erathostenes sieve to generate all the primes below a given limit \(N\). Using a modified version of this sieve, we could compute for any integer below \(N\) their prime decomposition. That is for any \(n < N\) we produce the unique list \((p_i, q_i)_i\) such that \((p_i)_i\) is prime, \(p_i < p_{i+1}\), and:

A classical problem is to generate all the primes below a limit \(N\). For example this could be used to efficiently compute the prime decomposition of a given integer. A very simple way to do that is to use an Erathostenes Sieve.

The method we used in the previous post to generate Pythagorean triples could be significantly improved. One of the main issues is that we are computing the GCD for all pairs \((m, n)\) and discarding pairs that are not coprime.

As per ProjectEuler 75, we would like to generate all integer triples (a, b, c) such that \(a^2 + b^2 = c^2\) with \(a + b + c \leq N\)