I guess all of you know the questions on intelligence tests where you get a series of integers and you have to predict the next integer. Examples:

2  4  6  ... (8)

1  4  9  ... (16) 

3  1  6  4  9  ... (7)

Well, what people can, computers can do better! The challenge is to build a program that takes a series of such numbers as input and correctly outputs the next number in the sequence. Or, if you're lazy, tell us how you would solve this problem.

For short sequences, this is part of the great unsolved problem in machine learning: how the hell does the human mind do that? We have never been able to construct anything with anywhere near the same level of ability to find unanticipated patterns in effectively arbitrary data. (Of course, the mind usually goes too far, and finds patterns that don't actually exist, but we still don't know how it works)

If you expand the problem so that the series of integers provided in each case is a couple thousand elements long, you can do it with any of the standard generic pattern-creating mechanisms, like genetic algorithms or neural networks, combined with the assumption that the series is a relatively simple arithmetic function. They suck compared to humans, though, and would never be able to figure out something like:

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)
 

bouk:

Or, if you're lazy, tell us how you would solve this problem.

Something involving wget (or similar) and http://www.research.att.com/~njas/sequences probably.

Though it didn't catch your 3rd sequence. The next number I suspect being 12.

Or 13 if you're a baker.   Or a pedant on /.

I think a bigger issue here is that for an arbitrary sequence of digits, there is probably more than one pattern that can generate that sequence, so there might be an unbounded number of correct next entries.  There's also likely the effect of entropy of the sequence - that is, how many numbers are required to determine the sequence? If I just give the number '1' then what comes next?  If I give '1' '2' what comes next (is it 3? or is it 4? Or something else?)  There is also hidden information, in that the AI had to know that the sequence of numbers is a "pattern" and not some other data stream.

So to solve this I think you have to first know that the pattern does indeed only have a single "correct" interpretation, or at least a known set of interpretations, and be able to evaluate the results by that.  That, of course, is a completely different and also-difficult problem!
 

In theory, I'd solve it like this 

First you generate a giant two dimensional array containing all the possible ways to generate a sequence you can think of.  For example:

{ 1, 1, 1, 1, 1 }, // f(n) = 1

{ 1, 2, 3, 4, 5 }, // f(n) = n

{ 1, 4, 9, 16, 25 }, // f(n) = n^2

{ 1, 1.4 1.6, 2, 2 and a little bit }, // f(n) = log n

{ 1, 1, 2, 3, 5 } // f(n) = f(n-1) + f(n-2)

and so on...

multiply these with other simple sequences like

g(n) = -1^n * f(n)

Then we run a massive OLS regression over the whole thing trying the sequences in small batches (since the user isn't going to be nice enough to enter the first 100 digits of the sequence and we want to break all the good statistical practices).  Compare the R-squared values (again because good statistical practices are for wimps).  And output the best fit.

In practice:

@seq = qw| 1 2 3 4 5 |;
$res = '';
$last = 0;
$cnt = 0;
while (@seq)
{
    $this = shift @seq;
    $diff = $this - $last;
    next if $diff == 0;
    print $this - $last, " * " if $this - $last != 1;
    print "u( x )" if not $cnt;
    print "u( x - ", $cnt ," )" if $cnt;
    print " + " if @seq;
}
continue
{
    $cnt++;
    $last = $this;
}

bouk:

I guess all of you know the questions on intelligence tests where you get a series of integers and you have to predict the next integer. Examples:

2  4  6  ... (8)

1  4  9  ... (16) 

3  1  6  4  9  ... (7)

Well, what people can, computers can do better! The challenge is to build a program that takes a series of such numbers as input and correctly outputs the next number in the sequence. Or, if you're lazy, tell us how you would solve this problem.

PJH:

Though it didn't catch your 3rd sequence. The next number I suspect being 12.

poopdeville:

I'm sure your reasoning for 12 is just as convincing.

Doubtful. I've just had another look at the sequence and (after only 3 pints of beer) can't be bothered working out how I got 12. It was probably some obfuscated method designed to allow me to involve the link to the slashdot post.

And no, that isn't a convincing reason.
 

poopdeville:

Weak. This problem is insoluble.

poopdeville:

PJH:

Though it didn't catch your 3rd sequence. The next number I suspect being 12.

Think of it as a sequence of pairs (x_n, x_n - 2). x_n can be arbitrary, but it uniquely determines this sequence. Still, it's a bullshit question. I'm sure your reasoning for 12 is just as convincing. A finite prefix to a sequence does not determine the sequence. Some answers, like 7 and 12 are more intuitive, but 9001 makes just as much mathematical "sense".

x = 3;
for (var i=0; i < 5; i++) {
   document.write(x +', ');
   x-=2;
   document.write(x +', ');
   x+=5;
}

or,

an interleaved +3 sequence, starting at 0 (not shown) and 1 (second number), respectively. 

It seems to me 7 is the only sensible answer.

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)

ummm....

3 5 9 4 2 4 2
3 5 8 7 2 7 8
3 5 7 ? 2 ? ?

On a related note, 4 is the magic number.

Do you know why?  because 4 is 4 is 4 is 4!  No other number possesses this property!

