An Introduction to McLean's algorithms

The problem is to find an Euler representation for xⁿ, that is, a representation of a positive integer base to a positive integer power in terms if lesser positive integer bases to the same power and such that the representation is minimal in terms of number of lesser powers required. The number of terms in an Euler representation is called the Euler length (for xⁿ).

Failing this, the problem is to reduce the upper bound for the Euler length by successively finding shorter and shorter representations, for two main reasons : to have a current best, which is worthy in itself, and to provide a restriction on the search for better results that will speed up any algorithms used.

We need some definitions, some obvious restrictions and an algorithm. Firstly, let me put the problem on a more mathematically symbolic, and also, hopefully, more compact and explanatory footing. We shall always consider our task to be finding solutions of the equation

xⁿ = a_{x- 1} (x-1)ⁿ + a_{x- 2} (x-2)ⁿ + ..... + a₂ 2ⁿ + a₁

such that the sum of all the coefficients is as small as possible (or minimal in the case of an Euler representation). This equation immediately suggests the use of a recursive formula containing and iterative loop (if this sounds too theoretical, bear with me).

Now allow me to introduce the idea of a search space. A search space (in the context of our search) is the complete set of combinations of lesser powers considered during the search for representations for a particular xⁿ, or, taking the above equation into consideration, the set of combinations (a_{x- 1} , …, a₁). For any algrebraists, this looks suspiciously like a vector space, and it is not surprising that the more general problem, (where xⁿ is 0 and the coefficients are allowed to be negative as well as positive) has been tackled in this way. However, the methods currently used for the general case cannot be transferred to our problem, since there is no control over the numbers of negative and positive coefficients occurring in the solutions produced.

Getting back to our problem, we are faced with the task of deciding how to travel through the search space. Are there any obvious restrictions we can apply ? The most obvious is that the Euler length of xⁿ is bounded above by xⁿ. This may seem unhelpful, but if we start searching without having a target to beat, then we'll never get anywhere. We have immediately restricted our search space to combinations of coefficients whose sum is less than xⁿ. This restriction will extend to the situation where we are looking to improve on existing results, that is, the sum of the a_i must be less than the current upper bound.

We will obviously not just select combinations of a_i at random and test them in the hope that we find a solution. We must have some sort of logical progression. We have two choices; to start from either i = 1 or i = x- 1. In the former case, we would be trying to build up solutions from scratch, not really getting near a result until the last moment, and consequently not being able to use any intermediate calculations to tighten the search space. In the latter case, since (x- 1)ⁿ is significant when compared to xⁿ (especially as x increases) we can quickly reduce the outstanding balance, that is, the remainder when lesser powers are continually subtracted from the original value, in effect breaking down xⁿ in terms of smaller and smaller powers. Needless to say, we shall be taking the second of these two approaches.

Here is the basic algorithm :

d = xⁿ

breakdown (xⁿ, x- 1, 0)

Fairly straightforward, isn't it ? Let me explain: our approach is to remove multiples of (x- 1)ⁿ from xⁿ, leaving smaller outstanding balances from which we remove multiples of (x- 2)ⁿ, etc., keeping a running total of powers used until we reach 1ⁿ, when we can just add on the remaining balance to the running total. In order to achieve this, breakdown (a, b, c) is a recursive function (that is, it calls a copy of itself) with three parameters : a is the outstanding balance, b is the base of the current power and c is the running total of powers used so far. The function is defined as follows :

breakdown (a, b, c)

if b = 1 then

if c + a < d then

d = c + a

print d "IS A NEW RECORD"

fi

return

fi

i = int (a / bⁿ)

while i ³ 0 do

breakdown (a - i*bⁿ, b - 1, c + i)

i = i - 1

end while

return

At each level of recursion, we are dealing with a specific power. The calculation immediately before the while loop is the maximum number of that power that can be subtracted from the outstanding balance, otherwise we would end up with a negative balance, which we are not equipped to deal with. Points to note include the recursive function call with adjusted parameters and the condition that stops the recursion when the base b is 1. The above algorithm is exhaustive, that is, the search space is guaranteed to contain Euler representations. On the other hand, the search space is still far too large for this to be useful on its own. We are therefore interested in amending the algorithm in such a way as to reduce the size of the search space while also preserving our guarantee of success.

We haven't yet used our restriction that the sum of the coefficients must be less than xⁿ. This translates into the following additional condition that may be placed immediately after the existing if statement :

{Amendment 1}

if c > d then

return

fi

In other words, if we have already exceeded our limit, then there is no point in continuing down this particular branch of the search space.

The same restriction can be used again, since as soon as we calculate the initial value of i, we can check to ensure that we have not gone over the limit, and if so, then we can reset this value, as follows :

{Amendment 2}

if i > d - c then

i = d - c

fi

Both of the above conditions preserve our guarantee while reducing the search space.

