Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15565 > unrolled thread

Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question

Started bypete <pfiland@mindspring.com>
First post2012-01-07 22:03 -0500
Last post2012-03-08 12:24 -0800
Articles 9 — 4 participants

Back to article view | Back to comp.lang.c

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question pete <pfiland@mindspring.com> - 2012-01-07 22:03 -0500
    Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-26 10:11 -0800
      Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question pete <pfiland@mindspring.com> - 2012-01-27 17:06 -0500
      Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question pete <pfiland@mindspring.com> - 2012-01-27 18:30 -0500
        Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-31 06:19 -0800
          Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question Willem <willem@toad.stack.nl> - 2012-03-08 22:26 +0000
        Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-31 22:28 -0800
          Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question pete <pfiland@mindspring.com> - 2012-02-01 18:47 -0500
            Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-08 12:24 -0800

#15565 — Re: [Hardest Maths Statement Puzzle] Toughest Math Statement Question

Frompete <pfiland@mindspring.com>
Date2012-01-07 22:03 -0500
SubjectRe: [Hardest Maths Statement Puzzle] Toughest Math Statement Question
Message-ID<4F090789.D54@mindspring.com>
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

[toc] | [next] | [standalone]

#16265

FromTim Rentsch <txr@alumni.caltech.edu>
Date2012-01-26 10:11 -0800
Message-ID<kfnaa5a2v1l.fsf@x-alumni2.alumni.caltech.edu>
In reply to#15565
pete <pfiland@mindspring.com> writes:

> 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.
>
> [snip program -- 114 lines of code, 24 lines of comments]

Seems like a rather long program for the problem...  how
about this instead?

#include <stdio.h>

int digit_sum_of_equals( unsigned number, unsigned total );

int
main(){
    const unsigned SUM = 43;
    unsigned  i = 999,  j = 99,  s, c;
    /***  's' is the square of 'i',  'c' is the cube of 'j'  ***/

    printf( "Looking for six digit numbers whose digits total %u...\n", SUM );

    while(  s = i*i,  c = j*j*j,  s > 99999  ||  c > 99999  ){

        if(  s > c  &&  s < 500000  &&  digit_sum_of_equals( s, SUM )  ){
            printf( "  %u == %u**2\n", s, i );
        }

        if(  c > s  &&  c < 500000  &&  digit_sum_of_equals( c, SUM )  ){
            printf( "  %u == %3u**3\n", c, j );
        }

        if(  s == c  &&  s >= 500000  &&  digit_sum_of_equals( s, SUM )  ){
            printf( "  %u == %u**2 == %u**3\n", s, i, j );
        }

        if(  s >= c  )  i--;
        if(  c >= s  )  j--;
    }

    return  0;
}

int
digit_sum_of_equals( unsigned n, unsigned t ){
    return  n == 0  ?  t == 0  :  digit_sum_of_equals( n/10, t - n%10 );
}

[toc] | [prev] | [next] | [standalone]

#16319

Frompete <pfiland@mindspring.com>
Date2012-01-27 17:06 -0500
Message-ID<4F231FE7.3B63@mindspring.com>
In reply to#16265
Tim Rentsch wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > 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.
> >
> > [snip program -- 114 lines of code, 24 lines of comments]
> 
> Seems like a rather long program for the problem...  how
> about this instead?
> 
> #include <stdio.h>
> 
> int digit_sum_of_equals( unsigned number, unsigned total );

The programs would have been more portable
if we both had used long unsigned instead of unsigned.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#16323

