## Missing digit – short puzzle

The number $2^{29}$ has $9$ digits, all different; which digit is missing?

Mathematical Mind-Benders, Peter Winkler

## Project Euler tips

A few years back I started working on Project Euler problems mainly because it was fun from a mathematical point of view, but also to improve my programming skills. After solving about 120 problems I seem to have hit a wall, because the numbers involved in some of the problems were just too big for my simple brute-force algorithms.

Recently, I decided to try and see if I can do some more of these problems. I cannot say that I’ve acquired some new techniques between 2012-2016 concerning the mathematics involved in these problems. My research topics are usually quite different and my day to day programming routines are more about constructing new stuff which works fast enough than optimizing actual code. Nevertheless, I have some experience coding in Matlab, and I realized that nested loops are to be avoided. Vectorizing the code can speed up things 100 fold.

So the point of Project Euler tasks is making things go well for large numbers. Normally all problems are tested and should run within a minute on a regular machine. This brings us to choosing the right algorithms, the right simplifications and finding the complexity of the algorithms involved.

## Project Euler Problem 285

Another quite nice problem from Project Euler is number 285. The result of the problem depends on the computation of a certain probability, which in turn is related to the computation of a certain area. Below is an illustration of the computation for k equal to 10.

To save you some time, here’s a picture of the case k=1 which I ignored and spent quite a lot of time debugging… Plus, it only affects the last three digits or so after the decimal point…

Here’s a Matlab code which can construct the pictures above and can compute the result for low cases. To solve the problem, you should compute explicitly all these areas.


function problem285(k)

N = 100000;

a = rand(1,N);
b = rand(1,N);

ind = find(abs(sqrt((k*a+1).^2+(k*b+1).^2)-k)<0.5);

plot(a(ind),b(ind),'.');
axis equal

M = k;
pl = 1;

for k=1:M
if mod(k,100)==0
k
end
r1 = (k+0.5)/k;
r2 = (k-0.5)/k;

f1 = @(x) (x<=(-1/k+r1)).*(x>=(-1/k-r1)).*(sqrt(r1^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f1 = @(x) f1(x).*(f1(x)>=0);
f2 = @(x) (x<=(-1/k+r2)).*(x>=(-1/k-r2)).*(sqrt(r2^2-(x+1/k).^2)-1/k).*(x>=0).*(x<=1); f2 = @(x) f2(x).*(f2(x)>=0);

if k == pl
thetas = linspace(0,pi/2,200);
hold on
plot(-1/k+r1*cos(thetas),-1/k+r1*sin(thetas),'r','LineWidth',2);
plot(-1/k+r2*cos(thetas),-1/k+r2*sin(thetas),'r','LineWidth',2);
plot([0 1 1 0 0],[0 0 1 1 0],'k','LineWidth',3);
hold off
axis off
end

A(k) = integral(@(x) f1(x)-f2(x),0,1);

end

xs = xlim;
ys = ylim;

w = 0.01;
axis([xs(1)-w xs(2)+w ys(1)-w ys(2)+w]);

sum((1:k).*A)



## Fireworks – Project Euler 317

You can read the text of the problem here. The idea is that we have an explosion at a given height in a uniform gravitational field (no friction/wind). Supposing that all particles go outwards from the explosion point with a constant initial speed, what is the shape of the body formed by these particles? A hint is given in the picture below with a nice Matlab simulation.

Now what happens if we add a little bit of wind? Here’s the perturbation obtained when adding a 10m/s uniform wind speed vs the initial configuration. Something like this would be a lot more challenging 🙂

## SEEMOUS 2017 Problems

March 5, 2017 1 comment

Problem 1. Let ${A \in \mathcal M_2(\Bbb{R})}$. Suppose

$\displaystyle A =\begin{pmatrix} a& b\\ c & d \end{pmatrix}$

satisfies

$\displaystyle a^2+b^2+c^2+d^2<1/5.$

Show that ${I+A}$ is invertible.

Problem 2. Let ${A,B \in \mathcal M_n(\Bbb{R})}$.

• a) Prove that there exists ${a>0}$ such that for every ${\varepsilon \in (-a,a),\varepsilon\neq 0}$ the matrix equation

$\displaystyle AX+\varepsilon X = B,\ X \in \mathcal M_n(\Bbb{R})$

has a unique solution ${X(\varepsilon) \in \mathcal M_n(\Bbb{R})}$.

• b) Prove that if ${B^2 = I_n}$ and ${A}$ is diagonalizable then

$\displaystyle \lim_{\varepsilon \rightarrow 0} \text{tr}(BX(\varepsilon)) = n-\text{rank}(A).$

Problem 3. Let ${f: \Bbb{R} \rightarrow \Bbb{R}}$ be a continuous function. Prove that

$\displaystyle \int_0^4 f(x(x-3)^2)dx = 2 \int_1^3 f(x(x-3)^2)dx$

Problem 4. a) Let ${n \geq 0}$ be an integer. Compute ${\displaystyle \int_0^1 (1-t)^n e^t dt}$.

b) Let ${k \geq 0}$ be a fixed integer and let ${(x_n)_{n \geq k}}$ be the sequence defined by

$\displaystyle x_n = \sum_{i=k}^n {i \choose k}\left(e-1-\frac{1}{1!}-\frac{1}{2!}-...-\frac{1}{i!}\right).$

Prove that the sequence converges and find its limit.

Categories: Uncategorized

## Project Euler Problem 144 – Laser light escaping an ellipse

Project Euler – problem 144 – visualization of the solution in Matlab

Categories: Geometry, matlab, Uncategorized

## Panaitopol primes – simple representation

February 4, 2017 1 comment

A prime number ${p}$ is called a Panaitopol prime if ${\displaystyle p = \frac{x^4-y^4}{x^3+y^3}}$. I stumbled upon these weird prime numbers while working on problem 291 from Project Euler.

While searching a bit about the problem I did a brute force check to find the first such primes and I found the following values:

$\displaystyle 5, 13, 41, 61, 113, 181, 313, 421, 613, 761.$

Categories: Uncategorized