Comment by gizmo686
11 years ago
Does the algorithm need to terminate? It seems like convergence would be sufficient. For example, we have no terminating algorithm to produce pi, but we have plenty of ways to precisly express it.
Of course, given the nature of this problem, you can define your converging algorithm to terminate when it is withing a certain error of what the "pure" answer would be. Of course, it is possible you would underestimate the number, and if someone could beet you by using the same method with a slightly different termination condition, so you may want to add 1...
Good point, although this problem involves only integers, so I'm not sure if "convergence" makes sense. Pi, of course, is a computable number, implying that there is a terminating algorithm that, given input n, outputs the nth digit of pi's decimal representation.