News for hackers. Stuff that matters.
Re:9,73,241,561,1081,1849,_?_ by bdr on Thursday November 05, 2009 @01:08PM (#924317)
Well, that could be done by brute force. Realistically, though, it's more about whether anyone can beat your answer.
Re:9,73,241,561,1081,1849,_?_ by jcl on Thursday November 05, 2009 @03:10PM (#924647)
I don't know why you're being modded down.

To elaborate: You can define "simplest program", for instance, as "shortest string consisting of [0-9], plus, minus, times, parentheses, and the symbol 'n' that when evaluated as a mathematical expression yields the given sequence for n=1, 2, 3...". You can then find a suitable string, like "((8 * n + 4) * n - 4) * n + 1", and do an exhaustive search of shorter strings to show that no better string exists. That would be 16^16, or less than a year on a computer that can knock off a trillion strings per second -- less if you use logic to constrain the search space.

However, realistically, a person asking such a question is merely looking for a "good" solution, not necessarily a proven-optimal one, as there may be multiple reasonable explanations for a given sequence. Rather, the value of the "simplest program" criteria is that it allows you to compare proposed solutions. So, yes, for any given number, there is a formula to make it next in the sequence. But by applying the "simplest program" criteria, we see that some formulas -- and hence some values -- are better than others.

Re:9,73,241,561,1081,1849,_?_ by g__ on Thursday November 05, 2009 @04:46PM (#924852)
You'd have to determine if a program halts. Unless you restrict to non-Turing-complete language, this is undecidable.
Re:9,73,241,561,1081,1849,_?_ by jcl on Thursday November 05, 2009 @07:21PM (#925145)
You can simply modify your definition of "simplest" to be "shortest that completes in a million steps" or some such. A program that takes so long to finish that you're not sure it will return your desired value is probably not the simplest.
Re:9,73,241,561,1081,1849,_?_ by eru on Thursday November 05, 2009 @05:29PM (#924934)
I can decide if some programs halt. (Just not for all.)