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?

Expert Community at Your Service

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

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Expert Answer

Vivian Soares
Answered 2022-01-03 Author has 1711 answers
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?
Ask My Question
0
 
encolatgehu
Answered 2022-01-04 Author has 1578 answers

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.

0
karton
Answered 2022-01-09 Author has 9103 answers
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.
0

Expert Community at Your Service

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

Relevant Questions

asked 2022-01-13
Does there exists a Ring with unity other than \(\displaystyle{Z}_{{{4}}}\) such that for all non-zero non-unit elements of ring, \(\displaystyle{2}{x}={0}\ \text{and}\ {x}\cdot{x}={0}\)
Let R be a ring with unity and \(\displaystyle{x}+{x}={0},{x}\cdot{x}={0}\) for all non-zero non unit element x of R.
\(\displaystyle{Z}_{{{4}}}\) is one of the example of that ring. Does there exists any other ring of this type ? If no then how can we prove that.
asked 2021-12-30
Are there any interesting and natural examples of semigroups that are not monoids (that is, they don't have an identity element)?
asked 2022-01-12
An automorphism of a group G is an isomorphism from G to itself. Denote by Aut G the set of all automorphisms of G.
a) Prove that Aut G is a group with respect to the operation of composition
b) Give an example of an abelian G such that Aut G is not abelian
asked 2022-01-15
How can one show (hopefully in an elementary manner) that there exist irreducible polynomials of arbitrary degree and number of variables over arbitrary field?
Does \(\displaystyle\forall{n},{d}\in{\mathbb{{{N}}}}\forall\) field \(\displaystyle{\mathbb{{{F}}}}\) exist an irreducible \(\displaystyle{f}\in{\mathbb{{{F}}}}{\left[{x}_{{{1}}},\cdots,{x}_{{{n}}}\right]}\) of degree d?
asked 2022-01-14
Show that an intersection of normal subgroups of a group G is again a normal subgroup of G
asked 2022-01-12
Is it true that for a Group G with Normal Group \(\displaystyle{N}:{\frac{{{G}}}{{{N}}}}={\frac{{{G}{N}}}{{{N}}}}?\)
I think the statement is correct. But why do we have to write: \(\displaystyle{\left[{G},{G}\right]}{\frac{{{N}}}{{{N}}}}\) here instead of just \(\displaystyle\frac{{{G},{G}}}{{N}}?\)
asked 2022-01-14
Consider \(\displaystyle\overline{{{F}}}_{{{p}}}\), the algebraic closure of \(\displaystyle{F}_{{{p}}}\). I want to see that: for every proper subfield \(\displaystyle{K}\leq\overline{{{F}_{{{p}}}}},\frac{\overline{{{F}}}_{{{p}}}}{{K}}\) is not a finite extension.
It is known that, and can be somewhat easily shown that \(\displaystyle\overline{{{F}}}_{{{p}}}=\cup_{{{n}\geq{1}}}{F}_{{{p}^{{{n}}}}}\).
Now, if any of the proper subfields have the form \(\displaystyle{F}_{{{p}^{{{n}}}}}\), it is easy enough to see that \(\displaystyle\overline{{{F}}}_{{{p}}}\ne{F}_{{{p}^{{{n}}}}}{\left(\alpha_{{{1}}},\cdots,\alpha_{{{m}}}\right)}\) for some \(\displaystyle\alpha_{{{i}}}\) by going high up enough, i.e, to some big enough m such that \(\displaystyle\alpha_{{{i}}}\in{F}_{{{p}^{{{m}}}}}\subseteq\overline{{{F}_{{{p}}}}}\)
The problem is characterizing the proper subfields. Is every subfield of \(\displaystyle\overline{{{F}_{{{p}}}}}\) going to have this form? Can we have an infinite intermediate subfield?

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question
...