for instance:   10 is 3 is 5 is 4.     11 is 6 is 3 is 5 is 4.   in fact, 193 is 21 is 9 is 4.   Go figure!

write a program to figure out why 4 is the magic number. 

dhromed:

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)

ummm....

3 5 9 4 2 4 2
3 5 8 7 2 7 8
3 5 7 ? 2 ? ?

No. The next few would be (3) 3 4 4 3 5 4 2 4.

(You're up the wrong tree)
 

tster:

On a related note, 4 is the magic number.

 

Do you know why?  because 4 is 4 is 4 is 4!  No other number possesses this property!

for instance:   10 is 3 is 5 is 4.     11 is 6 is 3 is 5 is 4.   in fact, 193 is 21 is 9 is 4.   Go figure!

 

write a program to figure out why 4 is the magic number. 

#!/usr/bin/perl -w
use strict;
my @t1 = qw(zero one two three four five six seven eight nine ten
eleven twelve thirteen fourteen fifteen sixteen seventeen
eighteen nineteen);
my @t2 = qw(zerty onety twenty thirty forty fifty sixty seventy eighty ninety);

sub convert {
    local $_ = $_[0];
    return "Err" unless /^\d{0,12}$/;
    s/(\d+)(\d{9})$/$1 billion $2/;
    s/(\d+)(\d{6})$/$1 million $2/;
    s/(\d+)(\d{3})$/$1 thousand $2/;
    s/0(\d\d)/$1/g;
    s/([1-9])(\d\d)/$t1[$1] hundred $2/g;
    s/([2-9])(\d)/$t2[$1] $t1[$2]/g;
    s/00( \w+ )?//g; #avoid "two million zero thousand" and friends.
    s/([01]?)(\d)/$t1[ $1 . $2]/eg;
    s/ //g;
    return length($_);
}
while($#ARGV > -1 ){
    my $num = shift(@ARGV);
    my $conv = convert($num);
    print("$num is $conv\n");
}

Often, these kind of number sequences are of defined by a simple arithmetic recursive formula (polynomial).

Sometimes there may be two polynomials, depending on the oddity of n, like the OP's third sequence. If you look at the number sequence modulo a prime, the arithmetic continuous to be valid and you will usually find a repeated pattern. If there is no pattern, that's a clue the sequence may not be arithmetic.

asuffield:

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3) 3 4 4 3 5 4 2 4

3 5 9 4 2 4 2 3 5 8 7 2 7 8 3 3 4 4 3 5 4 2 4
1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 (mod 2)
0 2 0 1 2 1 2 0 2 2 1 2 1 2 0 0 1 1 0 2 1 2 1 (mod 3)
2 0 4 4 2 4 2 3 0 3 2 2 2 3 0 0 1 1 3 0 1 0 1 (mod 5)

No pattern whatsoever, so I bet it's not arithmetic. The only thing obvious is that elements are all prime powers, and small primes at that. For any integer x, define PP(x) = p^k, where p is the smallest prime divisor of x and k its multiplicity (i.e. p^k divides x but p^k+1 does not). My guess is that asuffield's diabolical sequence (a₁, ..., a_n) is of the form (PP(x₁), ..., PP(x_n) ) for an simpler, hopefully arithmetic sequence (x₁, ..., x_n).

dhromed:

poopdeville:

PJH:

Though it didn't catch your 3rd sequence. The next number I suspect being 12.

Think of it as a sequence of pairs (x_n, x_n - 2). x_n can be arbitrary, but it uniquely determines this sequence. Still, it's a bullshit question. I'm sure your reasoning for 12 is just as convincing. A finite prefix to a sequence does not determine the sequence. Some answers, like 7 and 12 are more intuitive, but 9001 makes just as much mathematical "sense".

x = 3;
for (var i=0; i < 5; i++) {
   document.write(x +', ');
   x-=2;
   document.write(x +', ');
   x+=5;
}

or,

an interleaved +3 sequence, starting at 0 (not shown) and 1 (second number), respectively. 

It seems to me 7 is the only sensible answer.

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)

ummm....

3 5 9 4 2 4 2
3 5 8 7 2 7 8
3 5 7 ? 2 ? ?

I suppose such programs are not very interesting as long as they only compare given sequence to fit with hardcoded types. And making one that could crack sequences that it's author couldn't would probably require some major thinking out of the box.

Somewhat interestingly, finding continuations of polynomial sequences is more or less what the difference machine, the 'first computer' did.

We could apply the idea to predict next integer in a sequence given by any polynomial formula

E.g. 3n^3 - 5n^2 yields:

-2  4 36 112 250 ... (468)

Differences between the elements are: 

6 32 76 138

And again: 

26 44 62

18 18 ...

then we can reconstruct:

26 44 62 80

6 32 76 138 218
and finally -2  4 36 112 250 468
(without actually finding what the formula is)

bouk:

I guess all of you know the questions on intelligence tests where you get a series of integers and you have to predict the next integer.

The problem does not make any sense to me, and never did. There is a polynomial solution to every sequence, that can be constructed efficiently.

 If you've got a sequence n[0], n[2], n[3], ...,n[k], you can fit a polynomial of degree k as follows:

