## 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.

## IMC 2016 – Day 2 – Problem 7

**Problem 7.** Today, Ivan the Confessor prefers continuous functions satisfying for all . Fin the minimum of over all preferred functions.

## SIAM 100 digit challenge no 4 – Matlab solution

In 2002 the SIAM News magazine published a list of problems in numerical analysis. The answer to each of the problems should be given with an accuracy of at least digits. And so there came the *Hundred-Dollar, Hundred-Digit Challenge*. I present below my attempt to solving the th problem in this series, as it deals to finding the global minimum of a highly oscillating function. I confess that my approach is rather simplistic, but solves the problem. First let’s state the problem below:

**Problem 4.** What is the global minimum of the function

## Optimal triangles with vertices on fixed circles

Let and suppose is a triangle such that there exists a point which satisfies , , . What is the relative position of with respect to the triangle such that

a) The area is maximized;

b) The perimeter is maximized.

This was inspired by this answer on Math Overflow.

## Seemous 2015 Problem 1

**Problem 1.** Prove that for every the following inequality holds:

## Solve a Sudoku Puzzle using Matlab

There was a time when I loved to solve Sudoku puzzles. It happened sometimes to find some really difficult puzzles, which I was unable to solve. Having a program which solves Sudoku puzzles is cool, but knowing how it works is cooler.

There are multiple types of solvers. One can imagine to take each free cell in a Sudoku puzzle and associate to it the set of integers in which can lie in there (see the picture below). If the set of possible values contains only one element, then you have found the element corresponding to that cell. If not, then the program needs to make one guess, and see if it gets him to a contradiction. If it arrives at a contradiction, return to the choice step and choose another option, and this needs to be done recursively, which can take huge amounts of time.

One other method which can be implemented in Matlab is to use the matrix structure of the Sudoku table and write the constraints of non repetition on lines, columns and blocks as linear constraints. Once all these constraints are well defined, you can call a semidefinite programming solver to find a solution. A semidefinite programming solver looks to find the vector which optimizes a given cost functions under certain constraints. A good sudoku puzzle has only one solution, and therfore every admissible input which satisfies the constraints is a solution. This means that the cost function doesn’t matter here.

I will present the implementation using YALMIP. You can find another equivalent Matlab implementation here.

## Simple optimization problem regarding distances

Given points in the plane we can study the problem

For the solution is known and for a triangle which has an angle less than is the Toricelli (or Fermat) point, which lies at the intersection of the circumcircles of the equilateral triangles built outside the triangle having the sides of the triangle as support.

For , if we have a convex quadrilateral, then a simple triangle inequality argument proves that the optimal position for is the intersection of the diagonals.

In general, we cannot precisely say what is the position of the solution. Providing a numerical algorithm which computes the optimal position of is not a hard task, and I will do that in the end of this post.