# Is there an algorithm for working out the best way

Teddy Dillard 2022-01-02 Answered
Is there an algorithm for working out the best way (i.e. fewest multiplications) of calculating $$\displaystyle{A}^{{{n}}}$$ in a structure where multiplication is associative?

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

### Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Vivian Soares
Step 1
All you can think of are minimum and maximum values, and you can get stuck doing this by eye. You can check that example 510 can be done in 11 multiplications.
1) $$\displaystyle{x}\times{x}={x}^{{{2}}}$$
2) $$\displaystyle{x}^{{{2}}}\times{x}={x}^{{{3}}}$$
3) $$\displaystyle{x}^{{{3}}}\times{x}^{{{3}}}={x}^{{{6}}}$$
4) $$\displaystyle{x}^{{{6}}}\times{x}^{{{6}}}={x}^{{{12}}}$$
5) $$\displaystyle{x}^{{{12}}}\times{x}^{{{3}}}={x}^{{{15}}}$$
6) $$\displaystyle{x}^{{{15}}}\times{x}^{{{15}}}={x}^{{{30}}}$$
7) $$\displaystyle{x}^{{{30}}}\times{x}^{{{30}}}={x}^{{{60}}}$$
8) $$\displaystyle{x}^{{{60}}}\times{x}^{{{60}}}={x}^{{{120}}}$$
9) $$\displaystyle{x}^{{{120}}}\times{x}^{{{120}}}={x}^{{{240}}}$$
10) $$\displaystyle{x}^{{{240}}}\times{x}^{{{15}}}={x}^{{{255}}}$$
11) $$\displaystyle{x}^{{{255}}}\times{x}^{{{255}}}={x}^{{{510}}}$$
We can guarantee that this is the minimum. Unfortunately, this was a simple example and we don't know how to generalize it into a program. With this speed, you can solve half of the problem manually ...
Not sure how much to add because this is a project of Euler's problem, but if you express these metrics in binary you can see this strategy, why we thought the 510 was a simple example, and why we were so sure it couldn't be rolled up to fewer multiplications. And it might be possible to spot some cases in which you cannot achieve more than a binary method.
###### Not exactly what you’re looking for?
encolatgehu

There seems to be no efficient algorithm for this.
On the same page, however, it does link to a reference of some methods better than binary exponentiation.
One simple example is to use base-N number instead of base-2. e.g. for $$\displaystyle{A}^{{{510}}}$$,
with binary:
$$\displaystyle{2}={1}+{1}$$
$$\displaystyle{3}={2}+{1}$$
$$\displaystyle{6}={3}+{3}$$
$$\displaystyle{7}={6}+{1}$$
$$\displaystyle{14}={7}+{7}$$
$$\displaystyle{15}={14}+{1}$$
$$\displaystyle{30}={15}+{15}$$
$$\displaystyle{31}={30}+{1}$$
$$62=31+31$$
$$\displaystyle{63}={62}+{1}$$
$$\displaystyle{126}={63}+{63}$$
$$\displaystyle{127}={126}+{1}$$
$$\displaystyle{254}={127}+{127}$$
$$\displaystyle{255}={254}+{1}$$
$$\displaystyle{510}={255}+{255}$$ (15 multiplications)
with base-8:
$$\displaystyle{2}={1}+{1}$$
$$\displaystyle{3}={2}+{1}$$
$$\displaystyle{4}={3}+{1}$$
$$\displaystyle{5}={4}+{1}$$
$$\displaystyle{6}={5}+{1}$$
$$\displaystyle{7}={6}+{1}$$
$$\displaystyle{14}={7}+{7}$$
$$\displaystyle{28}={14}+{14}$$
$$\displaystyle{56}={28}+{28}$$
$$\displaystyle{63}={56}+{7}$$
$$\displaystyle{126}={63}+{63}$$
$$\displaystyle{252}={126}+{126}$$
$$\displaystyle{504}={252}+{252}$$
$$\displaystyle{510}={504}+{6}$$ (14 multiplications)
With base-4:
$$\displaystyle{2}={1}+{1}$$
$$\displaystyle{3}={2}+{1}$$
$$\displaystyle{4}={2}+{2}$$
$$\displaystyle{7}={4}+{3}$$
$$\displaystyle{14}={7}+{7}$$
$$\displaystyle{28}={14}+{14}$$
$$\displaystyle{31}={28}+{3}$$
$$62=31+31$$
$$\displaystyle{124}={62}+{62}$$
$$\displaystyle{127}={124}+{3}$$
$$\displaystyle{254}={127}+{127}$$
$$\displaystyle{508}={254}+{254}$$
$$\displaystyle{510}={508}+{2}$$
I don't know how to choose the optimal N.

karton
This is about solving the Project Euler problem, and not directly about your question. Admittedly, I'm quite late but remember having worked out this problem myself. The quickest cut to the solution is to use this OEIS page.
Add up the right hand entries for the first 200 rows, and you're done. As a general hint to Project Euler problems, when all this much theory is required, avoid writing your own programs and look it up somewhere.