piles of cannonballs

[Maybeso]

:surprised:ops: Oops! :surprised:ops:

Wackerbarth, I realized that as soon as I posted.

I was limiting my search too much. My logic was, the smallest pyramid becomes the top of the largest, so the cannonballs aren't rearranged. This means the middle sized one is restacked to form the base of the big one. It never occurred to me that it could add more than 1 layer to the base.

With my logic, I was searching for a number that is both triangular (as a flat base) and tetrahedral (as the mid-sized stack). What I should have been looking for is a number that is both tetrahedral, and the sum of 1 or more sequential triangular numbers.

Given T(n) = triangle with side n = n(n + 1)/2
and P(n) = pyramid with height n = n(n + 1)(n + 2)/6
and S(n,m) = sum of triangles with sides n thru m. S(56,58) = T(56) + T(57) + T(58).

The answer to the original puzzle is:
T(15) = 120, P(8) = 120, P(14) = 560
--> T(15) + P(14) = P(15) --> 120 + 560 = 680

The larger solutions are:
--> T(55) + P(54) = P(55) --> 1540 + 27720 = 29260
--> S(56,58) + P(55) = P(58) --> 4960 + 29260 = 34220 { Fusion's }
--> T(119) + P(118) = P(119) --> 7140 + 280840 = 287980 { Mine }
--> S(71,74) + P(70) = P(74) --> 10660 + 59640 = 70300 { Fusions }

Fusion's search didn't reach 7140 because he was checking many more combinations of sums. I was only looking for T(n) + P(n-1) = P(n).

[Fusion_power]

This runs in basic or basica or many of the various basic compilers. It is limited in several of them to no more than 64K of memory. I just did not care to extend the calculations any further so never re-coded to find larger solutions. If you want to try for larger numbers, replace all the "100"s with whatever size you choose. As Maybeso found, there are three numbers that have to be tracked
1. the length of a single edge which grows in a progression of 1, 2, 3, 4, 5, etc.
2. The number of balls on one face.
3. The total number of balls.

This is not an "elegant" solution but note that it works entirely using addition. It has a couple of minor glitches that really should be fixed but so what, it runs as is.

Fusion

100 DIM NB(3, 100)
110 B = 4
120 NB(0, 0) = 1: NB(1, 0) = 1: NB(2, 0) = 1
130 NB(0, 1) = 4: NB(1, 1) = 3: NB(2, 1) = 3
140 FOR A = 2 TO 100
150 NB(2, A) = B: B = B + 1
160 NB(1, A) = NB(1, (A - 1)) + NB(2, (A - 1))
170 NB(0, A) = NB(0, (A - 1)) + NB(1, A)
180 NEXT A
190 FOR A = 3 TO 100
200 FOR B = (A + 1) TO 100
210 FOR C = (B + 1) TO 100
220 IF (NB(0, A) + NB(0, B)) = NB(0, C) THEN PRINT NB(0, A); NB(0, B)
230 NEXT C
240 NEXT B
250 NEXT A

[cheesehead]

Doesn't this problem require just finding solutions to:

tetrahedral number + tetrahedral number = tetrahedral number

without necessarily having to consider triangular or pyramidral numbers?

The On-Line Encyclopedia of Integer Sequences (OEIS) sequence A002311 at http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A002311 lists tetrahedral numbers (by ordinal index n, where the nth tetrahedral number = n(n+1)(n+2)/6) that are sums of two tetrahedral numbers. It doesn't explicitly say the sequence is infinite, but I think the convention is to explicitly label known finite sequences as such (so it looks like A002311 is infinite). Right now, A002311 lists the first 34 of them. (The 34th is 1098*1099*1100/6 = 221228700.)

[Fusion_power]

Cheesehead,

Yes it does. I re-coded for that method of solution and ran all solutions up to @10,000,000. This is slow code but it works! Below is the output (unaudited, should be correct though).

100 CLS
110 FOR X = 1 TO 390
120 FOR Y = 1 TO 390
130 FOR Z = 1 TO 390
140 A = (X * (X + 1) * (X + 2) / 6)
150 B = (Y * (Y + 1) * (Y + 2) / 6)
160 C = (Z * (Z + 1) * (Z + 2) / 6)
170 IF ((A + B = C) AND (A <= B)) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X


10:10
120:560
1540:27720
4960:29260
7140:280840
10660:59640
19600:447580
39711:182104
102340:125580
171700:4106980
287980:620620
1107414:1373701


Note that you can convert the basic formula (N*(N+1)*(N+2))/6 to:(N^3+3*N^2+2*N)/6

Fusion

[cheesehead]

You can speed it up, a lot, with simple optimizations. (You probably know these, but let's go through the steps for the sake of readers who are newbie programmers.)

First, move calculations that don't have to be in inner loops to the outermost possible loop:

100 CLS
110 FOR X = 1 TO 390
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = 1 TO 390
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
130 FOR Z = 1 TO 390
{140 deleted}
{150 deleted}
160 C = (Z * (Z + 1) * (Z + 2) / 6)
170 IF ((C = S) AND (A <= B)) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

Note that you can convert the basic formula (N*(N+1)*(N+2))/6 to:(N^3+3*N^2+2*N)/6

Yes, but many simple compilers will execute the first formula (2 adds, 2 multiplies, 1 divide) faster than the second formula (2 adds, 2 multiplies, 2 exponentiations, 1 divide). Some will recognize that the second formula can be done as ((N+3)*N+2)*N/6 and get back down to (2 adds, 2 multiplies, 1 divide), but not the simple ones.

Next, move conditional branches from innermost loops to the outermost possible loop:

100 CLS
110 FOR X = 1 TO 390
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = 1 TO 390
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
127 IF (A > B) THEN GOTO 190
130 FOR Z = 1 TO 390
160 C = (Z * (Z + 1) * (Z + 2) / 6)
170 IF (C = S) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

Then recognize that the IF at 127 can be converted to a change in the range of the FOR loop at 120:

100 CLS
110 FOR X = 1 TO 390
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = X TO 390
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
{127 deleted}
130 FOR Z = 1 TO 390
160 C = (Z * (Z + 1) * (Z + 2) / 6)
170 IF (C = S) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

Next, recognize that, although the IF at 170 can't be eliminated by a change in the range of the FOR loop at 130, the value of C can't be equal to A + B unless Z is greater than Y, so one can skip values of Z that don't exceed Y:

100 CLS
110 FOR X = 1 TO 390
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = X TO 390
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
130 FOR Z = Y+1 TO 390
160 C = (Z * (Z + 1) * (Z + 2) / 6)
170 IF (C = S) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

Also, recognize that, once the value of C is greater than A + B, increasing the value of Z won't help find an equal value, so one can skip the rest of the innermost loop:

100 CLS
110 FOR X = 1 TO 390
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = X TO 390
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
130 FOR Z = Y+1 TO 390
160 C = (Z * (Z + 1) * (Z + 2) / 6)
165 IF (C > S) THEN GOTO 190
170 IF (C = S) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

Now, if X = 390 and Y = 390, then Z will start at 390+1, so adjust the FOR at 130 accordingly. And to keep from missing this if one changes upper limits, parameterize the 390.

100 CLS
105 U = 390
110 FOR X = 1 TO U
115 A = (X * (X + 1) * (X + 2) / 6)
120 FOR Y = X TO U
125 B = (Y * (Y + 1) * (Y + 2) / 6)
126 S = A + B
130 FOR Z = Y+1 TO U+1
160 C = (Z * (Z + 1) * (Z + 2) / 6)
165 IF (C > S) THEN GOTO 190
170 IF (C = S) THEN PRINT A, B, C
180 NEXT Z
190 NEXT Y
200 NEXT X

[Fusion_power]

Agree with most of the optimizations Cheesehead, disagree with the goto statement. There is only one place a goto statement belongs in any basic program, that is to branch to an error checking routine. (ON ERROR GOTO XXX) I never use goto for any other purpose.

I also rarely use basic on a PC anymore. Its handy though when I want to hack out a program quickly. I work on a large mainframe system that still uses a modified version of basic. Knowing how to write basic programs for it means a paycheck for me!

Here is an even more optimized program that runs in about 2% the time of the original. It could still be tweaked quite a bit in the z loop.

100 CLS
110 FOR X = 2 TO 390
120 A = (X * (X + 1) * (X + 2) / 6)
130 FOR Y = X TO 390
140 B = (Y * (Y + 1) * (Y + 2) / 6)
160 D = A + B
170 FOR Z = Y TO 700
180 C = (Z * (Z + 1) * (Z + 2) / 6)
190 IF (D = C) THEN PRINT A, B, C
195 IF (C > D) THEN Z=700
200 NEXT Z
210 NEXT Y
220 NEXT X
230 END

It also generated 5 new pairs:

562475:13251095
2573000:15288900
2699004:12794200
12794200:15086400
13718740:20337240

Fusion
[/b]

[Fusion_power]

Lol Cheese, looks like we overlapped on the posts.

The final example you posted using the goto to get to the NEXT Y statement will cause the program to crash and burn. This is because you jumped out of the Z loop without a proper NEXT. Substitute the line from my program and yours will work fine. Otherwise your logic is quite good. It could still be optimized a bit more in the Z loop though.

Fusion

[Fusion_power]

Here is one more addition that speeds up the code quite a bit. I haven't had time to go through it in detail to be sure its bug free, but it does give the correct output. It also finds another dozen pairs!

Note that it runs in about 45 seconds on an old 486 DX33 computer where the previous version took about 3 minutes to do the same calculations. Its still not an optimum solution even with this. (I'm using the 486 precisely because it is slow, it emphasizes any code optimizations)

Fusion

100 CLS
110 W = 500
120 FOR X = 3 TO W
130 A = (X * (X + 1) * (X + 2) / 6)
140 FOR Y = X TO (2 * W)
150 B = (Y * (Y + 1) * (Y + 2) / 6)
160 D = A + B
170 FOR Z = Y TO (3 * W) STEP 7
180 V = Z + 7
190 C = (V * (V + 1) * (V + 2) / 6)
200 IF C >= D THEN U = Z: Z = 3 * W
210 NEXT Z
220 FOR Z = U TO V
230 C = (Z * (Z + 1) * (Z + 2) / 6)
240 IF (D = C) THEN PRINT A, B, C
250 IF (C > D) THEN Z = V
260 NEXT Z
270 NEXT Y
280 NEXT X
290 END

[cheesehead]

Fusion_power, sorry about the nonworkable GOTOs. The only BASIC version I've used recently allows lots of stuff not in standard BASIC. Anyway, setting the loop index to the upper limit accomplishes what I had in mind.

As for the larger issue of whether GOTOs belong at all: I was in ACM when Communications of the ACM published Dijkstra's "GO TO Considered Harmful". (It always tickled me that membership in the Association for Computing Machinery apparently meant I was an honorary "computing machine"!) When I'm using a language designed without GOTO, which is almost all the time, I don't miss it.

When I composed my examples, what came to mind first was BREAK, then I thought, "No, can't depend on BREAK's being available in BASIC." (Wish I'd thought, "Can't depend on GOTO out of a loop's being available either.") I just forgot about maxing the loop index.

Lol Cheese, looks like we overlapped on the posts.

Yeah, I need to use a standard signature of "Under Construction" because I frequently revise my posts after first posting them. "Preview" isn't enough for me.

[Fusion_power]

My problem with goto goes back to commodore 64 days and the transactor magazine. They published a really good article on programming in basic with the specific intention of eliminating goto by substituting "for" loops. I really like the increased readability of code without goto.

Here is a sample of code in a game program I wrote years ago. There are some real oddities in it!

830 REM **** GENERIC ALPHANUMERIC INPUT ROUTINE ****
840 FOR WD = 1 TO 2
850 A$ = INKEY$
860 IF A$ >= "a" AND A$ <= "z" THEN A$ = CHR$(ASC(A$) AND 223)
870 IF A$ = "" THEN WD = 0 ELSE IF (A$ < "0" OR A$ > "Z") AND A$ <> CHR$(8) AND A$ <> CHR$(9) AND A$ <> CHR$(13) AND A$ <> CHR$(27) THEN WD = 0 ELSE WD = 2
880 NEXT WD

Line 840 establishes the for loop to get one and only one character from the keyboard. Line 850 reads the buffer for one character. Line 860 converts any lower case characters to upper case. Line 870 first checks that a key has been pressed and if not forces wd to zero which causes the loop to repeat, then it checks that only a valid key has been pressed.

Why go to so much trouble to get a single character from the keyboard? Its in a game written for my children to play and they were able to break any other code I was able to write. I call this bulletproof code! (not that it really is of course, just that my kids haven't figured out how to crack it.) I wrote a second routine that gets a long string such as a name, etc. It allows input to be left to right or right to left depending on calling parameters and screens for alpha, numeric, or combined characters.

[cheesehead]

Originally Posted by Fusion_power

They published a really good article on programming in basic with the specific intention of eliminating goto by substituting "for" loops. I really like the increased readability of code without goto.

Lack of WHILE, UNTIL or BREAK can lead to worse things than GOTOs.

Personally, I consider changing a loop index inside the loop to be more confusing than a GOTO ... when one has a choice, that is.

For instance:

840 FOR WD = 1 TO 2
850 ...
860 ...
870 IF ... THEN WD = 0 ELSE IF ... THEN WD = 0 ELSE WD = 2
880 NEXT WD

:( :)