Euler's sum of powers conjecture: Difference between revisions
Content deleted Content added
m pow table has upper bound of 249 |
m →{{header|Phix}}: added syntax colouring, marked p2js compatible |
||
Line 3,015: | Line 3,015: | ||
Quitting when the first is found drops the main loop to 0.7s, so 1.1s in all, vs 4.3s for the full search.<br> |
Quitting when the first is found drops the main loop to 0.7s, so 1.1s in all, vs 4.3s for the full search.<br> |
||
Without the return 0, you just get six permutes (of ordered pairs) for 144. |
Without the return 0, you just get six permutes (of ordered pairs) for 144. |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">250</span> |
|||
constant p5 = new_dict(), |
|||
sum2 = new_dict() |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">p5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">(),</span> |
|||
<span style="color: #000000;">sum2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span> |
|||
atom t0 = time() |
|||
for i=1 to MAX do |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
atom i5 = power(i,5) |
|||
<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;">MAX</span> <span style="color: #008080;">do</span> |
|||
setd(i5,i,p5) |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">i5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> |
|||
for j=1 to i-1 do |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)</span> |
|||
atom j5 = power(j,5) |
|||
<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: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
setd(j5+i5,{j,i},sum2) |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">j5</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j5</span><span style="color: #0000FF;">+</span><span style="color: #000000;">i5</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">},</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
?time()-t0 |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span> |
|||
function forsum2(object s, object data, object p) |
|||
if p<=s then return 0 end if |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">forsum2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">)</span> |
|||
integer k = getd_index(p-s,sum2) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">s</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if k!=NULL then |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span> |
|||
?getd(p,p5)&data&getd_by_index(k,sum2) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> |
|||
return 0 -- (show one solution per p) |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">data</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (show one solution per p)</span> |
|||
return 1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function forp5(object key, object /*data*/, object /*user_data*/) |
|||
traverse_dict(routine_id("forsum2"),key,sum2) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">forp5</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">key</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*data*/</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000080;font-style:italic;">/*user_data*/</span><span style="color: #0000FF;">)</span> |
|||
return 1 |
|||
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">forsum2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sum2</span><span style="color: #0000FF;">)</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
traverse_dict(routine_id("forp5"),0,p5) |
|||
<span style="color: #7060A8;">traverse_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">forp5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p5</span><span style="color: #0000FF;">)</span> |
|||
?time()-t0</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |