views:

318

answers:

6

This has been a programming problem which has interested me for a while.

You give the program a squence of numbers seperated by commas. It then finds a suitable formula from these numbers to find the next number in the sequence.

In: 1,2,3,4,5
Out: 6

In: 2,4,6,8
Out: 10

In: 10,8,6,4
Out: 2

I'm not sure if this problem is much more complex than it appears, in which case it may not be suitable for code golf. I'm just suggesting it.

A: 

This problem illistrates how much better the brain is at pattern matching than is a computer program. This kind of this won't be easy at all to code. You have to program in an (in)finite amount of possible patterns and code to check them against input, hoping for a match - or multiple matches. That isn't a golf type problem.

Michael Dorgan
+4  A: 

(Copied from my comment above): actually, assuming the size of the input is finite, this is always solvable - you can fit an n-1 degree polynomial on any given n point sequence...

Trivially, in MATLAB (don't have an install with me, but it should work):

x = [1, 2, 3, 4]
y = [2, 4, 6, 8]
poly = polyfit(x, y, 3)
nextnum = polyval(poly, 5)

This creates a four-point polynomial with y as the input sequence, fits a 3rd degree polynomial to it and evaluates it at the next point (5). Of course, there are an infinite number of functions that will generate any given n points, so guessing the "right" next number is impossible. However, this will give you a function that produces your first n input numbers and then a next number. Not the point, perhaps, but it's all that can be done here.

tzaman
+1  A: 

This is not a programming problem. There are infinitely many suitable formulas, and finding a formula is not a particularly interesting problem. Finding a formula of a certain type may be an interesting or useful problem, depending on the type.

For example, given n values, there is always exactly one suitable formula that is a polynomial of degree n. This is often useful to prove other mathematical theorems, but doesn't have many practical applications.

A keyword for this kind of problem is interpolation. The three examples you've given are linear interpolations; finding out whether a linear interpolation is possible and what its result would be is a relatively easy golf problem.

The On-Line Encyclopedia of Integer Sequences is a website that gathers specific sequences that people have found interesting.

Gilles
Have to mention, OEIS is a brilliant resource for any project euler fans. :)
tzaman
+1  A: 

Mathematica

f = FindSequenceFunction[{#}, Length[{#}] + 1] &

>f[1,2,3,4,5]
6

>f[2,4,6,8]
10

>f[10, 8, 6, 4]
2

>f[1!, 2!, 3!, 4!, 5!]
720

>f[1, 4, 9, 16, 25]
36

>f[1, 1, 2, 3, 5, 8, 13] // Fibonacci numbers
21

>f[1, 1/2, 1/3, 1/4, 1/5, 1/6, 1/7] // Harmonics
1/8

>f[1, 1 + x, 1 + x + x^2, 1 + x + x^2 + x^3, 1 + x + x^2 + x^3 + x^4] // Polynomial sequences
(-1 + x^6)/(-1 + x)

>f[1, -1/2, 1/3, -1/4, 1/5, -1/6, 1/7] // Alternating signs
-1/8

>f[1^1, 2^2, 3^3, 4^4] // n^n sequence
3125

>f[Sin[Pi/4], 2 Sin[Pi/4], 3 Sin[Pi/4], 4 Sin[Pi/4]] // Trig series
5/Sqrt[2]
belisarius
+2  A: 

As some others already said: Assuming finite input, there will always be at least one polynomial fitting those points (or, for that matter, a sequence), so the following PowerShell script will always generate a valid next number for at least one of the sequences:

1

It's also just one byte long, so I guess it's golfy enough.

Joey
:) If you want to be pedantic, the original requirements _do_ mention finding "a suitable _formula_ (...) to find the next number in the sequence" ;)
tzaman
if you want to be pedantic, 1 is also a formula...
Sanjay Manohar
+1  A: 

J, 13 characters

(>:@$p.~p.@<)

Explanation:

>:@$  NB. One more than the size of the input list...
p.~   NB. ... substituted into the polynomial with coefficients...
p.@<  NB. ... the coefficients of the polynomial with roots specified by the input list

Usage:

   (>:@$p.~p.@<)  1 2 3
6

   (>:@$p.~p.@<)  10 8 6 4 
_15
David
cool!! you've inspired me to learn J!I do like "1 2 3 6" :)
Sanjay Manohar