Computer Challenge Problems

From: gjfee@jeeves.uwaterloo.ca, latest known address: gjfee@cecm.sfu.ca

Here are 14 problems to challenge your computer algebra system. If you can solve any of the following then post your solution with the following extra information if known.

  1. The computer hardware and some indication of its speed and its memory size.
  2. The computer software including version numbers and operating systems.
  3. The CPU time in seconds needed to solve one of the given problems.
  4. The memory space needed to solve a given problem in bytes.
  5. The programs that you had to write and the size of them in bytes, and some indication of how long it took you to write them.
  6. The solution (if it is small enough to post).

The problems:

  1. Given that the arc lengths of the 3 principal perimeters of an ellipsoid are 0.989, 0.853 and 0.712 meters, find the surface area in square meters of the ellipsoid to 33 significant digits. Note: A principal perimeter is the curve that is the intersection of the ellipsoid and a plane that contains 2 of the 3 principal semi-axis.

  2. Find a conic that touches the following 5 given conics? 
     
11689*x^2-9600*x*y+2169*y^2-2204198*x+908304*y+103910536=0,
11281*x^2-10800*x*y+4036*y^2-1981082*x+1110832*y+91469653=0,
221*x^2-264*x*y+144*y^2+11368*x-1056*y+269456=0,
17425*x^2-7560*x*y+17056*y^2-1635370*x-554456*y+50763289=0, 
58825*x^2-6160*x*y+41764*y^2+4470090*x-1814952*y+98454609=0 .

    If you can't find the coefficients exactly then can you find a numerical approximation to them to 17 significant digits. Note: By touching , I mean that the pair of conics have a common tangent line at an intersection point.

  3. What is the shortest path along the surface of the ellipsoid with equation x^2/17^2 + y^2/8^2 + z^2/3^2 = 1 , starting at point 1. (x=7, y=5, z>0) and going to point 2. (x=-9, y=-3, z<0). Also find the arc length of the shortest path. Find the exact answer in terms of known special functions (if possible) and also find numerical approximations to 17 significant digits.

  4. What is the shortest path along the surface of the torus with equation (x^2+y^2+21+z^2)^2-100*x^2-100*y^2 = 0 , starting at point 1. with coordinates, (x=5,y=0,z=2) and finishing at point 2. with coordinates, (-4,2,(-41+20*5^(1/2))^(1/2)) . Also find the arc length of the shortest path? Find the exact answer, in terms of known special functions (if possible) and also find numerical approximations to 17 significant digits.

  5. Optimize the Campbell, Baker , Hausdorff formula to order 12. The formula is : 
     
ln(exp(t*A) @ exp(t*B)) = (A+B)*t + 1/2*c(A,B)*t^2
+ (1/12*c(A,c(A,B)) - 1/12*c(B,c(A,B)))*t^3 + O(t^4), (to order 3)

    where t is a real parameter and A and B are square matrices, and "c" is the commutator defined by: c(A,B) = A @ B - B @ A, and @ denotes matrix multiplication. It is known that all higher order terms (higher than first order in "t") can be expressed in terms of linear combinations of nested commutators. By optimize I mean minimize the number of commutators. For example , for the above given CBH series to third order can be optimized as follows: 
     
