
Exercises and problems in Informatics April 2004 
I. 76. Write a program (i76.pas, ...) that computes for any positive integer x (1\(\displaystyle \le\)x \(\displaystyle \le\)500000) the number of ordered positive integer pairs [a,b] such that the least common multiple of a and b is x.
Example. For x=3 the output should be 3, since the appropriate pairs are [1,3], [3,3] and [3,1], while for x=6 the answer is 9, since the pairs now are [1,6], [2,3], [2,6], [3,6], [6,6], [6,3], [6,2], [3,2], [6,1]. (10 points)
I. 77. Interesting figures are obtained if the sine function is composed with power functions using the following formula: r^{a}=sin (a\(\displaystyle \varphi\)), where a is a real parameter, and r and \(\displaystyle \varphi\) represent the points of the curve in the usual polarcoordinates.
Write your program (i77.pas, ...) which plots such a curve for any given value of a. The example shows the curve corresponding to \(\displaystyle a=\frac{1}{2}\). (10 points)
I. 78. Ackermann studied computability and complexity of functions. The socalled Ackermann function of two nonnegative integer arguments is recursively defined by
\(\displaystyle
A(n,m)=\begin{cases}
m+1,&\mbox{if\ }n=0\\
A(n1,1),&\mbox{if\ }\)0,\ m=0\\
A\big(n1,A(n,m1)\big),&\mbox{if\ }n>0,\ m>0.
\end{cases}
">
An interesting property of this function is that it grows faster than any other ``ordinary'' function, further, explicit representation of A(n,m) is known only for very special values of n and m.
Prepare a sheet (i78.xls) that computes the values of the Ackermann function in the following form (the message #REF! (or #HIV!) can appear if we are no longer able to compute the actual value). (10 points)
m\n  0  1  2  3  4 
0  1  2  3  5  13 
1  2  3  5  13  #HIV! 
2  3  4  7  29  #HIV! 
3  4  5  9  61  #HIV! 
4  5  6  11  125  #HIV! 
5  6  7  13  253  #HIV! 
6  7  8  15  509  #HIV! 
7  8  9  17  1021  #HIV! 
8  9  10  19  2045  #HIV! 
9  10  11  21  4093  #HIV! 
10  11  12  23  8189  #HIV! 
11  12  13  25  16381  #HIV! 
12  13  14  27  #HIV!  #HIV! 

Send your solutions to the following email address:
Deadline: 13 May 2004
