Puzzle (8-14) (answer)

[Steven Schveighoffer]

"Wyverex" wrote
>
> 1)  Find the smallest x + y + z with integers x  y  z  0 such that x + y, 
> x - y, x + z, x - z, y + z, y - z are all perfect squares.

attempt 1:

import tango.io.Stdout;
import tango.math.Math;


bool issquare(long x)
{
    auto r = sqrt(cast(double)x);
    auto lr = cast(long)r;
    if(lr * lr == x || (lr + 1) * (lr + 1) == x)
        return true;
    return false;
}

void main()
{
    for(long x = 3; ; x++)
    {
        for(long i = 1; i * i < x; i++)
        {
            long y = x - (i * i);
            if(issquare(x + y))
            {
                for(long j = 1; j * j < y; j++)
                {
                    long z = y - (j * j);
                    if(issquare(y + z) && issquare(x + z) && issquare(x - 
z))
                    {
                        Stdout(x, y, z).newline;
                        return;
                    }
                }
            }
        }
    }
}

execution time:

real    0m27.115s
user    0m27.115s
sys     0m0.001s

answer:
434657, 420968, 150568

attempt 2 (little bit of cheating, because I know the answer fits within an 
int):

bool issquare(int x)
{
    auto r = sqrt(cast(double)x);
    auto lr = cast(int)r;
    if(lr * lr == x || (lr + 1) * (lr + 1) == x)
        return true;
    return false;
}

void main()
{
    int[][int] pairs;

    for(int x = 3; ; x++)
    {
        for(int i = 1; i * i < x; i++)
        {
            int y = x - (i * i);
            if(issquare(x + y))
            {
                int[] *arr = y in pairs;
                if(arr !is null)
                {
                    foreach(z; *arr)
                    {
                        if(issquare(x - z) && issquare(x + z))
                        {
                            Stdout(x, y, z).newline;
                            return;
                        }
                    }
                }
                arr = x in pairs;
                if(arr is null)
                {
                    pairs[x] = new int[0];
                    arr = x in pairs;
                }
                *arr ~= y;
            }
        }
    }
}

runtime:

real    0m11.303s
user    0m11.299s
sys     0m0.005s

When I did this same solution with longs, it was about 23 seconds, so 
caching the pairs of possible adjacent values doesn't really save a whole 
lot.

> 2)  Develop a bigint type.  should be able to + - * / %.  Should also be 
> printable!

Yeah, right. I don't have a week to kill :P

> 2.5) make bigfloat.

ditto.

-Steve