PDS Section 3                  Date: 1st feb 2010

Week 4

Part 1Fie to submit: primepalin.c
An integer is said to be a palindrome if it is equal to its reverse. For example, 79197 and 324423 are palindromes. In this task you will be given an integer N, 1 ≤ N ≤ 1000000. You must find the smallest integer M ≥ N such that M is a prime number and M is a palindrome.

For example, if N is 31 then the answer is 101.

Input

A single integer N, (1 ≤ N ≤ 1000000)

Output

Your output must consist of a single integer, the smallest prime palindrome greater than or equal to N.


Part 2.  File to submit: rootfind.c,  root.out

a) Write a fundtion double power (double x, int n)  to compute x to the power n.

 
b)
double nRootBisection(double y, int n) computes the n-th root of  y via bisection method. This function should make calls to the power( ) function defined in 1. A root is to be found with a tolerance of 0.000001. Print the number of iterations required.

Bisection method: Bisection is a numerical algorithm for iteratively converging on a solution of a function f(x) known to lie inside some interval [a,b]. The algorithm evaluates the function f(x) at the midpoint of the interval [a,b],  x = (a+b)/2.  and then tests to see in which of the subintervals [a,(a+b)/2] or [(a+b)/2,b] the solution lies.   This procedure is then repeated with the new interval, as often as needed to locate the solution within the desired accuracy.
For the problem of finding the n-th root of y,  we want to solve for the value x such that f(x) = xn - y = 0

  c) Newton-Raphson algorithm: Another numerical algorithm for converging on a numerical solution of f(x) = xn - y = 0 is the Newton-Raphson method. This algorithm starts with an initial guess for x and then at each iteration updates the estimated x using the equation: x = (x - f(x)) / f'(x), where f'(x) is the first derivative. This process is repeated until the change in x is within the numerical tolerance interval around zero.

Write the function
double nRootNewton(double y, int n)
to implement this method. Print the root found and the number of iterations required to find a
root with a tolerance of 0.000001.

  d) Write a main( ) function that tests the above functions to calculate the following:
  1. Find the value of 2.3175
  2. Find the 4th root of  630
  3. Find the 10th root of 2000
  4. Find the 20th root of 1000000
  5. and a few more examples