Talk:Babbage problem: Difference between revisions
m
→Efficiency
m (→Efficiency) |
|||
Line 129:
The task calls for an efficient solution. If n<sup>2</sup> ends in 6 then n must end in 4 or 6 which eliminates 80% of the values of n being tested by many (I don't want to say all in case a solution has done this but I couldn't see one) of the solutions being offered. This logic can be extended but I'll settle for the easy 80%.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 18:09, 21 December 2022 (UTC)
:The worst case is 25,264 iterations (sometimes -519), but of course yields the easiest to understand solution, slightly better half that (even only, sometimes -262), slightly better (ends in 4 or 6, as per F# and several others) is 5,057 iterations, slightly better (multiples of 8) 3,158 iterations, even better (prefix*1e6+269696) 638 iterations, and my own Phix/proper method (and I think Tcl.2 and Unix shell.2) builds candidate lists and gets there
|