## Using parfor in Matlab

We all know that loops don’t behave well in Matlab. Whenever it is possible to vectorize the code (i.e. use vectors and matrices to do simultaneous operations, instead of one at a time) significant speed-up is possible. However, there are complex tasks which cannot be vectorized and loops cannot be avoided. I recently needed to compute eigenvalues for some 10 million domains. Since the computations are independent, they could be run in parallel. Fortunately Matlab offers a simple way to do this, using **parfor**.

There are some basic rules one need to respect to use parfor efficiently:

- Don’t use parfor if vectorization is possible. If the task is not vectorizable and computations are independent, then parfor is the way to go.
- Variables used in each computation should not overlap between processors. This is for obvious reasons: if two processors try to change the same variable using different values, the computations will be meaningless in the end.
- You can use an array or cell to store the results given by each processor, with the restriction that processors should work on disjoint parts of the array, so there is no overlap.

The most restrictive requirement is the fact that one cannot use the same variables in the computations for different processors. In order to do this, the simplest way I found was to use a function for the body of the loop. When using a matlab function, all variables are local, so when running the same function in parallel, the variables won’t overlap, since they are local to each function.

So instead of doing something like

parfor i = 1:N commands ... array(i) = result end

you can do the following:

parfor i=1:N array(i) = func(i); end function res = func(i) commands...

This should work very well and no conflict between variables will appear. Make sure to initialize the array before running the parfor, a classical Matlab speedup trick: array = zeros(1,N). Of course, you could have multiple outputs and the output array could be a matrix.

There is another trick to remember if the parpool cannot initialize. It seems that the parallel cluster doesn’t like all the things present in the path sometimes. Before running parfor try the commands

c = parcluster('local'); c.parpool

If you recieve an error, then run

restoredefaultpath c = parcluster('local'); c.parpool

and add to path just the right folders for your code to work.

## Putnam 2017 A2 – Solution

**Problem A2.** We have the following recurrence relation

for , given and . In order to prove that is always a polynomial with integer coefficients we should prove that divides somehow. Recurrence does not seem to work very well. Also, root based arguments might work, but you need to take good care in the computation.

A simpler idea, which is classic in this context, is to try and linearize the recurrence relation. In order to do this, let’s write two consecutive recurrence relations

We add them and we obtain the following relation

which leads straightforward to a telescoping argument. Finally, we are left with a simple linear recurrence with integer coefficient polynomials, and the result follows immediately.

## Putnam 2017 – Problem A1

**Problem A1.** We have and . Therefore .

Next, let’s note what elements cannot be in . Note that taking square roots and squaring cannot change a non-zero remainder modulo into a zero remainder. Therefore, starting from one could never get a multiple of following the allowed operations. Thus we can safely say that multiples of are not in the minimal set .

Furthermore, could only be obtained as a square root of itself with the allowed operations. Starting from , one could never get below by performing square roots or . Therefore, the minimal set does not contain and multiples of .

Now, we show that it contains all the rest. The general idea is as follows: it is enough to find which is the smallest element in a class of remainders modulo to deduce that all larger elements are there (recall the operation ). Now in order to obtain small elements of , one would need to take successive square roots. So if we prove that for some we have for some then we get that .

Now let’s start from the beginning. We have so . Since is in for every , we get that all squares of the form greater than are in . Moreover, so all numbers of the form greater than are in . Since it follows that . Moreover, ends in and is greater than so . Next, we have which ends in and is greater than so it is also in . Therefore .

Finally, we have that , and , . This means that the minimal set is .

## Putnam 2017 – Problems

Source: Art of Problem Solving forum

**Problem A1.** Let be the smallest set of positive integers such that

- a) is in
- b) is in whenever is in and
- c) is in whenever is in

Which positive integers are not in

(The set is “smallest” in the sense that is contained in any other such set.)

**Problem A2.** Let , and

for all Show that, whenever is a positive integer, is equal to a polynomial with integer coefficients.

**Problem A3.** Let and be real numbers with and let and be continuous functions from to such that but For every positive integer define

Show that is an increasing sequence with

**Problem A4.** A class with students took a quiz, on which the possible scores were Each of these scores occurred at least once, and the average score was exactly Show that the class can be divided into two groups of students in such a way that the average score for each group was exactly

