One possibility is giving and I'm not sure if this is the mininum possible for though.
How can I find the set of distinct positive integers S={a,b,c,d,e,f,g,h,i} such that:
- a+b, b+c, a+c are squares,
- d+e, e+f, d+f are squares,
- g+h, h+i, g+i are squares,
- a+b+c=d+e+f=g+h+i is square?
If there are several solutions then choose with minimal a+b+c.
You can use following Maple program :
Code:for a from 1 to 5000 do for b from 1 to 5000 do for c from 1 to 5000 do for d from 1 to 5000 do for e from 1 to 5000 do for f from 1 to 5000 do for g from 1 to 5000 do for h from 1 to 5000 do for i from 1 to 5000 do if not(a=b) and not(a=c) and not(a=d) and not(a=e) and not(a=f) and not(a=g) and not(a=h) and not(a=i) and not(b=c) and not(b=d) and not(b=e) and not(b=f) and not(b=g) and not(b=h) and not(b=i) and not(c=d) and not(c=e) and not(c=f) and not(c=g) and not(c=h) and not(c=i) and not(d=e) and not(d=f) and not(d=g) and not(d=h) and not(d=i) and not(e=f) and not(e=g) and not(e=h) and not(e=i) and not(f=g) and not(f=h) and not(f=i) and not(g=h) and not(g=i) and not(h=i) then if type(sqrt(a+b+c+d+e+f+g+h+i),integer) then print(a,b,c,d,e,f,g,h,i); break; end if; end if; end do; end do; end do; end do; end do; end do; end do; end do; end do;
No Princeps; you have:
"if type(sqrt(a+b+c+d+e+f+g+h+i),integer)"
but problem is:
"4. a+b+c = d+e+f = g+h+i is a square"
Plus I'm flabbergasted that Maple would "suggest" such a program;
make it only 50 instead of 5000 as limit for the 9 variables:
50^9 / (32 000 000 * 1 000 000) = ~61 years !
(32 million = seconds in 1 year rounded up; computer speed:1 million = number per second)
With 5000, that becomes: 61 035 156 250 000 000 000 years.
Ways to drastically reduce "the search" are required; as example:
a < b < c ; d > a and d < e < f ; g > d and g < h < i (prevents duplicates).
Another is to eliminate 2 full loops by calculating f and i:
f = a + b + c - d - e ; i = a + b + c - g - h
and completely get out of the current loop if above results in f =< e or i =< h
I got "lucky!" by assigning 1000 as limit to a, d, g; 2000 to b, e, h; 3000 to c, f, i.
Code:for a from 1 to 3000 do for b from 1 to 3000 do for c from 1 to 3000 do for d from 1 to 3000 do for e from 1 to 3000 do for f from 1 to 3000 do for g from 1 to 3000 do for h from 1 to 3000 do for i from 1 to 3000 do if not(a=b) and not(a=c) and not(a=d) and not(a=e) and not(a=f) and not(a=g) and not(a=h) and not(a=i) and not(b=c) and not(b=d) and not(b=e) and not(b=f) and not(b=g) and not(b=h) and not(b=i) and not(c=d) and not(c=e) and not(c=f) and not(c=g) and not(c=h) and not(c=i) and not(d=e) and not(d=f) and not(d=g) and not(d=h) and not(d=i) and not(e=f) and not(e=g) and not(e=h) and not(e=i) and not(f=g) and not(f=h) and not(f=i) and not(g=h) and not(g=i) and not(h=i) then if a+b+c=d+e+f and a+b+c=g+h+i then if type(sqrt(a+b+c),integer) then print(a,b,c,d,e,f,g,h,i); break; end if; end if; end if; end do; end do; end do; end do; end do; end do; end do; end do; end do;
Still a big mess, Princeps...did you try and run that?
Anyway, you're missing that these must be squares: a+b, a+c, b+c, d+e, d+f, e+f, g+h, g+i, h+i.
Mine, in UBasic, looks like:
k = 3000
for a = 1 to k-2
for b = a+1 to k-1
if sqrt(a+b) <> integer then next b
for c = b+1 to k
if sqrt(a+c) <> integer or sqrt(b+c) <> integer or sqrt(a+b+c) <> integer then next c
for d = a+1 to k-2
for e = d+1 to k-1
if sqrt(d+e) <> integer or e=b or e=c then next e
f = a+b+c-d-e
if f=<e then cancel loop e : next d
if f=b or f=c then next e
if sqrt(d+f) <> integer or sqrt(e+f) <> integer then next e
for g = d+1 to k-2
for h = g+1 to k-1
if sqrt(g+h) <> integer or h=b or h=c or h=e or h=f then next h
i = a+b+c-g-h
if i=<h then cancel loop h : next g
if i=b or i=c or i=e or i=f then next h
if sqrt(g+i) <> integer or sqrt(h+i) <> integer then next h
print a,b,c,d,e,f,g,h,i
next a
next b
next c
next d
next e
next g
next h
next h
Found a quicker way: calculate and stay as squares instead of full loops;
like, if a=3, then b = 6, 13, 22, 33...
Came across this interest case, a = 209:
Code:209 2000 8816 416 4625 5984 824 1025 9176 209 2000 8816 416 4625 5984 824 3800 6401 209 2000 8816 416 4625 5984 1224 2376 7425 209 2000 8816 824 1025 9176 1224 2376 7425 209 2000 8816 824 3800 6401 1224 2376 7425
This is interesting. No one has the solution yet? I'll definitely take a shot at it. I'm getting 77 integer triplets below 10,000 that meet the conditions a+b, a+c, b+c, a+b+c are all square. If that is correct then the full solution could involve some very large numbers. The algorithm will probably need to be fairly efficient.
Edit: Oh, I didn't realize Wilmer gave solutions. It obviously isn't generating all triplets either.
Perhaps we can come up with a more difficult, but similar problem?
Thanks for stepping in, Mr.B; I was feeling "lonely"!
Agree with your 77 integer triplets below 10,000; and I get 996 integer triplets below 100,000.
My program gets the 77 in 6 seconds; the 996 in 10 minutes, 33 seconds.
I'm curious: are your times faster?
The OP asked only for the minimum case; I gave him that already:
minimum case = 2401: a=97 b=192 c=2112 ; d=376 e=465 f=1560 ; g=720 h=801 i=880
Not sure what you mean with this:
"Edit: Oh, I didn't realize Wilmer gave solutions. It obviously isn't generating all triplets either."
I do generate ALL triplets; I don't want to type them all!
Like, under 10,000, there are 9 cases; the minimum is the one I show above; the maximum is:
maximum case = 9604: a=388 b=768 c=8448 ; d=1504 e=1860 f=6240 ; g=2880 h=3204 i=3520
Sorry, there are a couple lot of things wrong with my last post. When I said "It obviously isn't generating all triplets either.", I was talking about my program, but I didn't realize when I said it how out of context it was. It appears that my program actually does generate all of them. I thought that since my program didn't generate the ones you gave, it was wrong, but I forgot that my program had only generated triplets for a+b+c < 10,000.
My times are much slower, but I didn't try to optimize the algorithm at all. I'm sure I can make them much faster. Generating all triplets a+b+c < 10,000 takes about 5 minutes right now.
I see. Here's my "way", triplets under 10,000:
For u = 8 to 99 : v = u^2 [since we're dealing with squares, get the square first]
For a = 1 to INT(v/3) - 1 [since a<b<c, a has to be < 1/3 of the square]
For w = CEILING(SQRT(2*a + 1)) to HIGH [in order to calculate b, since a+b = a square]
b = w^2 - a
c = v - a - b
If c =< b then end loop: next a
If (a + c) and (b + c) are squares then print a;b;c;v
Next w
Next a
Next u
So mainly:
get the square first
calculate b
default c
For a+b+c < 1,000,000 I'm getting an answer in about half a second, and although all of the solutions are valid, I'm definitely not getting a full set of solutions this time (for a+b+c < 10,000 I'm getting 69 triplets in about 0 ms). I'll post my algorithm here when I've worked out the bugs. There is actually still a lot more optimizing that may be possible as well.