Taxicab numbers: Difference between revisions
Content added Content deleted
(Added Forth entry) |
(→{{header|Phix}}: rewrote, syntax coloured, made p2js compatible) |
||
Line 2,921: | Line 2,921: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(phixonline)--> |
|||
{{trans|Raku}} |
|||
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Taxicab_numbers.exw</span> |
|||
Uses a dictionary to map sum of cubes to either the first/only pair or an integer index into the result set. |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
Turned out to be a fair bit slower (15s) than I first expected. |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">cube_sums</span><span style="color: #0000FF;">()</span> |
|||
<lang Phix>function get_taxis(integer last) |
|||
<span style="color: #000080;font-style:italic;">// create cubes and sorted list of cube sums</span> |
|||
sequence taxis = {} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cubes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
integer c1 = 1, maxc1 = 0, c2 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1189</span> <span style="color: #008080;">do</span> |
|||
atom c3, h3 = 0 |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">cube</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">i</span> |
|||
while maxc1=0 or c1<maxc1 do |
|||
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cube</span><span style="color: #0000FF;">)</span> |
|||
c3 = power(c1,3) |
|||
<span style="color: #000000;">cubes</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">cube</span> |
|||
for c2 = 1 to c1 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
atom this = power(c2,3)+c3 |
|||
<span style="color: #000000;">sums</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (706,266 in total)</span> |
|||
integer node = getd_index(this) |
|||
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">}</span> |
|||
if node=NULL then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
setd(this,{c2,c1}) |
|||
else |
|||
if this>h3 then h3 = this end if |
|||
object data = getd_by_index(node) |
|||
if not integer(data) then |
|||
taxis = append(taxis,{this,{data}}) |
|||
data = length(taxis) |
|||
setd(this,data) |
|||
if data=last then |
|||
maxc1 = ceil(power(h3,1/3)) |
|||
end if |
|||
end if |
|||
taxis[data][2] &= {{c2,c1}} |
|||
end if |
|||
end for |
|||
c1 += 1 |
|||
end while |
|||
destroy_dict(1,justclear:=true) |
|||
taxis = sort(taxis) |
|||
return taxis |
|||
end function |
|||
sequence taxis = get_taxis(2006) |
|||
constant sets = {{1,25},{2000,2006}} |
|||
for s=1 to length(sets) do |
|||
integer {first,last} = sets[s] |
|||
for i=first to last do |
|||
printf(1,"%d: %d: %s\n",{i,taxis[i][1],sprint(taxis[i][2])}) |
|||
end for |
|||
end for</lang> |
|||
{{out}} |
|||
<pre> |
|||
1: 1729: {{9,10},{1,12}} |
|||
2: 4104: {{9,15},{2,16}} |
|||
3: 13832: {{18,20},{2,24}} |
|||
4: 20683: {{19,24},{10,27}} |
|||
5: 32832: {{18,30},{4,32}} |
|||
6: 39312: {{15,33},{2,34}} |
|||
7: 40033: {{16,33},{9,34}} |
|||
8: 46683: {{27,30},{3,36}} |
|||
9: 64232: {{26,36},{17,39}} |
|||
10: 65728: {{31,33},{12,40}} |
|||
11: 110656: {{36,40},{4,48}} |
|||
12: 110808: {{27,45},{6,48}} |
|||
13: 134379: {{38,43},{12,51}} |
|||
14: 149389: {{29,50},{8,53}} |
|||
15: 165464: {{38,48},{20,54}} |
|||
16: 171288: {{24,54},{17,55}} |
|||
17: 195841: {{22,57},{9,58}} |
|||
18: 216027: {{22,59},{3,60}} |
|||
19: 216125: {{45,50},{5,60}} |
|||
20: 262656: {{36,60},{8,64}} |
|||
21: 314496: {{30,66},{4,68}} |
|||
22: 320264: {{32,66},{18,68}} |
|||
23: 327763: {{51,58},{30,67}} |
|||
24: 373464: {{54,60},{6,72}} |
|||
25: 402597: {{56,61},{42,69}} |
|||
2000: 1671816384: {{940,944},{428,1168}} |
|||
2001: 1672470592: {{632,1124},{29,1187}} |
|||
2002: 1673170856: {{828,1034},{458,1164}} |
|||
2003: 1675045225: {{744,1081},{522,1153}} |
|||
2004: 1675958167: {{711,1096},{492,1159}} |
|||
2005: 1676926719: {{714,1095},{63,1188}} |
|||
2006: 1677646971: {{891,990},{99,1188}} |
|||
</pre> |
|||
{{trans|C}} |
|||
Using a [[Priority_queue#Phix|priority queue]], otherwise based on C, quite a bit (18.5x) faster.<br> |
|||
Copes with 40000..6, same results as Go, though that increases the runtime from 0.8s to 1min 15s. |
|||
<lang Phix>sequence cubes = {} |
|||
procedure add_cube() |
|||
integer n = length(cubes)+1 |
|||
cubes = append(cubes,n*n*n) |
|||
pq_add({{n,1},cubes[n]+1}) |
|||
end procedure |
|||
constant VALUE = PRIORITY |
|||
function next_sum() |
|||
while length(pq)<=2 or pq[1][VALUE]>=cubes[$] do add_cube() end while |
|||
sequence res = pq_pop() |
|||
integer {x,y} = res[DATA] |
|||
y += 1 |
|||
if y<x then |
|||
pq_add({{x,y},cubes[x]+cubes[y]}) |
|||
end if |
|||
return res |
|||
end function |
|||
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cube_sums</span><span style="color: #0000FF;">()</span> |
|||
function next_taxi() |
|||
sequence top |
|||
while 1 do |
|||
top = next_sum() |
|||
if pq[1][VALUE]=top[VALUE] then exit end if |
|||
end while |
|||
sequence res = {top} |
|||
atom v = top[PRIORITY] |
|||
while 1 do |
|||
top = next_sum() |
|||
res = append(res,top[DATA]) |
|||
if pq[1][VALUE]!=v then exit end if |
|||
end while |
|||
return res |
|||
end function |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">nm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> |
|||
for i=1 to 2006 do |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> |
|||
sequence x = next_taxi() |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
if i<=25 or i>=2000 then |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"First 25 Taxicab Numbers, 2000..2006th, and all interim triples:\n"</span><span style="color: #0000FF;">)</span> |
|||
atom v = x[1][VALUE] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
x[1] = x[1][DATA] |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">np1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
string y = sprintf("%11d+%-10d",sq_power(x[1],3)) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">np1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">nm1</span> <span style="color: #008080;">then</span> |
|||
for j=2 to length(x) do |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">25</span> |
|||
y &= sprintf(",%11d+%-10d",sq_power(x[j],3)) |
|||
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">2000</span> <span style="color: #008080;">and</span> <span style="color: #000000;">idx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">2006</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> |
|||
printf(1,"%4d: %10d: %-23s [%s]\n",{i,v,sprint(x),y}) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
end if |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end for</lang> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cubes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> |
|||
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span><span style="color: #0000FF;"><</span><span style="color: #000000;">x</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ydx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">binary_search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cubes</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">ydx</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"(%3d^3=%9d) + (%4d^3=%10d)"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ydx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%4d %10d = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" or "</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">idx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">nm1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">np1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
First 25 Taxicab Numbers, 2000..2006th, and all interim triples: |
|||
1: 1729: {{10,9},{12,1}} [ 1000+729 , 1728+1 ] |
|||
1 1729 = ( 1^3= 1) + ( 12^3= 1728) or ( 9^3= 729) + ( 10^3= 1000) |
|||
2 4104 = ( 2^3= 8) + ( 16^3= 4096) or ( 9^3= 729) + ( 15^3= 3375) |
|||
3 13832 = ( 2^3= 8) + ( 24^3= 13824) or ( 18^3= 5832) + ( 20^3= 8000) |
|||
4 20683 = ( 10^3= 1000) + ( 27^3= 19683) or ( 19^3= 6859) + ( 24^3= 13824) |
|||
5 32832 = ( 4^3= 64) + ( 32^3= 32768) or ( 18^3= 5832) + ( 30^3= 27000) |
|||
6 39312 = ( 2^3= 8) + ( 34^3= 39304) or ( 15^3= 3375) + ( 33^3= 35937) |
|||
7 40033 = ( 9^3= 729) + ( 34^3= 39304) or ( 16^3= 4096) + ( 33^3= 35937) |
|||
8 46683 = ( 3^3= 27) + ( 36^3= 46656) or ( 27^3= 19683) + ( 30^3= 27000) |
|||
9 64232 = ( 17^3= 4913) + ( 39^3= 59319) or ( 26^3= 17576) + ( 36^3= 46656) |
|||
10 65728 = ( 12^3= 1728) + ( 40^3= 64000) or ( 31^3= 29791) + ( 33^3= 35937) |
|||
11 110656 = ( 4^3= 64) + ( 48^3= 110592) or ( 36^3= 46656) + ( 40^3= 64000) |
|||
12 110808 = ( 6^3= 216) + ( 48^3= 110592) or ( 27^3= 19683) + ( 45^3= 91125) |
|||
13 134379 = ( 12^3= 1728) + ( 51^3= 132651) or ( 38^3= 54872) + ( 43^3= 79507) |
|||
14 149389 = ( 8^3= 512) + ( 53^3= 148877) or ( 29^3= 24389) + ( 50^3= 125000) |
|||
15 165464 = ( 20^3= 8000) + ( 54^3= 157464) or ( 38^3= 54872) + ( 48^3= 110592) |
|||
16 171288 = ( 17^3= 4913) + ( 55^3= 166375) or ( 24^3= 13824) + ( 54^3= 157464) |
|||
17 195841 = ( 9^3= 729) + ( 58^3= 195112) or ( 22^3= 10648) + ( 57^3= 185193) |
|||
18 216027 = ( 3^3= 27) + ( 60^3= 216000) or ( 22^3= 10648) + ( 59^3= 205379) |
|||
19 216125 = ( 5^3= 125) + ( 60^3= 216000) or ( 45^3= 91125) + ( 50^3= 125000) |
|||
20 262656 = ( 8^3= 512) + ( 64^3= 262144) or ( 36^3= 46656) + ( 60^3= 216000) |
|||
21 314496 = ( 4^3= 64) + ( 68^3= 314432) or ( 30^3= 27000) + ( 66^3= 287496) |
|||
22 320264 = ( 18^3= 5832) + ( 68^3= 314432) or ( 32^3= 32768) + ( 66^3= 287496) |
|||
23 327763 = ( 30^3= 27000) + ( 67^3= 300763) or ( 51^3= 132651) + ( 58^3= 195112) |
|||
24 373464 = ( 6^3= 216) + ( 72^3= 373248) or ( 54^3= 157464) + ( 60^3= 216000) |
|||
25 402597 = ( 42^3= 74088) + ( 69^3= 328509) or ( 56^3= 175616) + ( 61^3= 226981) |
|||
2000: 1671816384: {{1168,428},{944,940}} [ 1593413632+78402752 , 841232384+830584000 ] |
|||
455 87539319 = (167^3= 4657463) + ( 436^3= 82881856) or (228^3= 11852352) + ( 423^3= 75686967) or (255^3= 16581375) + ( 414^3= 70957944) |
|||
2001: 1672470592: {{1124,632},{1187,29}} [ 1420034624+252435968 , 1672446203+24389 ] |
|||
535 119824488 = ( 11^3= 1331) + ( 493^3= 119823157) or ( 90^3= 729000) + ( 492^3= 119095488) or (346^3= 41421736) + ( 428^3= 78402752) |
|||
2002: 1673170856: {{1164,458},{1034,828}} [ 1577098944+96071912 , 1105507304+567663552 ] |
|||
588 143604279 = (111^3= 1367631) + ( 522^3= 142236648) or (359^3= 46268279) + ( 460^3= 97336000) or (408^3= 67917312) + ( 423^3= 75686967) |
|||
2003: 1675045225: {{1153,522},{1081,744}} [ 1532808577+142236648 , 1263214441+411830784 ] |
|||
655 175959000 = ( 70^3= 343000) + ( 560^3= 175616000) or (198^3= 7762392) + ( 552^3= 168196608) or (315^3= 31255875) + ( 525^3= 144703125) |
|||
2004: 1675958167: {{1159,492},{1096,711}} [ 1556862679+119095488 , 1316532736+359425431 ] |
|||
888 327763000 = (300^3= 27000000) + ( 670^3= 300763000) or (339^3= 38958219) + ( 661^3= 288804781) or (510^3=132651000) + ( 580^3= 195112000) |
|||
2005: 1676926719: {{1095,714},{1188,63}} [ 1312932375+363994344 , 1676676672+250047 ] |
|||
1299 700314552 = (334^3= 37259704) + ( 872^3= 663054848) or (456^3= 94818816) + ( 846^3= 605495736) or (510^3=132651000) + ( 828^3= 567663552) |
|||
2006: 1677646971: {{990,891},{1188,99}} [ 970299000+707347971 , 1676676672+970299 ] |
|||
1398 804360375 = ( 15^3= 3375) + ( 930^3= 804357000) or (198^3= 7762392) + ( 927^3= 796597983) or (295^3= 25672375) + ( 920^3= 778688000) |
|||
1515 958595904 = ( 22^3= 10648) + ( 986^3= 958585256) or (180^3= 5832000) + ( 984^3= 952763904) or (692^3=331373888) + ( 856^3= 627222016) |
|||
1660 1148834232 = (222^3= 10941048) + (1044^3=1137893184) or (718^3=370146232) + ( 920^3= 778688000) or (816^3=543338496) + ( 846^3= 605495736) |
|||
1837 1407672000 = (140^3= 2744000) + (1120^3=1404928000) or (396^3= 62099136) + (1104^3=1345572864) or (630^3=250047000) + (1050^3=1157625000) |
|||
2000 1671816384 = (428^3= 78402752) + (1168^3=1593413632) or (940^3=830584000) + ( 944^3= 841232384) |
|||
2001 1672470592 = ( 29^3= 24389) + (1187^3=1672446203) or (632^3=252435968) + (1124^3=1420034624) |
|||
2002 1673170856 = (458^3= 96071912) + (1164^3=1577098944) or (828^3=567663552) + (1034^3=1105507304) |
|||
2003 1675045225 = (522^3=142236648) + (1153^3=1532808577) or (744^3=411830784) + (1081^3=1263214441) |
|||
2004 1675958167 = (492^3=119095488) + (1159^3=1556862679) or (711^3=359425431) + (1096^3=1316532736) |
|||
2005 1676926719 = ( 63^3= 250047) + (1188^3=1676676672) or (714^3=363994344) + (1095^3=1312932375) |
|||
2006 1677646971 = ( 99^3= 970299) + (1188^3=1676676672) or (891^3=707347971) + ( 990^3= 970299000) |
|||
</pre> |
</pre> |
||