CS13002 PDS Lab, Spring 2003, Section 1/A

Solution of Assignment 2



  1. The decimal expansion of 2t starts with 2003, if and only if
    2003 * 10k <= 2t < 2004 * 10k
    for some non-negative integer k. Taking logarithm to the base 10 gives
    k + 3 + log102.003 <= t log102 < k + 3 + log102.004,
    that is,
    log102.003 <= {t log102} < log102.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 {log102}, {2log102}, {3log102}, ... , till we get a t for which {t log102} is bounded by log102.003 and log102.004. We don't have to compute the integers 2t which would rapidly grow quite large. Their logarithms will do. However, it is unnecessary to compute log102 inside the loop. One can precompute log102 and obtain (t+1)log102 by adding log102 to the previous value t log102.
    #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 25924 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 S7(p) is always non-composite. One can check that the first 10 values of i for which S7(pi) is composite are 647, 1182, 1185, 1367, 1368, 1432, 1433, 1552, 1582 and 1614. The corresponding primes pi 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]