Pythagorean quadruples: Difference between revisions
Added solution for EDSAC
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added solution for EDSAC) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 665:
<pre>The values of d <= 2200 which can't be represented:
1 2 4 5 8 10 16 20 32 40 64 80 128 160 256 320 512 640 1024 1280 2048</pre>
=={{header|EDSAC order code}}==
A solution from first principles would probably take a long time on EDSAC, so we use the theoretical results [https://mathoverflow.net/questions/90914/sums-of-three-non-zero-squares quoted in MathOverflow]. From these it follows easily that if d is a power of 2, or 5 times a power of 2, then d^2 is not the sum of three non-zero squares. The converse does not follow, but if d is a counterexample then d^2 exceeds 5*(10^10), and therefore d exceeds the limit in the task description. The EDSAC output thus consists of two interleaved arrays, as in the AppleScript solution.
<syntaxhighlight lang="edsac">
[Pythagorean quadruples - Rosetta Code
EDSAC program, Initial Orders 2]
[Arrange the storage]
T46K P56F [N parameter: modified library s/r P7 to print integer]
T47K P106F [M parameter: main routine]
[Library subroutine M3, prints header at load time.
Here, header leaves teleprinter in figures mode.]
PFGKIFAFRDLFUFOFE@A6FG@E8FEZPF
*NUMBERS!WHOSE!SQUARES!ARE!NOT!THE!SUM!
OF!THREE!NONZERO!SQUARES@&MAXIMUM#!V!
..PK [after header, blank tape and PK (WWG, 1951, page 91)]
[------------------------------------------------------------------------------]
[Main routine]
E25K TM GK [load at address specified by M parameter]
[Constants]
[0] P1100F [limit, right-justified, e.g. P1100F for 2200]
[1] !F [teleprinter space]
[2] @F [carriage return]
[3] &F [line feed]
[4] K4096F [teleprinter null]
[5] PD [17-bit constant 1]
[6] P2D [17-bit constant 5]
[Variables]
[7] PF [2^m, where m = 0, 1, 2, ...]
[8] PF [5*2^n, where n = 0, 1, 2, ...]
[Enter here, with acc = 0]
[Complete header by printing limit]
[9] A4@ T1F [print leading zeros as nulls]
A@ TF [pass limit to print subroutine in 0F]
[13] A13@ GN [call print subroutine; leaves acc clear]
O2@ O3@ [print new line]
[Initialize variables]
A5@ T7@ [2^m := 1]
A6@ T8@ [5*2^n := 5]
[Loop back to here after printing number]
[Print 2^m or 5*2^n, whichever is smaller]
[21] A7@ S8@ [compare values]
E28@ [jump if 5*2^n is smaller]
A8@ [else restore 2^m in acc]
LD U7@ [double value in memory]
E32@ [jump to common code]
[28] T4F [clear acc]
A8@ [acc := 5*2^n]
LD U8@ [double value in memory]
[32] RD [common code: undo doubling in acc]
TF [pass number to print subroutine in 0F]
A@ SF [test for number > limit]
G42@ [jump to exit if so]
O1@ [print space before number]
T4F [clear acc]
[39] A39@ GN [call print subroutine; leaves acc clear]
E21@ [loop back for next number]
[Here when done]
[42] O2@ O3@ [print new line]
O4@ [print null to flush teleprinter buffer]
ZF [halt the machine]
[------------------------------------------------------------]
[Subroutine to print 17-bit non-negative integer
Parameters: 0F = integer to be printed (not preserved)
1F = character for leading zero
(preserved; typically null, space or zero)
Workspace: 4F, 5F
Even address; 39 locations]
E25K TN [load at address specified by N parameter]
GKA3FT34@A1FT35@S37@T36@T4DAFT4FH38@V4FRDA4D
R1024FH30@E23@O35@A2FT36@T5FV4DYFL8FT4DA5F
L1024FUFA36@G16@OFTFT35@A36@G17@ZFPFPFP4FZ219D
E25K TM GK [M parameter again]
E9Z [define entry point]
PF [acc = 0 on entry]
</syntaxhighlight>
{{out}}
<pre>
NUMBERS WHOSE SQUARES ARE NOT THE SUM OF THREE NONZERO SQUARES
MAXIMUM = 2200
1 2 4 5 8 10 16 20 32 40 64 80 128 160 256 320 512 640 1024 1280 2048
</pre>
=={{header|FreeBASIC}}==
Line 764 ⟶ 851:
<pre>1 2 4 5 8 10 16 20 32 40 64 80 128 160 256 320 512 640 1024 1280 2048</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_limit = 2200
long x, x2, y, s = 3, s1, s2, counter
long l( _limit )
long ladd( _limit * _limit * 2 )
for x = 1 to _limit
x2 = x * x
for y = x to _limit
ladd( x2 + y * y ) = 1
next
next
for x = 1 to _limit
s1 = s
s = s + 2
s2 = s
for y = x + 1 to _limit
if ladd(s1) == 1 then l(y) = 1
s1 = s1 + s2
s2 = s2 + 2
next
next
counter = 1
for x = 1 to _limit
if ( l(x) == 0 )
if ( counter mod 7 == 0 )
printf @"%6ld", x : counter == 1 : continue
else
printf @"%6ld\b", x
counter++
end if
end if
next
print
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
1 2 4 5 8 10 16
20 32 40 64 80 128 160
256 320 512 640 1024 1280 2048
</pre>
=={{header|Go}}==
{{trans|FreeBASIC}}
Line 2,321 ⟶ 2,458:
=={{header|Wren}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="
var N2 = N * N * 2
var s = 3
Line 2,352 ⟶ 2,489:
System.print()</syntaxhighlight>
{{out}}
<pre>
1 2 4 5 8 10 16 20 32 40 64 80 128 160 256 320 512 640 1024 1280 2048
</pre>
=={{header|XPL0}}==
{{trans|C}}
Twenty-seven seconds on my (cheap) Raspberry Pi 4.
<syntaxhighlight lang "XPL0">def N = 2200;
int A, B, C, D, AABB, AABBCC;
char R(N+1);
[FillMem(R, 0, N+1); \zero solution array
for A:= 1 to N do
[for B:= A to N do
[if (A&1 and B&1) = 0 then \for positive odd A and B, no solution
[AABB:= A*A + B*B;
for C:= B to N do
[AABBCC:= AABB + C*C;
D:= sqrt(AABBCC);
if AABBCC = D*D and D <= N then R(D):= 1; \solution
];
];
];
];
for A:= 1 to N do
if R(A) = 0 then
[IntOut(0, A); ChOut(0, ^ )]; \print non-solutions
CrLf(0);
]</syntaxhighlight>
{{out}}
<pre>
| |||