Algorithm do discovery number patterns

Question

Well, i must develop a software that can discovery a pattern in sequence of numbers, ex:

First Pattern: 10,20,30,40,50.. (The software must understand that numbers are always count +10).

Second Pattern: 1,3,5 ... ( The software must understand that numbers are always odd).

So, the pattern is defined by user and the software must continue the sequence. Exists some algorithm wit this propose ?

PS: I'm thinking about I.A techniques, like BackPropagation or something else, but this is better solution ? Don't have a more easy solution ?

Answer 1

The only solution I can see is to write a function to check for every possible pattern and then output the once that return true. So you take the first value check how much is added and then check if the next one is equally bigger. Then check if the others follow said pattern. Do note that your first and second example would given this algorithm both have the same type of pattern (new value = last value + constant).

So in pseudoishcode your first function would look something like this:

  step=value[1]-value[0]
   for (value as i)
      if (value[i]-value[i-1]!=step)
         return false
return true

Next you might want to start looking for a way to detect primes which I would advice to search for as it's a common algorithm.

An alternative if you think there really are going to be nearly infinite possible sequences I suggest you look into gennetic programming. And then use the number of matching numbers as fitness function of your program. However this only works if you have a very large number of available data points and might not even function at all. Another problem is that this way you will be unable to output the correct answer and merely be able to predict future answers.

Answer 2

Both of the problems you suggest are linear, and therefore have solutions in the form

y = mx + c

For example, your first is m==10, c==10 and your second is m==2, c==1.

Determining linear relationships like this is trivial to do, and using techniques to determine more complex relationships can be done, but teaching software what they "mean" (e.g. "odd numbers") is more-or-less impossible. For example, to find the "nature" of the relationship for

2, 3, 5, 7, 11, 13

You would probably have to write a specific test with the relationship already in mind.

Answer 3

To make an algorithm capable of learning anything, you need an inductive bias that will restrict your search space to a smaller space, or makes your algorithm prefer some hypotheses over others.

The space of your search is the space of all the functions from integers to integers. This space is too wide to make a practical algorithm. You have to choose a smaller space.

See also the Ugly duckling theorem and the No free lunch theorem in search and optimization.

Answer 4

Suppose you are given a0, a1, ..., ak. You can go for several patterns:

1. polynomial sequence, Ansatz an = c0 + c1*n + c2*n^2 + ... + ck*n^k: . Through the k+1 points (0,a0), (1,a1), ... (k,ak) you can always fit a polynomial of degree k. Now that is not very interesting in the general case, but if the highest order coefficient(s) ck is zero, then the last sequence number ak fits to the polynomial defined by the previous sequence numbers. This way you can find odd numbers, square numbers, triangle numbers (1, 1+2, 1+2+3, ...) etc.

2. linear recursion, Ansatz an = c0 + c1 * a(n-1) + ... + cm*a(n-m): You need m+1 equations for a linear recursion of order m. This way you can find sequences like the Fibonacci numbers (an = a(n-1) + a(n-2)), but also geometric sequences (e.g. 1,2,4,8,...) and sequences like 1, 11, 111, ... (an = 10*a(n-1)+1). Here are the m+1 equations:

   am = c0 + c1 * a(m-1) + ... + cm*a0

   a(m+1) = c0 + c1 * am + ... + cm*a1 ...

   a(2m) = c0 + c1 * a(2m-1) + ... + cm*am

   So you can set m=floor((k-1)/2) s.t. 2m<k and then check if the recursion also holds for ak and possibly a(k-1).

There are other patterns, but these two are already very powerful and cover many cases.