CS13002 PDS Lab, Spring 2003, Section 1/A

Solution of Assignment 2

1. The decimal expansion of 2^t starts with 2003, if and only if

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

   for some non-negative integer k. Taking logarithm to the base 10 gives

   k + 3 + log₁₀2.003 <= t log₁₀2 < k + 3 + log₁₀2.004,

   that is,

   log₁₀2.003 <= {t log₁₀2} < log₁₀2.004,

   where {x} denotes the fractional part of x. For a real variable (float or double) the fractional part can be computed using the instruction:

   float x, fracPart;
   fracPart = x - (int)x;
   

   Here we have to compute {log₁₀2}, {2log₁₀2}, {3log₁₀2}, ... , till we get a t for which {t log₁₀2} is bounded by log₁₀2.003 and log₁₀2.004. We don't have to compute the integers 2^t which would rapidly grow quite large. Their logarithms will do. However, it is unnecessary to compute log₁₀2 inside the loop. One can precompute log₁₀2 and obtain (t+1)log₁₀2 by adding log₁₀2 to the previous value t log₁₀2.

   #include <stdio.h>
   #include <math.h>
   
   int main ()
   {
      double lbnd, ubnd, log2, tlog2, fracPart;
      int t;
   
      lbnd = log10(2.003);
      ubnd = log10(2.004);
      t = 1;
      tlog2 = log2 = log10(2);
   
      while (1) {
         fracPart = tlog2 - ((int)tlog2);
         if ((fracPart >= lbnd) && (fracPart < ubnd)) {
            printf("t = %d\n", t);
            exit(0);
         }
         t++;
         tlog2 += log2;
      }
   }
   

   The smallest t with the desired property is 5924. All the digits of 2⁵⁹²⁴ are:

   25924 = 2003061637362250094324352202990797505217864677818397836800 \
          7659165361050350279154759991771199911974352493964801781881 \
          0485321621824403574627109859040275679807088397019876644597 \
          0862695312087409249151777128487581638836782413106672421784 \
          9412809372706945867884764072480336009122863301601137229511 \
          7047967909532569553036072850819964922634101595010294018734 \
          2730489501821069944829557731639780006365842984870889998688 \
          3227960036090607467773048144962968405246699694071928225442 \
          6650917759797928090898872963734591638346652900550399162103 \
          7563002754434510263089862351133209615699374115230912673579 \
          9813671489551466715739353979333820121345309808702158098146 \
          5863551416788735887067666253505131943902435378846743049747 \
          5468874866064376943332152093996272348632745905645630043300 \
          7517234299137145500723885506192770715531311196081798524604 \
          4222956037844958656237615878164702616503109645655884105423 \
          2207694209747056274183239238261876467026268992439006984784 \
          4283389888060216248920119089667380910369317282672603098140 \
          7646752274556621439810379241219962700414598303991204745102 \
          4819761649287172898204813826813623180236178263545116482078 \
          9688353222966503865672398085456098990565379065631543971947 \
          0200525175201345526515374671681821338499996691130527800940 \
          1732178099835974776671489189007871384774849822341977769605 \
          8572936125304599565140227658820461459458195969508751068939 \
          2981565591425151945883662520735622999232826434506481461388 \
          9932304287260954576512207844722975446310885864878667740422 \
          2644258149581858847869381448478196761232419191758138779160 \
          0906177113170870706486020575278578630601941210897336938556 \
          0422268027800848378563465486811023716626799244277964982620 \
          1916831002838384268288720556619201627610001582529306565837 \
          2504763155460851619819676311477034561979527321330216182453 \
          11033906335618521141732279732251524088201216.
   

   No built-in C data type can store an integer with this much precision. There are special-purpose routines for doing that.
   
   
   
2. This is easy. One should patiently write all the required routines. There are more efficient routines (than the following ones) for checking if an integer is prime or composite. But these routines are quite complicated and need not outperform the naïve routines for small input values.

   #include <stdio.h>
   #include <math.h>
   
   int nPrime = 1;
   
   int isPrime (int n)
   {
      int i, r;
   
      if (n==1) return(0);
      if (n==2) return(1);
      if (n==3) return(1);
      r = sqrt(n);
      for (i=2;i<=r;i++) if ((n%i)==0) return(0);
      return(1);
   }
   
   int isComposite (int n)
   {
      int i, r;
   
      if (n==1) return(0);
      if (n==2) return(0);
      if (n==3) return(0);
      r = sqrt(n);
      for (i=2;i<=r;i++) if ((n%i)==0) return(1);
      return(0);
   }
   
   int base7sum ( int n )
   {
      int sum = 0;
   
      while (n>0) {
         sum += n % 7;
         n /= 7;
      }
      return(sum);
   }
   
   int main ()
   {
      int n=3;
   
      while (1) {
         if (isPrime(n)) {
            nPrime++;
            if (isComposite(base7sum(n))) {
               printf("i = %d, p_i = %d.\n", nPrime, n);
               exit(0);
            }
         }
         n += 2;
      }
   }
   

   The answer is:

   i = 647, p_i = 4801.
   

   It is rather surprising that for each of the 646 smaller primes p the sum S₇(p) is always non-composite. One can check that the first 10 values of i for which S₇(p_i) is composite are 647, 1182, 1185, 1367, 1368, 1432, 1433, 1552, 1582 and 1614. The corresponding primes p_i are 4801, 9547, 9601, 11311, 11317, 11941, 11953, 13033, 13327 and 13669. Thus these special primes are rather rare. Why? Nobody seems to know a good explanation.

[Course home] [Home]