**Problem A5.** Each of the integers from to is written on a separate card, and then the cards are combined into a deck and shuffled. Three players, and take turns in the order choosing one card at random from the deck. (Each card in the deck is equally likely to be chosen.) After a card is chosen, that card and all higher-numbered cards are removed from the deck, and the remaining cards are reshuffled before the next turn. Play continues until one of the three players wins the game by drawing the card numbered

Show that for each of the three players, there are arbitrarily large values of for which that player has the highest probability among the three players of winning the game.

**Problem A6.** The edges of a regular icosahedron are distinguished by labeling them How many different ways are there to paint each edge red, white, or blue such that each of the 20 triangular faces of the icosahedron has two edges of the same color and a third edge of a different color?

**Problem B1.** Let and be distinct lines in the plane. Prove that and intersect if and only if, for every real number and every point not on or there exist points on and on such that

**Problem B2.** Suppose that a positive integer can be expressed as the sum of consecutive positive integers

for but for no other values of Considering all positive integers with this property, what is the smallest positive integer that occurs in any of these expressions?

**Problem B3.** Suppose that

is a power series for which each coefficient is or . Show that if , then must be irrational.

**Problem B4.** Evaluate the sum

(As usual, denotes the natural logarithm of )

**Problem B5.** A line in the plane of a triangle is called an *equalizer* if it divides into two regions having equal area and equal perimeter. Find positive integers with as small as possible, such that there exists a triangle with side lengths that has exactly two distinct equalizers.

**Problem B6.** Find the number of ordered -tuples such that are distinct elements of and

is divisible by

## A hint for Project Euler Pb 613

The text for Problem 613 can be found here. The hint is the following picture 🙂

## IMC 2017 – Day 2 – Solutions

See the previous post for the statements of the problems.

**Problem 6.** We have that

Suppose for . Then for we have

This shows that . In the same way, having for leads to .

Now all we need to do is to apply the above procedure to inequalities of the form for and for , which come from the definition of the limit when . The case infinite is similar.

**Problem 7.** If all roots of are real then the sum of their square is non-negative. Suppose is a polynomial of degree . If we denote are the roots of then

If then the previous inequality translates to

which is equivalent to . Now if we compute the coefficients for we find something which for contradicts the previous inequality.

**Problem 8.** We start by observing that the eigenvalues of are and . Next, using the properties of block matrix determinants, we have the following equalities

The block determinant formula holds if is invertible. This happens for all but finitely many values of (the eigenvalues of ). Moreover, since the above equalities are polynomial equalities, this implies equality for every . Therefore, for each eigenvalue of (multiplicity accounted) we have and as eigenvalues for .

Therefore the eigenvalues of are

Note that a phenomenon similar to the Pascal triangle appears, which makes that adjacent eigenvalues of (which have a difference equal to ) with multiplicities and generate an eigenvalue of with multiplicity

**Problem 9.** Elementary techniques in ODE show that . We note that and . Therefore on . This implies, using a recurrence argument, that . This shows that exists for , but, for now, might be infinite.

In order to find an upper bound we may look what is the equation satisfied by an eventual limit of as . We arrive at the ODE . It is immediate to see that . Now we would like to prove that on , and for this we define . Using and the hypothesis we get . Using this we have

and . This implies that

This implies easily that on , which means that on . Thus the pointwise limit of exists. Let’s denote it by . Since using the monotone convergence theorem we have the convergence of integrals . Thus the limit satisfies

Therefore satisfies and which means that the limit is indeed for .

## IMC 2017 – Day 2 – Problems

**Problem 6.** Let be a continuous function such that exists (finite or infinite).

Prove that

**Problem 7.** Let be a nonconstant polynomial with real coefficients. For every positive integer let

Prove that there are only finitely many numbers such that all roots of are real.

**Problem 8.** Define the sequence of matrices by the following recurrence

where is the identity matrix.

Prove that has distinct integer eigenvalues with multiplicities , respectively.

**Problem 9.** Define the sequence of continuously differentiable functions by the following recurrence

Show that exists for every and determine the limit function.

**Problem 10.** Let be an equilateral triangle in the plane. Prove that for every there exists an with the following property: If is a positive integer and are non-overlapping triangles inside such that each of them is homothetic to with a negative ratio and

then