Anonymous user
Taxicab numbers: Difference between revisions
inserted Pascal
(inserted Pascal) |
|||
Line 1,328:
402597 = 61^3 + 56^3
402597 = 69^3 + 42^3</pre>
=={{header|Pascal}}==
{{works with |Free Pascal}}
searchSameSum takes most of the time.[[c]] Version is ~9 times faster aka 43 ms.
<lang>program taxiCabNo;
uses
sysutils;
type
tPot3 = Uint32;
tPot3Sol = record
p3Sum : tPot3;
i1,j1,
i2,j2 : word;
end;
tpPot3Sol = ^tPot3Sol;
tPotarr = array[0..0] of tPot3Sol;
tpPotarr = ^tPotarr;
var
//1290^3 = 2'146'689'000 < 2^31-1
pot3 : array[0..1290] of tPot3;//
AllSol : array[0..3000] of tpot3Sol;
AllSolHigh : NativeInt;
MaxInsDist : NativeInt;
procedure SolOut(const s:tpot3Sol;no: NativeInt);
begin
with s do
writeln(no:5,p3Sum:12,' = ',j1:5,'^3 +',i1:5,'^3 =',j2:5,'^3 +',i2:5,'^3');
end;
procedure InsertAllSol;
var
tmp: tpot3Sol;
p :tpPotarr;
p3Sum: tPot3;
i: NativeInt;
Begin
i := AllSolHigh;
IF i > 0 then
Begin
p := @AllSol[0];
tmp := p^[i];
p3Sum := p^[i].p3Sum;
//search the right place for insertion
repeat
dec(i);
IF (p^[i].p3Sum <= p3Sum) then
BREAK;
until (i<=0);
IF p^[i].p3Sum = p3Sum then
EXIT;
//free the right place by moving one place up
inc(i);
IF i<AllSolHigh then
Begin
move(p^[i],p^[i+1],SizeOf(AllSol[0])*(AllSolHigh-i));
AllSol[i]:= tmp;
IF MaxInsDist < AllSolHigh-i then
MaxInsDist := AllSolHigh-i;
end;
end;
inc(AllSolHigh);
end;
function searchSameSum(var sol:tpot3Sol):boolean;
var
Sum,
SumHi: tPot3;
hi,lo: NativeInt;
Begin
Sum := sol.p3Sum;
lo:= Sol.i1;
hi:= Sol.j1;
repeat
dec(hi);
SumHi := Sum-Pot3[hi];
while (lo<hi) AND (SumHi>Pot3[lo]) do
inc(lo);
IF SumHi = Pot3[lo] then
BREAK;
until lo>=hi;
IF lo< hi then
Begin
sol.i2:= lo;
sol.j2:= hi;
searchSameSum := true;
end
else
searchSameSum := false;
end;
procedure Search;
var
i,j: LongInt;
Begin
MaxInsDist := 0;
AllSolHigh := 0;
For j := 2 to High(pot3)-2 do
Begin
For i := 1 to j-1 do
Begin
with AllSol[AllSolHigh] do
Begin
p3Sum:= pot3[i]+pot3[j];
i1:= i;
j1:= j;
end;
IF searchSameSum(AllSol[AllSolHigh]) then
BEGIN
InsertAllSol;
IF AllSolHigh>High(AllSol) then
EXIT;
end;
end;
end;
end;
var
i: LongInt;
Begin
For i := Low(pot3) to High(pot3) do
pot3[i] := i*i*i;
AllSolHigh := 0;
Search;
For i := 0 to 24 do SolOut(AllSol[i],i+1);
For i := 1999 to 2005 do SolOut(AllSol[i],i+1);
writeln('count of solutions ',AllSolHigh);
writeln('maximal insertion distance ', MaxInsDist);
end.</lang>
<pre> 1 1729 = 12^3 + 1^3 = 10^3 + 9^3
2 4104 = 16^3 + 2^3 = 15^3 + 9^3
.....
24 373464 = 72^3 + 6^3 = 60^3 + 54^3
25 402597 = 69^3 + 42^3 = 61^3 + 56^3
2000 1671816384 = 1168^3 + 428^3 = 944^3 + 940^3
2001 1672470592 = 1187^3 + 29^3 = 1124^3 + 632^3
..
2005 1676926719 = 1188^3 + 63^3 = 1095^3 + 714^3
2006 1677646971 = 1188^3 + 99^3 = 990^3 + 891^3
count of solutions 2297
maximal insertion distance 50
real 0m0.383s
</pre>
=={{header|Perl}}==
Uses segmentation so memory use is constrained as high values are searched for. Also has parameter to look for Ta(3) and Ta(4) numbers (which is when segmentation is really needed). By default shows the first 25 numbers; with one argument shows that many; with two arguments shows results in the range.
Line 1,713 ⟶ 1,856:
if H.3=='' | H.3==',' then H.3=2006 /*H3 " " high " " " " */
mx=max(L.1, H.1, L.2, H.2, L.3, H.3) /*find how many
mx=mx+mx%10; ww=length(mx)*3 /*cushion; compensate for the triples.*/
w=ww%2; numeric digits max(9,ww) /*prepare to use some larger numbers. */
Line 1,754 ⟶ 1,897:
2: 4104 ───► 15^3 + 9^3 ──and── 16^3 + 2^3
3: 13832 ───► 20^3 + 18^3 ──and── 24^3 + 2^3
4: 20683 ───► 24^3 +
2: 4104 = 2 19^3 ──and── 27^3 + 10^3
5: 32832 ───► 30^3 + 18^3 ──and── 32^3 + 4^3
6: 39312 ───► 33^3 + 15^3 ──and── 34^3 + 2^3
| |||