Taxicab numbers: Difference between revisions

=={{header|Phix}}==

{{trans|Perl_6}}

Uses a dictionary to map sum of cubes to either the first/only pair or an integer index into the result set.

Turned out to be a fair bit slower (15s) than I first expected.

<lang Phix>

function get_taxis(integer last)

sequence taxis = {}

integer c1 = 1, maxc1 = 0, c2

atom c3, h3 = 0

while maxc1=0 or c1<maxc1 do

c3 = power(c1,3)

for c2 = 1 to c1 do

atom this = power(c2,3)+c3

integer node = getd_index(this)

if node=NULL then

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

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

for i=1 to 2006 do

sequence x = next_taxi()

if i<=25 or i>=2000 then

atom v = x[1][VALUE]

x[1] = x[1][DATA]

string y = sprintf("%11d+%-10d",sq_power(x[1],3))

for j=2 to length(x) do

y &= sprintf(",%11d+%-10d",sq_power(x[j],3))

end for

printf(1,"%4d: %10d: %-23s [%s]\n",{i,v,sprint(x),y})

end if

end for</lang>

{{out}}

<pre>

1: 1729: {{10,9},{12,1}} [ 1000+729 , 1728+1 ]

2: 4104: {{15,9},{16,2}} [ 3375+729 , 4096+8 ]

3: 13832: {{20,18},{24,2}} [ 8000+5832 , 13824+8 ]

4: 20683: {{24,19},{27,10}} [ 13824+6859 , 19683+1000 ]

5: 32832: {{30,18},{32,4}} [ 27000+5832 , 32768+64 ]

6: 39312: {{33,15},{34,2}} [ 35937+3375 , 39304+8 ]

7: 40033: {{33,16},{34,9}} [ 35937+4096 , 39304+729 ]

8: 46683: {{30,27},{36,3}} [ 27000+19683 , 46656+27 ]

9: 64232: {{39,17},{36,26}} [ 59319+4913 , 46656+17576 ]

10: 65728: {{40,12},{33,31}} [ 64000+1728 , 35937+29791 ]

11: 110656: {{40,36},{48,4}} [ 64000+46656 , 110592+64 ]

12: 110808: {{45,27},{48,6}} [ 91125+19683 , 110592+216 ]

13: 134379: {{51,12},{43,38}} [ 132651+1728 , 79507+54872 ]

14: 149389: {{50,29},{53,8}} [ 125000+24389 , 148877+512 ]

15: 165464: {{48,38},{54,20}} [ 110592+54872 , 157464+8000 ]

16: 171288: {{54,24},{55,17}} [ 157464+13824 , 166375+4913 ]

17: 195841: {{57,22},{58,9}} [ 185193+10648 , 195112+729 ]

18: 216027: {{59,22},{60,3}} [ 205379+10648 , 216000+27 ]

19: 216125: {{50,45},{60,5}} [ 125000+91125 , 216000+125 ]

20: 262656: {{60,36},{64,8}} [ 216000+46656 , 262144+512 ]

21: 314496: {{66,30},{68,4}} [ 287496+27000 , 314432+64 ]

22: 320264: {{68,18},{66,32}} [ 314432+5832 , 287496+32768 ]

23: 327763: {{67,30},{58,51}} [ 300763+27000 , 195112+132651 ]

24: 373464: {{60,54},{72,6}} [ 216000+157464 , 373248+216 ]

25: 402597: {{69,42},{61,56}} [ 328509+74088 , 226981+175616 ]

2000: 1671816384: {{1168,428},{944,940}} [ 1593413632+78402752 , 841232384+830584000 ]

2001: 1672470592: {{1124,632},{1187,29}} [ 1420034624+252435968 , 1672446203+24389 ]

2002: 1673170856: {{1164,458},{1034,828}} [ 1577098944+96071912 , 1105507304+567663552 ]

2003: 1675045225: {{1153,522},{1081,744}} [ 1532808577+142236648 , 1263214441+411830784 ]

2004: 1675958167: {{1159,492},{1096,711}} [ 1556862679+119095488 , 1316532736+359425431 ]

2005: 1676926719: {{1095,714},{1188,63}} [ 1312932375+363994344 , 1676676672+250047 ]

2006: 1677646971: {{990,891},{1188,99}} [ 970299000+707347971 , 1676676672+970299 ]

</pre>