Rosetta Code

Taxicab numbers: Difference between revisions

Page Discussion

Taxicab numbers (view source)

Revision as of 13:45, 13 April 2022

8,245 bytes added ,  2 years ago
→‎{{header|Phix}}: rewrote, syntax coloured, made p2js compatible
(Added Forth entry)
(→‎{{header|Phix}}: rewrote, syntax coloured, made p2js compatible)
Line 2,921:
 
=={{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}}
<pre>
First 25 Taxicab Numbers, 2000..2006th, and all interim triples:
1: 1729: {{10,9},{12,1}} [ 1000+729 , 1728+1 ]
2:1 4104:1729 {{15,9},{16,2}}= ( 1^3= [ 1) + ( 12^3= 3375+729 1728) or ,( 9^3= 4096 729) +8 ( 10^3= ]1000)
3:2 13832: {{20,18},{24,4104 = ( 2}}^3= [8) + ( 16^3= 8000+5832 4096) or ( , 9^3= 13824 729) +8 ( 15^3= ]3375)
4:3 20683:13832 {{24,19},{27,10}}= ( 2^3= [ 8) 13824+6859 ( 24^3= , 13824) or ( 18^3= 5832) 19683+1000 ( 20^3= ]8000)
5:4 32832:20683 {{30,18},{32,4}}= ( 10^3= 1000) [+ ( 27^3= 27000+5832 19683) or ( ,19^3= 6859) 32768+64 ( 24^3= ]13824)
6:5 39312:32832 {{33,15},{34,2}}= ( 4^3= [ 64) + ( 35937+337532^3= 32768) ,or ( 18^3= 39304+8 5832) + ( 30^3= ]27000)
7:6 40033:39312 {{33,16},{34,9}}= ( 2^3= [ 8) + ( 35937+4096 34^3= ,39304) or ( 15^3= 39304 3375) +729 ( 33^3= ] 35937)
8:7 46683:40033 {{30,27},{36,3}}= ( 9^3= [ 729) + ( 34^3= 27000+19683 39304) ,or ( 16^3= 46656 4096) +27 ( 33^3= ]35937)
9:8 64232:46683 {{39,17},{36,26}}= ( 3^3= [ 27) + ( 59319+4913 36^3= ,46656) or ( 27^3= 46656 19683) +17576 ( 30^3= ]27000)
10: 9 65728: {{40,12},{33,31}}64232 = ( 17^3= [ 4913) + ( 39^3= 64000+1728 59319) or ,( 26^3= 17576) 35937+29791 ( 36^3= ]46656)
11:10 110656: {{40,36},{48,4}}65728 = ( 12^3= [1728) + ( 40^3= 64000+46656 64000) or ( ,31^3= 29791) 110592+64 ( 33^3= ]35937)
12:11 110808:110656 {{45,27},{48,6}}= ( 4^3= [ 64) + ( 91125+1968348^3= 110592) ,or ( 36^3= 110592 46656) +216 ( 40^3= ]64000)
13:12 134379:110808 {{51,12},{43,38}}= ( 6^3= [ 216) + ( 132651+1728 48^3= 110592) ,or ( 27^3= 7950719683) +54872 ( 45^3= ]91125)
14:13 149389:134379 {{50,29},{53,8}}= ( 12^3= 1728) [+ ( 51^3= 125000+24389 132651) or ( ,38^3= 54872) 148877+512 ( 43^3= ]79507)
15:14 165464:149389 {{48,38},{54,20}}= ( 8^3= [ 512) + ( 110592+54872 53^3= ,148877) or ( 29^3= 157464 24389) +8000 ( 50^3= ]125000)
16:15 171288:165464 {{54,24},{55,17}}= ( 20^3= [8000) + ( 54^3= 157464+13824 157464) or ,( 38^3= 16637554872) +4913 ( 48^3= ]110592)
17:16 195841:171288 {{57,22},{58,9}}= ( 17^3= 4913) [+ ( 55^3= 185193+10648 166375) or ( ,24^3= 13824) 195112+729 ( 54^3= ]157464)
18:17 216027:195841 {{59,22},{60,3}}= ( 9^3= [ 729) + ( 205379+1064858^3= 195112) ,or ( 22^3= 216000+27 10648) + ( 57^3= ]185193)
19:18 216125:216027 {{50,45},{60,5}}= ( 3^3= [ 27) + ( 125000+91125 60^3= ,216000) or ( 22^3= 216000 10648) +125 ( 59^3= ]205379)
20:19 262656:216125 {{60,36},{64,8}}= ( 5^3= [ 125) + ( 216000+4665660^3= 216000) or ( ,45^3= 91125) 262144+512 ( 50^3= ]125000)
21:20 314496:262656 {{66,30},{68,4}}= ( 8^3= [ 512) + ( 287496+2700064^3= 262144) ,or ( 36^3= 314432+64 46656) + ( 60^3= ]216000)
22:21 320264:314496 {{68,18},{66,32}}= ( 4^3= [ 64) 314432+5832 ( 68^3= , 314432) or ( 30^3= 27000) 287496+32768 ( 66^3= ] 287496)
23:22 327763:320264 {{67,30},{58,51}}= ( 18^3= [5832) + ( 68^3= 300763+27000 314432) or ,( 32^3= 19511232768) +132651 ( 66^3= ]287496)
24:23 373464:327763 {{60,54},{72,6}}= ( 30^3= 27000) + [( 67^3= 216000+157464 300763) or ,( 51^3= 132651) 373248+216 ( 58^3= ]195112)
25:24 402597:373464 {{69,42},{61,56}}= ( 6^3= [ 216) + ( 328509+74088 72^3= ,373248) or ( 54^3= 226981 157464) +175616 ( 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>
 
Petelomax
7,806

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/242335"