CS13002 PDS Lab, Spring 2003, Section 1/A

Assignment 2

1. [The year Y2K3]

   Find the smallest positive integer t such that the decimal expansion of 2^t starts with 2003, that is,
   
   

   2^t = 2003...,

   that is, the four most significant decimal digits of 2^t are 2003.
   
   Note: For example 2¹⁶ written in decimal is 65536. This expansion starts with 65, 655 etc. Your 2^t should start with 2003 and may be followed by any number of other digits.
   
   Hint: 2^t satisfies the stated property if and only if

   2003 * 10^k <= 2^t < 2004 * 10^k

   for some non-negative integer k. Now take logarithm to the base 10 and concentrate on the fractional parts.
   
   
   
2. [Primes in base seven]

   Write functions to perform the following tasks:
   
   

   • Check if a positive integer (provided as parameter) is prime.
   • Check if a positive integer (provided as parameter) is composite.
   • Return the sum S₇(n) of the 7-ary digits of a positive integer n (supplied as parameter).
   
   Use the above functions to find out the smallest positive integer i for which S₇( p_i ) is composite, where p_i is the i-th prime. Also print the prime p_i .
   
   Note: 1 is neither prime nor composite. The sequence of primes is denoted by p₁=2, p₂=3, p₃=5, p₄=7, p₅=11, ....
   
   As an illustratuve example for this exercise consider the 31st prime p₃₁ = 127 that expands in base 7 as

   127 = 2 * 7² + 4 * 7 + 1,

   i.e., the 7-ary expansion of 127 is 241 and therefore

   S₇(127)=2+4+1=7,

   which is prime.

[Course home] [Home]