- suppose f(m) = sum(c[i]*x^i, 0<=i<=k) = n[m]

- then n[0] = c[0], n[1] = c[0] + c[1] * 1 + c[2] * 1^2 + ..., n[2] = c[0] + c[1] * 2 + c[2] * 2 ^ 2 + ...

- solve the system of k+1 linear equations with k unknowns

- if the solution doesn't exist, take out one of the numbers of the sequence (as it is dependent on the others) and try again.

Then, simply compute f(k + 1).

Like this, you would quickly find out that the first series matches f(m) = 2 + 2 * m, and f(3) = 8. The second one is f(m) = 1 + 2m + m^2, and f(3) = 16. The last one is f(m) = 3 - 17.2 * m + 23.3 * m^2 - 9.3 * m^3 + 1.2 * m^4, which makes the next number ... 63!

asuffield:

For short sequences, this is part of the great unsolved problem in machine learning: how the hell does the human mind do that? We have never been able to construct anything with anywhere near the same level of ability to find unanticipated patterns in effectively arbitrary data. (Of course, the mind usually goes too far, and finds patterns that don't actually exist, but we still don't know how it works)

If you expand the problem so that the series of integers provided in each case is a couple thousand elements long, you can do it with any of the standard generic pattern-creating mechanisms, like genetic algorithms or neural networks, combined with the assumption that the series is a relatively simple arithmetic function. They suck compared to humans, though, and would never be able to figure out something like:

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)
 

3 4 4 3 5 4 2 4 2 4 5 4 4 2 9 8 4 8 4 3 4 5 2 7 2 4 13 8 2 11 9 4 2 6 3 4 7 4 3 3 3 5 8 4 4 8 5 3 2 5 4 4 3 2 5

<snip>

1 1 1 1 1 1 1 1 1 1 1 1 1 1 (1)

Hatshepsut:

asuffield:

For short sequences, this is part of the great unsolved problem in machine learning: how the hell does the human mind do that? We have never been able to construct anything with anywhere near the same level of ability to find unanticipated patterns in effectively arbitrary data. (Of course, the mind usually goes too far, and finds patterns that don't actually exist, but we still don't know how it works)

If you expand the problem so that the series of integers provided in each case is a couple thousand elements long, you can do it with any of the standard generic pattern-creating mechanisms, like genetic algorithms or neural networks, combined with the assumption that the series is a relatively simple arithmetic function. They suck compared to humans, though, and would never be able to figure out something like:

3 5 9 4 2 4 2 3 5 8 7 2 7 8 (3)
 

3 4 4 3 5 4 2 4 2 4 5 4 4 2 9 8 4 8 4 3 4 5 2 7 2 4 13 8 2 11 9 4 2 6 3 4 7 4 3 3 3 5 8 4 4 8 5 3 2 5 4 4 3 2 5

<snip>

1 1 1 1 1 1 1 1 1 1 1 1 1 1 (1)

 

 Ok, this is bugging the hell out of me.  This isn't one of those esoteric patterns that have to do with the order of something not mathematical (like the 4 is 4 is 4 is 4 one?)

 The closest I got was N[x] = (N[x-1] + N[x-2] + k[x]) mod 10, where k[0] = 3 and k[x]=k[x-1] - 1.

For example:

3 = 0+0+3

5 = 0+3+2

9 = 3+5+1

4 =(5+9+0) mod 10

2 =(9+4-1) mod 10

4 = 4+2-2

3 = 2+4-3

and the pattern broke here...

4+3-4 should equal 3, but the pattern states a 5.

ARGH!  Gimme a hint
 

ebs2002:

ARGH!  Gimme a hint

 

This isn't one of those esoteric patterns that have to do with the order of something not mathematical (like the 4 is 4 is 4 is 4 one?)

Ironic that you quoted this example and still didn't see it. It's really quite simple, particularly when you realise that I was describing something which a generic piece of software could never solve.

By the power invested in these sequences by the Law of Small Numbers, I declare that the n+1 term of each series to be 42. Prove me wrong.

I think it's fair to say that for any given set/sequence of numbers, there'll be an infinite number of supersets that contain the sequence. All you're doing is picking out the easy ones that can be done with simple (or at least simplified) math.

MarcB:

By the power invested in these sequences by the Law of Small Numbers, I declare that the n+1 term of each series to be 42. Prove me wrong.

I think it's fair to say that for any given set/sequence of numbers, there'll be an infinite number of supersets that contain the sequence. All you're doing is picking out the easy ones that can be done with simple (or at least simplified) math.

And it's only been about four months since the last time somebody said that in this thread.

Don't people read before they post? 

asuffield:

ebs2002:

ARGH!  Gimme a hint

 

This isn't one of those esoteric patterns that have to do with the order of something not mathematical (like the 4 is 4 is 4 is 4 one?)

Ironic that you quoted this example and still didn't see it. It's really quite simple, particularly when you realise that I was describing something which a generic piece of software could never solve.

3 4 6 5 2 2 3 3 9 2 3 8 4 4 1 3 2 (3)

*forehead slap*