Taxicab numbers: Difference between revisions
Content added Content deleted
(inserted Pascal) |
|||
Line 1,328: | Line 1,328: | ||
402597 = 61^3 + 56^3 |
402597 = 61^3 + 56^3 |
||
402597 = 69^3 + 42^3</pre> |
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}}== |
=={{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. |
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: | Line 1,856: | ||
if H.3=='' | H.3==',' then H.3=2006 /*H3 " " high " " " " */ |
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=max(L.1, H.1, L.2, H.2, L.3, H.3) /*find how many ta/sup> = 38xicab numbers needed.*/ |
||
mx=mx+mx%10; ww=length(mx)*3 /*cushion; compensate for the triples.*/ |
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. */ |
w=ww%2; numeric digits max(9,ww) /*prepare to use some larger numbers. */ |
||
Line 1,754: | Line 1,897: | ||
2: 4104 ───► 15^3 + 9^3 ──and── 16^3 + 2^3 |
2: 4104 ───► 15^3 + 9^3 ──and── 16^3 + 2^3 |
||
3: 13832 ───► 20^3 + 18^3 ──and── 24^3 + 2^3 |
3: 13832 ───► 20^3 + 18^3 ──and── 24^3 + 2^3 |
||
4: 20683 ───► 24^3 + |
4: 20683 ───► 24^3 + /sup> |
||
2: 4104 = 2 19^3 ──and── 27^3 + 10^3 |
|||
5: 32832 ───► 30^3 + 18^3 ──and── 32^3 + 4^3 |
5: 32832 ───► 30^3 + 18^3 ──and── 32^3 + 4^3 |
||
6: 39312 ───► 33^3 + 15^3 ──and── 34^3 + 2^3 |
6: 39312 ───► 33^3 + 15^3 ──and── 34^3 + 2^3 |