s[1] = A+B;
s[2] = 1/2*c(A,B);
s[3] = 1/6*c(A-B,s[2]);
CBH = (((s[3]*t+s[2])*t)+s[1])*t;

    Cost is only 2 commutators plus a few other operations.

  6. Does this equation x^5 - 5*x^3 + 5*x -5 = 0, have a solution in terms of radicals. If it does then find the radical expression?

  7. Construct the regular polygon with 2^32-1 sides. If this is too difficult then try the regular 17'gon and then the regular 257'gon and then the regular 2^16+1 gon. By construct in the weak sense I mean express the coordinates of the the polygon in terms of square roots and the other 4 basic arithmetic operations ( add, subtract, multiply and divide). In the strong sense , I mean write out a list of ruler and compass moves that any good "student" could follow. You are given 2 points on a sheet of paper and that is your unit distance and you must construct the n'gon in a circle of unit radius, where one of your given points is the center of the unit circle and the other one must be a vertex of the regular n'gon. A possible example of a ruler and compass move: step number 1897. Draw a circle with center the point given in step number 643 and radius given in step number 783 . This intersects the line given in step number 351 in 2 points. The intersection point closest to the point from step number 498 , will be called the point determined by this step number 1897. Try to minimize the number of steps.

  8. Is x rational, where x is the real root of F(-.2,.2;.5;x)=5/6 , and 0<=x<=1 ? Note: F denotes the Gauss hypergeometric function and F(-.2,.2;.5;x) means that the numerator parameters are -.2 and .2 , the denominator parameter is .5 and the argument is x .

  9. Plateau problem. Find the surface with minimal surface area and boundary given by the following space curve. 
     
x(t) = 23*cos(t)+4*sin(2*t)+cos(4*t),
y(t) = 11*sin(t)-3*cos(2*t)-sin(3*t),
z(t) = 5*sin(t) -2*sin(3*t)+cos(5*t)
for 0<=t<=2*Pi

    Find the surface and its surface area to 17 significant digits.

  10. Find the maximum of J(10000,x) for 0<=x<=infinity and where it occurs , both to 17 significant digits. Note: J denotes the Bessel function of the first kind , and J(10000,x) means that the order is 10000 and the argument is x .

  11. Let u(x,y) be the solution to the following second order linear partial differential equation, (Poisson's equation): diff(u(x,y),x,x) + diff(u(x,y),y,y) = -2 , on the interier of the L-shaped region with the following boundary conditions, it is zero everywhere on the following L-shaped boundary: join (0,0) to (3,0) to (3,1) to (1,1) to (1,2) to (0,2) to (0,0) in all cases with straight line segments. What is the maximum value of u(x,y) and where does it occur? Find numerical approximations to 33 significant digits. Note: diff(u(x,y),x,x) denotes the second partial derivative of u(x,y) with respect to x twice.

  12. What is the hyper-surface area of the following 4-dimensional hyper-ellipsoid: 
     
w^2/3^2 + x^2/7^2 + y^2/11^2 + z^2/19^2 = 1 ,

    to 17 significant digits? Can the triple integral be reduced to a double integral? a single integral? a known special function?

  13. What is an efficient method to evaluate a high degree Bernstein polynomial at a given point, given the Bernstein polynomial in the form of a array of function values. Example: Given the degree n=20000, and an array "a" indexed from 0 to n , such that a[i] = f(i/n) for i from 0 to n, to a precision of 16 significant digits. We are also given the function f(x) = cos(x) . The point "v" is .4567890123456789 . Evaluate the Bernstein polynomial for f(x)=cos(x) of degree n=20000 at the point "v". We would like only 10 significant digits for the evaluation. Can this be done without forming the Bernstein polynomial? Can your computer algebra system write a program to do this that could be executed in some other language like C or fortran, that could run without causing exponent overflow or exponent underflow error messages, and that only needs 16 digits for all intermediate operations? Note: the Bernstein polynomial of degree n for function f(x) is defined by: b(x) = sum( f(i/n)*binomial(n,i)*x^i*(1-x)^(n-i), for i from 0 to n).

  14. Find the solution of the following second order linear differential equation. 
     
(9*x+1)^5*((x-1)^2+1/37)^4*diff(y(x),x$2) + (3*x+1)*diff(y(x),x)
+ (x^5-3*x^2+8)*y(x) = 0,

    with the following initial conditions: y(0)=1, D(y)(0)=0 . Find y(10) and D(y)(10) to 33 significant digits. Note: diff(y(x),x$2) denotes the second derivative of y(x) with respect to x, and D(y)(0) denotes the derivative of y(x) with respect to x, evaluated at x=0 .