11

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. Request people to not tag this as a homework problem, so that more people can give answers.

IAdapter
  • 62,595
  • 73
  • 179
  • 242
vshenoy
  • 1,153
  • 1
  • 8
  • 14
  • Out of context that is a calculation, it doesn't require any proof. – Kobi Oct 05 '09 at 08:58
  • Is there a programming related question here? – kloucks Oct 05 '09 at 11:29
  • 2
    I'd guess given that the book in question is The Art of Computer Programming it is at least marginally related - but I think it is more a case of Knuth wanting to explicitly let other maths people know what was considered out of scope. – garethm Oct 05 '09 at 11:34

3 Answers3

4

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).

garethm
  • 2,163
  • 17
  • 27
  • 3
    Hi garethm, I doubt it. If the above problem required using Peano axioms, it would have the rating of at least M30 or HM30, where as i think that this particular question has the rating of less than 15. Is it possible that, the expectation is something like this (for e.g.): Prove that 1 + 2 + 3 + ... + 10 = 55. Generalize your answer. And the answer would be something like: (1+10) + (2+9) + ... + (5+6) = 5 x 11 = (10 x 11) / 2 and the generalization would obviously be (at least to Gauss :-) 1 + 2 + 3 + ... + n = (n x (n+1))/2. If so, what such identity is hidden in 13^3 = 2197 ? – vshenoy Oct 05 '09 at 12:08
3

I initially considered it as follows:
n3 = n * n * n
logn(n3) = logn(n*n*n)
logn(n3) = logn(n) + logn(n) + logn(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.

Stuart Thiel
  • 13
  • 3
Stuart Thiel
  • 31
  • 2
1

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.)

user3060129
  • 23
  • 1
  • 4