solution to "what's the next number in this sequence?" problems

[almostbusto]

Well I am sure this math problem has been solved, its not very difficult, but i can't find it published anywhere. I want to compare the standard published solution to mine just to see how ugly mine is.


anyway here's the problem:

every math nerds knows that given a sequence like 1, 2, 3, 4.... or 1, 4, 9, 16... that the next number can actually be any real number. meaning that there is a function that maps the first five positive integers to 1, 2, 3, 4, X where X is any real.



so I was thinking about IQ tests which always seem to ask about the next number in a sequence and how idiotic that is. I quickly decided that a better question is to ask for a function that maps the first N positive integers to N given numbers. Eventually i decided that might not be a good question either if there was an algorithmic solution that could be executed for any sequence. I was sure there was such an algorithm.


a bit later i am in the shower and going over this again and i come up with an algortihm that will map the first N integers to any possible sequence of real numbers of length N. you give me the sequence you want, ill give you the function.


so its not that hard of a problem, feel free to post your solutions in this thread.

edit: found this link http://qntm.org/1111 which seems to have a method. his method is prettier in some ways. i always knew that a nth degree polynomial can be made to pass through any N points. This is something they cover in first year regression (a regression with N data points and N regressors will always have perfect fit). however, a person taking an IQ test can't just solve N simultaneous equations instantly. my solution is instant, you give me the numbers and then i can immediately start writing the solution.

EDIT2: a second similar link http://mathforum.org/library/drmath/view/56864.html

[almostbusto]

just to clarify. My solution is a formula, not actually an algorithm. i was wondering if there were any other formulas out there.

[m_the0ry]

The reason why they are included on IQ tests is the exact reason why you are arguing they shouldn't be. You're talking about pattern recognition, something that has stumped computers since their inception and yet humans appear to be able to systematically doing it. Yes, the prediction is always 100% conjecture and there is a reasonable justification for any and all possible answers. There is no algorithm to apply to pattern recognition that applies to all patterns. And yet once a pattern is exposed, it is forever after obviously apparent.

It is in this sense that pattern recognition is a measurement of your ability to 'self-teach'.

Note that there is a new line of computer research that seeks to model the neocortex at a simple and yet infinitely extensible way (search google or wikipedia for 'numenta') allowing it to 'self-teach' with exposure to data. What I said about computers and there being no algorithm for all pattern detection is something considered classically true but that may be proven untrue in the near future.

[almostbusto]

yea yea yea... i get all that, i wasn't making an argument about iq tests. i have solved a whole class of problems with a single formula, i was wondering if this formula already exists or not. my solution seems to be too ugly but i can't think of a better way to write it.

anyway to address your comment somewhat, the whole point is that there is an infinite number of patterns represented by the one sequence. iq tests are just looking for the "most obvious" one. which does add subjectivity into the mix. in most cases though, there isn't a "very obvious" second choice. so that shouldn't be too much of a problem. the test will still be practical.

however, you probably shouldn't penalized a smart kid (like me [img]/images/graemlins/smile.gif[/img] ) who can write in his own numbers and justify each one with a formula since that answers the question equally as well.

[BruceZ]

Map 1,2,3,4,5 ==> x1, x2, x3, x4, x5

Solution:

F(n) = F1(n) + F2(n) + F3(n) + F4(n) + F5(n)

where

F1(n) = x1

F2(n) = (n-1)*[x2 - F1(2)]

F3(n) = (n-1)*(n-2)*[x3 - F1(3) - F2(3)]/2!

F4(n) = (n-1)*(n-2)*(n-3)*[x4 - F1(4) - F2(4) - F3(4)]/3!

F5(n) = (n-1)*(n-2)*(n-3)*(n-4)*[x5 - F1(5) - F2(5) - F3(5) - F4(5)]/4!

[m_the0ry]

[ QUOTE ]
however, you probably shouldn't penalized a smart kid (like me [img]/images/graemlins/smile.gif[/img] ) who can write in his own numbers and justify each one with a formula since that answers the question equally as well.

[/ QUOTE ]

definitely agree. Like I said there's a 100% logical and true justification for any possible answer; the answers only vary in complexity. Finding a more complex answer with proper justification I would argue deserves greater recognition because it highlights the ability to think outside the box.

And as Einstein said, "imagination is more important than knowledge"

[almostbusto]

Bruce nice solution. I think yours is cleaner than mine, though mine is not in anyway recursive so it might be more intuitive for some.



mine was:

let
A1,A2,A3.... An be the target sequence


S=Z1+Z2....+Zn

Z1= (2-x)(3-x)....(n-x)*(A1/(n-1!)
Z2= (1-x)(3-x).....(n-x)*(A2/(-1*(n-2)!))
.
.
.
Zk=(1-x)(2-x)(3-x).....(k-1-x)(k+1-x)...(n-x)(Ak/([(-1)^(k-1)](k-1)!*(n-k)!)
.
.
.
Zn=(1-x)(2-x).....(n-1-x)(An/[(-1)^(n-1)](n-1)!)


i think thats right. you need the -1^X bit because (-x)! isn't defined. it isn't defined right? i have never seen that, there is no reason not to define it as x!*(-1)^x though.


if you notice, my solution is a polynomial of order n. which is what those two links mention doing. however this formula is a lot easier to execute than solving n simultaneous equations.