+- CC Zone - Chip's Challenge Forum (https://forum.bitbusters.club)
+-- Forum: Non-Chip's Challenge (https://forum.bitbusters.club/forum-6.html)
+--- Forum: Games and Trivia (https://forum.bitbusters.club/forum-23.html)
+--- Thread: Sequences (/thread-2175.html)
Sequences - BitBuster - 26-Apr-2012
...does it still work for a random string of numbers? I'm guessing there has to be SOME pair of numbers that divides in such a way (rational or otherwise) as to produce the string of numbers, but...
Sequences - geodave - 26-Apr-2012
Quote:...does it still work for a random string of numbers? I'm guessing there has to be SOME pair of numbers that divides in such a way (rational or otherwise) as to produce the string of numbers, but...
Yes. I don't want to totally geek out here (too late!), but Klein (I think it was him) basically proved that there is a mathematical formula for ANY finite sequence of numbers. If you think about it, that kind of makes sense. Anyway, Gödel used it in his incompleteness proof, which is one of the greatest things ever that no one knows about.
You can always use a polynomial approximation to get a valid "next number" in a sequence. You just have to make the power high enough to give you enough unknowns and enough formulas. (Or you can let a computer solve the matrix for you.)
OR, and this is incredibly math-geeky, you can use repeated differences to come up with a next number:
1,3,7,24,46,111,.....
2,4,17,18,65
2,13,1,43
11,-12,42
-23,54
77
77,77
-23,54,131
11,-12,42,173
2,13,1,43,216
2,4,17,18,65,281
1,3,7,24,46,111,392
Which, in theory, is a six-degree polynomial. I'm not going to bore you with that derivation.
Sequences - BitBuster - 26-Apr-2012
I'd be interested in that derivation. This discussion is strangely engrossing. I'm starting to hate myself for it.
Sequences - IceyLava108 - 26-Apr-2012
C, H _ _
Sequences - BitBuster - 27-Apr-2012
^C, H, I, P?
(I dunno. I fail.)
Back to one of the previous examples...
Say the sequence was:
1, 2, 3, 4, 5, 126, 127.
By repeated differences (correct me if I'm getting this wrong), we'd get:
1,1,1,1,121,1
0,0,120
0,120
120
120, 120
...ok, I'm lost. There's a reason why I did all I could to avoid math classes in college.
Sequences - geodave - 27-Apr-2012
You have to take the difference of every two numbers, so each list has one less number:
1, 2, 3, 4, 5, 126, 127
1,1,1,1,121,1
0,0,0,120,-120
0,0,120,-240
0,120,-360
120,-480
-600
(then add the last number again)
-600,-600
(now move back up the lists, adding a new number to the end)
120,-480,-1080
0,120,-360,-1440
0,0,120,-240,-1680
0,0,0,120,-120,-1800
1,1,1,1,121,1,-1799
Now, this can seem very counter-intuitive. However, if you use the polynomial method you'll get a similar result. This is a high-order equation which eventually dives very negative. That's probably the only way you get a curve that hits 1 all those times with 121 in the middle.
It's a lot more common to use this method for increasing sequences:
1,3,6,10,15
2,3,4,5
1,1,1
1,1,1,1 (you can go back up once all the numbers are the same)
2,3,4,5,6
1,3,6,10,15,21
I'll make a separate posting on the polynomial method.
Sequences - BitBuster - 27-Apr-2012
A high order equation? Eh? Is it possible to derive the equation, or do we just "know" that it exists.
Also, is there a theoretical limit on the number of valid answers to any given sequence?
Sequences - geodave - 27-Apr-2012
The polynomial process for solving equations involves creating a set of equations based on the known numbers in the sequence.
For example, if your sequence is
1,4,10,20
You can make the following set of equations:
an<sup>3</sup> + bn<sup>2</sup> + cn + d = f(n) for all n
a + b + c + d = 1
8a + 4b + 2c + d = 4
27a + 9b + 3c + d = 10
64a + 16b + 4c + d = 20
(You can only get as many unknowns and equations as you have numbers in the sequence.)
Now you solve by subtracting successive equations. I won't show all my work.
7a + 3b + c = 3
19a + 5b + c = 6
37a + 7b + c = 10
12a + 2b = 3
18a + 2b = 4
6a = 1
a = 1/6
b = 1/2
c = 1/3
d = 0
Therefore the next number in the sequence is:
125a + 25b + 5c + d =
125/6 + 25/2 + 5/3 + 0 =
(125 + 75 + 10) / 6 = 210/6 = 35
If you use the difference method:
1,4,10,20
3,6,10
3,4
1
1,1
3,4,5
3,6,10,15
1,4,10,20,35
You can sort of see they use the same numbers.
Now, this gets very messy very quickly, so I recommend using Excel instead.
Sequences - BitBuster - 27-Apr-2012
Quote:an<sup>3</sup> + bn<sup>2</sup> + cn + d = f(n) for all n
a + b + c + d = 1
8a + 4b + 2c + d = 4
27a + 9b + 3c + d = 10
64a + 16b + 4c + d = 20
...so the coefficients are always the same; only the numbers at the end change? And so I assume that if you had five numbers in the sequence, you would include a variable "e" and include exponents of 5 in the last equation?
Crazy stuff. This thread is proving to be very educational.
Sequences - geodave - 27-Apr-2012
You have the idea. This gets very messy when you get to about 6 unknowns (6<sup>5</sup>=7776). For "nice" sequences that you can figure out in other ways, typically the results are simple. But if you just pick random numbers -- it gets ugly quickly.
Quote:A high order equation? Eh? Is it possible to derive the equation, or do we just "know" that it exists.
Also, is there a theoretical limit on the number of valid answers to any given sequence?
Technically, it doesn't "exist" -- it's an approximation. It only gives one of the possible answers.
And no, I don't believe there is any theoretical limit. What's that number for the size of all natural numbers again? Aleph?