I need a little clarity in the description of this problem. Is there some background information that can help shed more light on what the problem is about?
For example how are P1 and P2 different?
The output produces a list of numbers but how are they related to calculating X^n?
For example,
n = 37
[1, 2, 3, 5, 8, 16, 21, 37]
size = 8
Thank you for your explanation, it i very much appreciated
Hey Brian,
First, thanks for your email. The prototype of this problem is an interesting complexity problem.
To solve your question, this problem does not have any relation with straight line on geometry. The straight line here refers the computation you can choose is increasing always, like a straight line. P1 and P2 refer two different straight lines to achieve x^15. One thing we might forgot to mention is the initial element you have is x, and you need to find the shortest straight line to achieve x^n.
Please let me know if you still have any problem.
The output produces a list of numbers but how are they related to calculating X^n? The program is called ComputingXPowN and takes a parameter n, so I am assuming it is calculating X^n. What value is X?
It certainly isn’t calculating X^n so what is it calculating?
For example, when I run the program it produces the number 37. How are the numbers [1,2,3,5,8,16,21,37] related to n=37? It’s hard to tell anything from the various outputs what the relationship of n is to the numbers in the lists.
n = 37
[1, 2, 3, 5, 8, 16, 21, 37]
size = 8
n = 55
[1, 2, 3, 4, 7, 11, 22, 33, 55]
size = 9
n = 82
[1, 2, 3, 5, 10, 20, 21, 41, 82]
size = 9
n = 85
[1, 2, 3, 5, 10, 20, 40, 45, 85]
size = 9
In this problem, we focus on the power only, it means the value of x is not important. It seems you have problem about understanding the example of n = 15. We listed two examples in the book for n = 15 and let me only list the power only as follows:
P1 = <1, 2, 4, 8, 12, 14, 15> (takes 7 steps)
P2 = <1, 2, 3, 5, 10, 15> (takes 6 steps)
You start from 1, and the only operation you can do is either either the square of some previous element or the product of any two previous elements. Therefore, we just want to find what is the shortest we can do to reach 15 in this example. One stupidest way is just always take the product of 1, which is an previous element, and the latest element. This will be looked as follows:
P3 = <1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15> (takes 15 steps)
Please take a look of those examples you try, you shall notice that for any example, any intermediate element is derived from the two operations we mentioned above, and the program is outputting the shortest of that.