Frompete <pfiland@mindspring.com>
Date2012-01-27 18:30 -0500
Message-ID<4F233391.5FC@mindspring.com>
In reply to#16265
Tim Rentsch wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > 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.
> >
> > [snip program -- 114 lines of code, 24 lines of comments]
> 
> Seems like a rather long program for the problem...  how
> about this instead?
> 
> #include <stdio.h>
> 
> int digit_sum_of_equals( unsigned number, unsigned total );
> 
> int
> main(){
>     const unsigned SUM = 43;
>     unsigned  i = 999,  j = 99,  s, c;
>     /***  's' is the square of 'i',  'c' is the cube of 'j'  ***/
> 
>     printf( "Looking for six digit numbers whose digits total %u...\n", SUM );
> 
>     while(  s = i*i,  c = j*j*j,  s > 99999  ||  c > 99999  ){
> 
>         if(  s > c  &&  s < 500000  &&  digit_sum_of_equals( s, SUM )  ){
>             printf( "  %u == %u**2\n", s, i );
>         }
> 
>         if(  c > s  &&  c < 500000  &&  digit_sum_of_equals( c, SUM )  ){
>             printf( "  %u == %3u**3\n", c, j );
>         }
> 
>         if(  s == c  &&  s >= 500000  &&  digit_sum_of_equals( s, SUM )  ){
>             printf( "  %u == %u**2 == %u**3\n", s, i, j );
>         }
> 
>         if(  s >= c  )  i--;
>         if(  c >= s  )  j--;
>     }
> 
>     return  0;
> }
> 
> int
> digit_sum_of_equals( unsigned n, unsigned t ){
>     return  n == 0  ?  t == 0  :  digit_sum_of_equals( n/10, t - n%10 );
> }

The algorithm seems to be a little more clever.
I'll have to study it a bit.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#16490

From88888 Dihedral <dihedral88888@googlemail.com>
Date2012-01-31 06:19 -0800
Message-ID<8610849.1416.1328019561212.JavaMail.geo-discussion-forums@prnc5>
In reply to#16323
在 2012年1月28日星期六UTC+8上午7时30分25秒，pete写道：
> Tim Rentsch wrote:
> > 
> > pete 
>  writes:
> > 
> > > 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.
> > >
> > > [snip program -- 114 lines of code, 24 lines of comments]
> > 
> > Seems like a rather long program for the problem...  how
> > about this instead?
> > 
> > #include <stdio.h>
> > 
> > int digit_sum_of_equals( unsigned number, unsigned total );
> > 
> > int
> > main(){
> >     const unsigned SUM = 43;
> >     unsigned  i = 999,  j = 99,  s, c;
> >     /***  's' is the square of 'i',  'c' is the cube of 'j'  ***/
> > 
> >     printf( "Looking for six digit numbers whose digits total %u...\n", SUM );
> > 
> >     while(  s = i*i,  c = j*j*j,  s > 99999  ||  c > 99999  ){
> > 
> >         if(  s > c  &&  s < 500000  &&  digit_sum_of_equals( s, SUM )  ){
> >             printf( "  %u == %u**2\n", s, i );
> >         }
> > 
> >         if(  c > s  &&  c < 500000  &&  digit_sum_of_equals( c, SUM )  ){
> >             printf( "  %u == %3u**3\n", c, j );
> >         }
> > 
> >         if(  s == c  &&  s >= 500000  &&  digit_sum_of_equals( s, SUM )  ){
> >             printf( "  %u == %u**2 == %u**3\n", s, i, j );
> >         }
> > 
> >         if(  s >= c  )  i--;
> >         if(  c >= s  )  j--;
> >     }
> > 
> >     return  0;
> > }
> > 
> > int
> > digit_sum_of_equals( unsigned n, unsigned t ){
> >     return  n == 0  ?  t == 0  :  digit_sum_of_equals( n/10, t - n%10 );
> > }
> 
> The algorithm seems to be a little more clever.
> I'll have to study it a bit.
> 
> -- 
> pete

Looking for an integer number rasied to a power of 6  that fits all

conditions in the range should be easy even without writing a program.

[toc] | [prev] | [next] | [standalone]

#18363

FromWillem <willem@toad.stack.nl>
Date2012-03-08 22:26 +0000
Message-ID<slrnjlichb.1bqb.willem@toad.stack.nl>
In reply to#16490
88888 Dihedral wrote:
)> > > 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.
) Looking for an integer number rasied to a power of 6  that fits all
)
) conditions in the range should be easy even without writing a program.

No because only two of the three conditions are true.  One is false.
If contition 3 were false, then the number would be both a square and
a cube, and it would be above 500000.  There is exactly one sixth power
between 500000 and 999999, which is 531441, and that does not sum to 43.

So we're looking for a number that's either a cube or a square (but not
 both) between 100000 and 499999.

