Short & Sweet Math Challenges #6 [LONG] Message #1 Posted by Valentin Albillo on 24 May 2004, 1:28 p.m.
Hi everybody, here we go (again):
Say you've just got that powerful, new HP calculator for your collection (say an HP33S
or some HP48/49 model) and you're itching to test it on some interesting problem.
Here's one of my own devising for you to try. Apart from being interesting in its own right (IMHO), it might actually be useful ! Consider for instance its use by someone teaching math to prepare interesting problems for his/her students (i.e.: K = 7.041776 anyone ? :) Read on ...
Before we begin ...
We all know Pi is a transcendental number. By definition, this means Pi cannot be the root
of any polynomial equation with integer coefficients, whatever its degree (this is also
true of all other transcendental numbers such as e, sin(1), log(2), etc). In particular,
Pi cannot be a root of a cubic equation with integer coefficients, such as
A*x^3 + B*x^2 + C*x + D = 0
where A,B,C,D are all of them integer. However, this doesn't preclude the fact that such an equation
might have a root which is as close an approximation to Pi as desired for sufficiently large A,B,C,D. And thus,
here is
The challenge:
"Write a program for your preferred HP calculator to find the integer coefficients A,B,C,D of the cubic equation:
A*x^3 + B*x^2 + C*x + D = 0
which has a root that best approximates a given positive constant K (say, K = Pi), where the
coefficients are less or equal in absolute value to a maximum given integer value, M
(say, M = 9)."
Notes:
Without loss of generality, the A coefficient will always be positive
(i.e: it goes from 1 to M, both included) while the B,C, and D coefficients can be
either positive or negative (i.e: they go from M to +M, both included). Your
program must input K (say Pi), M (say 9) and a very loose initial interval for the
root (say [3.1, 3.2]) and must output the coefficients A,B,C,D of the "best"
equation, the value X of the root, and the absolute difference between the
root X and the given constant K.
For instance, given the inputs K=Pi, M=20, Interval= [3.1, 3.2] it might
output something like (not the best solution, of course):
A= 1, B= 10, C= 19, D= 8, X= 3.14162732179, DIF= 0.00003466820
which means that the cubic equation x^3  10*x^2 + 19*x + 8 = 0 has a root
x= 3.14162732179, which differs from Pi by only 0.00003466820.
You are expected to deliver a general program, that will work for any positive constant K, maximum coefficient M and given initial interval [X1,X2], but for the purposes of testing the efficiency and accuracy of your solution you should try these two cases:
 Case 1: constant K = Pi, Max. coefficient M = 9, initial interval [3.1, 3.2]
 Case 2: same but with Max. coefficient M = 20
Hints:
 Absolutely refrain from using a PC. You'll learn nothing about writing and optimizing
programs for your HP calculator and will ruin the pleasure of seeing your efforts
and ingenuity succeed with your little HP machine. This is intended for real programmers using real HP calcs, not the "bruteforceusingazillionGhzPC" kind.
 Though most any HP model can be used to successfully solve this challenge, it is advisable
that you use a suitably fast HP calculator, say any model using a Saturn CPU (HP33S, HP32S,
HP32SII, HP42S, HP48/49, HP71B, etc), in order to attain reasonable running times.
 Even so, you'll need to exercise your ingenuity to achieve bearable running times.
A bruteforce approach is doomed to failure. Consider this:
 for M = 9, your program will have to choose among no less than 61,731 possible cubic equations, from (1,9,9,9) to (9,9,9,9)
 for M=20, your program will have to choose among more than 1 million possible equations,
(namely 1,378,420) from (1,20,20,20) to (20,20,20,20)
In a few days, I'll give a solution for the HP71B, which will be a 9line program
(300+ bytes), with the following running times:
 For the case constant K = Pi, Max. coefficient M = 9, initial interval [3.1, 3.2],
it takes 7 min. 16 seconds to find the solution among the 61,731 cubic equations
possible, output it and stop.
 For the case constant K = Pi, Max. coefficient M = 20, initial interval [3.1, 3.2],
it takes 3 hour 4 min. to find the solution among the 1,378,420 cubic equations
possible, output it and stop.
Now's your turn. Just put that brand new shiny HP33S, that wonderful classical HP42S, that ultrapowerful HP49, or that venerable HP71B to the task, plus your ingenuity and RPN/RPL/BASIC/FORTH/Assembler programming skills of course. After all, if the good old HP71B can do it in 3 hours using BASIC,
what incredible times will you be able to achieve with much faster machines using RPN/RPL, say ? Emulators very
welcome too, of course.
Best regards from V.
