About an exercise appearing in TAOCP volume one's "Notes on the Exercises"

There is a question in TAOCP vol 1, in "Notes on Exercises" section, which goes something like:

"Prove that 13^3 = 2197. Generalize your answer. (This is a horrible kind of problem that the author has tried to avoid)."

Questions:

1. How would you actually go about proving this ? (Direct multiplication is one way, another way could be using formula of (a+b)^3). Does the solution requires using some method that will allow us to make some kind of generalization ?

2. What is the generalization here ?

3. Why is this a horrible kind of problem ?

4. What are some other kind of similar horrible problems that you are aware of ?

Appreciate any answers.

P.S. I apologize if the statement of problem above makes it look like a homework problem, but its not. Requ开发者_开发百科est people to not tag this as a homework problem, so that more people can give answers.

I'd guess that he's alluding to perhaps proving it starting from just the Peano axioms. Then constructing the integers, and going on to formally show that 13^3 = 2197 is a natural, logical conclusion that flows from the definition of exponentiation.

We could generalize to show that given an a and b, there exists some integer c, that is a^b.

This is a horrible kind of a problem because most people find it uninteresting.

Similar sorts of problems can be found in a course on analysis (along with some greatly more interesting).

I initially considered it as follows:
n³ = n * n * n
log_n(n³) = log_n(n*n*n)
log_n(n³) = log_n(n) + log_n(n) + log_n(n)
3 = 1 + 1 + 1
3 = 3

This seems fairly circular in its use of logarithmic identities, but given where I'm at in my algorithms research, it was oddly comforting.

Got stuck at the same exercise and 'solved' it this way: a^b = mult(i=1 to b) a

After a bit of thinking I came to the conclusion that this is a prime factorization (both 13 and 3 are primes). Look up fermat's little theorem.

(I know, it's an old thread but maybe this'll help somebody who is also seeking an answer to this execise.)