As a matter of fact, the powers of 6 below 500000 don't sum to 43 either,
so the 'but not both' check is optional, and we can simple scan all squares
and all cubes for the one that has a digit sum of 43:

 for (int s = 317; s < 708; s++)
   if (digit_sum(s*s) == 43)
     printf("%d\n", s*s);
 for (int c = 47; c < 80; c++)
   if (digit_sum(c*c*c) == 43)
     printf("%d\n", c*c*c);

(The function digit_sum should be self-evident.)


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#16570

FromTim Rentsch <txr@alumni.caltech.edu>
Date2012-01-31 22:28 -0800
Message-ID<kfnsjivxe2m.fsf@x-alumni2.alumni.caltech.edu>
In reply to#16323
pete <pfiland@mindspring.com> writes:

> Tim Rentsch wrote:
>> 
>> pete <pfiland@mindspring.com> writes:
>> 
>> > 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.
>> >
>> > [snip program -- 114 lines of code, 24 lines of comments]
>> 
>> Seems like a rather long program for the problem...  how
>> about this instead?
>> 
>> #include <stdio.h>
>> 
>> int digit_sum_of_equals( unsigned number, unsigned total );
>> 
>> int
>> main(){
>>     const unsigned SUM = 43;
>>     unsigned  i = 999,  j = 99,  s, c;
>>     /***  's' is the square of 'i',  'c' is the cube of 'j'  ***/
>> 
>>     printf( "Looking for six digit numbers whose digits total %u...\n", SUM );
>> 
>>     while(  s = i*i,  c = j*j*j,  s > 99999  ||  c > 99999  ){
>> 
>>         if(  s > c  &&  s < 500000  &&  digit_sum_of_equals( s, SUM )  ){
>>             printf( "  %u == %u**2\n", s, i );
>>         }
>> 
>>         if(  c > s  &&  c < 500000  &&  digit_sum_of_equals( c, SUM )  ){
>>             printf( "  %u == %3u**3\n", c, j );
>>         }
>> 
>>         if(  s == c  &&  s >= 500000  &&  digit_sum_of_equals( s, SUM )  ){
>>             printf( "  %u == %u**2 == %u**3\n", s, i, j );
>>         }
>> 
>>         if(  s >= c  )  i--;
>>         if(  c >= s  )  j--;
>>     }
>> 
>>     return  0;
>> }
>> 
>> int
>> digit_sum_of_equals( unsigned n, unsigned t ){
>>     return  n == 0  ?  t == 0  :  digit_sum_of_equals( n/10, t - n%10 );
>> }
>
> The algorithm seems to be a little more clever.
> I'll have to study it a bit.

It follows pretty directly from the problem statement that
a solution must be either a square or a cube (or both).

Knowing that, we simply go through the squares and cubes
in order, checking each case appropriately.  The only
complication is making sure each case is checked once
and once only, which is done by the s/c comparisons in
checking for solutions and in the logic that chooses
which of s and/or c to change for the next loop iteration.

[toc] | [prev] | [next] | [standalone]

#16626

Frompete <pfiland@mindspring.com>
Date2012-02-01 18:47 -0500
Message-ID<4F29CEF5.1880@mindspring.com>
In reply to#16570
Tim Rentsch wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > Tim Rentsch wrote:
> >>
> >> pete <pfiland@mindspring.com> writes:
> >>
> >> > 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.
> >> >

> > The algorithm seems to be a little more clever.
> > I'll have to study it a bit.
> 
> It follows pretty directly from the problem statement that
> a solution must be either a square or a cube (or both).
> 
> Knowing that, we simply go through the squares and cubes
> in order, checking each case appropriately.  The only
> complication is making sure each case is checked once
> and once only, which is done by the s/c comparisons in
> checking for solutions and in the logic that chooses
> which of s and/or c to change for the next loop iteration.

I got it now.
That was well done.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#18346

FromTim Rentsch <txr@alumni.caltech.edu>
Date2012-03-08 12:24 -0800
Message-ID<kfnhaxysuwh.fsf@x-alumni2.alumni.caltech.edu>
In reply to#16626
pete <pfiland@mindspring.com> writes:

> Tim Rentsch wrote:
>> 
>> [an explanation]
>
> I got it now.
> That was well done.

Thank you.  It's always a pleasure seeing your comments,
doubly so when they are so complimentary. :)

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web