Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 07 Jan 2012 21:03:32 -0600
Message-ID: <4F090789.D54@mindspring.com>
Date: Sat, 07 Jan 2012 22:03:37 -0500
From: pete <pfiland@mindspring.com>
Reply-To: pfiland@mindspring.com
Organization: PF
X-Mailer: Mozilla 3.04Gold (WinNT; I)
MIME-Version: 1.0
Newsgroups: comp.lang.c
Subject: Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question
References: <d2f643df-1028-4906-808d-faa935f94fa0@f8g2000prm.googlegroups.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 155
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.156.228.227
X-Trace: sv3-berK5HIPIiK5f4CPtYLJg0mGcBropHi8zqTbybvxqiG8L9qN9usTiBmFuRw7xxkAIW6S7wShDuEu7fB!elpp30kOsOPl5v05CrjwIV2Zk8xwFTMG9kgYsFqTXHv5XrFtqw0NCyAiDUoPlDH9TFDyeaMJ2ADt!9GaeB5csGQ==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5093
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:15565

divya bisht wrote:
> 
> Toughest Math Statement Question
> (Source : http://hardest-puzzle.blogspot.com/2011/12/toughest-math-statement-question.html
> )
> 
> I am thinking of a 6-digit number. The sum of the digits is 43.
> 
> And only two of the following three statements about the number are
> true:
> 
> (1) it's a square number,
> (2) it's a cube number, and
> (3) the number is under 500000.

/* BEGIN digit_sum_test.c output */

499849 is a 6 digit number.
The sum of the digits of 499849 is 43.
499849 is less than 500000.
499849 is the square of 707.
499849 is not a cube number.

/* END digit_sum_test.c output */




/* BEGIN digit_sum_test.c */
/*
** 999970      cube root == 99, sqrt == 999
** 529999      cube root == 80, sqrt == 728
**
** 499993      cube root == 79, sqrt == 707
** 169999      cube root == 55, sqrt == 412
*/
#include <stdio.h>
#include <stdlib.h>

#define NMEMB(A) (sizeof (A) / sizeof *(A))

unsigned isqrt(unsigned n, unsigned *remainder);
unsigned digit_sum(unsigned n);
int compar(const void*a, const void*b);

int 
main(void)
{
    unsigned bc[99 - 80 + 1];
    unsigned sc[79 - 55 + 1];
    unsigned n;
    unsigned *p;
    unsigned sqrt;
    unsigned rem;
    unsigned square;

    p = bc + NMEMB(bc);
    n = 99;
    do {
        *--p = n * n * n;
    } while (n-- != 80);
    p = sc + NMEMB(sc);
    do {
        *--p = n * n * n;
    } while (n-- != 55);
    puts("/* BEGIN digit_sum_test.c output */\n");
    for (n = 0; n != NMEMB(bc); ++n) {
        sqrt = isqrt(bc[n], &rem);
        if (!rem && digit_sum(bc[n]) == 43) {
            printf("%u is a 6 digit number.\n", bc[n]);
            printf("The sum of the digits of %u is %u.\n",
                bc[n], digit_sum(bc[n]));
            printf("%u is the cube   of %u.\n", bc[n], 80 + n);
            printf("%u is the square of %u.\n", bc[n], sqrt);
            printf("%u is not less than 500000.\n", bc[n]);
        }
    }
    for (n = 0; n != NMEMB(sc); ++n) {
        sqrt = isqrt(sc[n], &rem);
        if (rem && digit_sum(sc[n]) == 43) {
            printf("%u is a 6 digit number.\n", sc[n]);
            printf("The sum of the digits of %u is %u.\n",
                sc[n], digit_sum(sc[n]));
            printf("%u is less than 500000.\n", sc[n]);
            printf("%u is the cube of %u.\n", sc[n], 55 + n);
            printf("%u is not a square number.\n", sc[n]);
        }
    }
    n = 412;
    do {
        square = n * n;
        if (digit_sum(square) == 43 
            && bsearch(&square, sc, NMEMB(sc), sizeof *sc, compar)
            == NULL) 
        {
            printf("%u is a 6 digit number.\n", square);
            printf("The sum of the digits of %u is %u.\n",
                square, digit_sum(square));
            printf("%u is less than 500000.\n", square);
            printf("%u is the square of %u.\n", square, n);
            printf("%u is not a cube number.\n", square);
        }
    } while (n++ != 707);
    puts("\n/* END digit_sum_test.c output */");
    return 0;
}

unsigned 
isqrt(unsigned n, unsigned *remainder)
{
    unsigned power_of_4, root;

    power_of_4 = ((unsigned)-1 >> 2 - (unsigned)-1 % 3) + 1;
    root = 0;
    do {
        if (n >= root + power_of_4) {
            n -= root + power_of_4;
            root += power_of_4 << 1;
        }
        root >>= 1;
        power_of_4 >>= 2;
    } while (power_of_4 != 0);
    if (remainder != NULL) {
        *remainder = n;
    }
    return root;
}

unsigned 
digit_sum(unsigned n)
{
    unsigned sum = 0;
    unsigned tenth = n / 10;

    while (n != 0) {
        sum += n - 10 * tenth;
        n = tenth;
        tenth /= 10;
    }
    return sum;
}

int 
compar(const void *a, const void *b)
{
    const unsigned *aa = a;
    const unsigned *bb = b;

    return *bb > *aa ? -1 : *bb != *aa;
}

/* END digit_sum_test.c */

-- 
pete