In practice, computers are better at some things than at others. For instance, recursive function calls are heavy on resources and often have an internal system limit, and so we should minimise this if possible. Also, it is obvious that division is much more demanding than subtraction, and so we could replace the division above by a subtraction loop. We can also remove repetitive calculations of bⁿ by performing these once at the start and storing the values in a table or array.

Since the ratio bⁿ / (b- 1)ⁿ increases as b decreases, the number of loop iterations increases on average as the value of b decreases in the function definition, which increases the number of function calls. There are two ways to combat this. Firstly, why wait until b = 1 before halting the recursion, when it is obvious that when b = 2, we can immediately calculate the number of 2s and 1s required to match exactly with the outstanding balance ? So, instead of the b = 1 code above, we can use the following :

if b = 2 then

i = int (a / bⁿ)

j = a - (i*bⁿ)

if i + j + c < d then

d = c + a

print d "IS A NEW RECORD"

fi

return

fi

The ratio bⁿ / (b- 1)ⁿ provides an additional, and in practice highly effective, restriction. Remembering that this ratio increases as b decreases, then as soon as this value exceeds d, we know that the initial value of i is the only one that we can have at this particular level of recursion, since otherwise we would need too many occurrences of (b- 1)ⁿ. We can therefore insert one more condition immediately prior to Amendment 2.

{Amendment 3}

if bⁿ / (b- 1)ⁿ > d - c then

r = i

else

r = 0

fi

and change the loop condition to :

while i ³ r do

This amendment, which I call the drill-down effect (because it bypasses some of the other restrictions and quickly targets possible solutions) significantly speeds up the algorithm, and is one of several suggestions provided by Scott Chase. Note that in an implementation, the ratios will be pre-calculated to reduce repetition.

When it comes right down to it, even with all of the above improvements in place, in most cases the actual running time of any program version of the above algorithm can be measured in weeks, if not years. The main aim, then, for those of us who are interested in these things, is to improve on whatever happens to be the current best result. The basic approach here is to apply additional modifications that make the search space small enough to cover in a reasonable time but big enough to contain useful results.

There are a couple of obvious tactics that require little or no change to the algorithm. Firstly, instead of starting with d = xⁿ, we can start with d = the current best value, since there's no point in repeating previous effort. We could even take a chance and enter a value much lower than the current best in the hope that a solution will be found, though this is a long shot. Secondly, we can simply stop the program, or set it to stop, before its natural end, perhaps after a standard duration, and see what intermediate results we have. For this we would normally require that intermediate results are stored and/or dumped in some way, which depends on the nature of the programming language and operating system used.

However, there are also several active modifications that can be made :

1. Since we can always calculate the number of 2s and 1s whenever we require, one method of speeding up the algorithm is to replace the d in Amendments 1 and 2 above by a sub-limit, e, an upper bound which excludes the contribution of 2s and 1s. This follows from the reasonable assumption that a solution with a lower value of d will probably (but not definitely) have a lower value of e. We lose the exhaustiveness of the algorithm, but gain a bit of speed. This is another idea suggested by Scott Chase.
2. We can introduce a loop cap, that is, a separate restriction on the number of times that the while loop can be performed at any level of recursion. Obviously, the higher the loop cap, the slower the algorithm, but this is a useful method to produce good initial estimates from which to proceed.
3. With a slight modification in the way that the recursive function is defined, we can introduce an early abort strategy, that is, a separate condition that, if true, will cause the iterative loop to halt prematurely. The specific method I have of doing this is to make breaksum return the count of powers required to complete a solution (whether or not it is an improvement on the current best) from the point that it is called. At a particular recursion level, this count must decrease monotonically, in other words, solutions must get shorter and shorter. A soon as this fails to be true, the loop is exited and the lowest value passed back up to the previous level of recursion. A more explicit definition of the early abort strategy may be found elsewhere.
4. A slight amendment consists of halting each while loop at the value 1 instead of 0. This can often, though not always, substantially speed up the algorithm. Since the search space is altered, in particular reduced in size, in most cases the results obtained here are no better than normal. However, there are occasional successes, and the improvement in speed justifies its use. It should be noted that the amendment only works to a certain limit on x for each power n, since the requirement that every number less than x is involved at least once eventually becomes too restrictive.

Implementation

All of these slightly differing methods may be used, either separately or together, and in different combinations, with the output of one feeding into the next in order to reduce and alter the search space in the hope that better and better results are obtained (by that I mean shorter and shorter solutions). It is very much a hands-on process, which can be made easier if additional steps are taken by the programmer, such as displaying current location, dumping intermediate results, allowing dynamic alteration of limits (especially of d and e), etc. All sorts of different platforms are used to implement the search algorithms, including Unix versions of C and Windows with Visual C++. In addition, I find UltraBasic, which runs on DOS or WIN-DOS, to be very good for developing, prototyping and testing as well as searching. It is highly interactive, allowing dynamic query and update of variables and limits. Its bad points include lack of memory and a limit on the depth of recursion allowed.

URL : www.glasgowg43.freeserve.co.uk/eulalgos.htm