|
|
|
October 13th, 2006
12:51 pm - Ask LJ: Finding how a sequence of numbers grows
I have an infinite sequence of numbers which grows superlinearly and I'm attempting to figure out the formula to figure out the next one.
I can prove that it's not a function x^k where k is a natural number <=7 by taking the numbers and figuring out the difference between the numbers in the sequence, then figuring out the differences between those.
The first 10 numbers (and differences) are:
0 80 135 225 375 620 1040 1735 2900 4840 8080
1 55 90 150 245 420 695 1165 1940 3240
2 35 60 95 175 275 470 775 1300
3 25 35 80 100 195 305 525
4 10 45 20 95 110 220
5 35 -25 75 15 110
6 -55 100 -60 95
7 155 -160 155
It's worth noting the point of inflection on the 4th level. I don't have more than those 10 numbers unfortunately. It's tempting to believe that the next one on the 7th row would be -160 though.
The numbers always end in either 0 or 5, though they don't switch between 0 and 5 in any sort of regular pattern.
That's all I can think of off hand to try and crack that problem.
Incidentally, this is (in theory) part of a class of functions. Those numbers correspond to resource counts for a game (Travian incidentally) and I'm trying to predict how it grows for a program I'm writing.
|
Tentatively: The next number is 13475, I believe. One prior number would logically exist in the sequence: 50.
===|==============/ Level Head The next number is plausible and seems to follow the pattern. There's nothing in the game to suggest the prior number (but that doesn't mean that they don't compute it using a prior term). How'd you come to that solution? Re-thought it -- tentative assumption corrected. I divided by 5 to get rid of the spurious and misleading rounding effect. Here's the sequence up to about 5 billion (x=35).
80
135
225
375
620
1,040
1,735
2,900
4,840
8,080
13,500
22,540
37,645
62,865
104,985
175,320
292,790
488,955
816,555
1,363,650
2,277,295
3,803,085
6,351,150
10,606,420
17,712,720
29,580,245
49,399,010
82,496,345
137,768,895
230,074,055
384,223,675
641,653,535
1,071,561,405
1,789,507,550
2,988,477,605
4,990,757,605
value = 5 * round( 16 * 1.67 ^ [integer greater than or equal to zero], 0 )
The 1.67 is within about 0.00003 of the required value within the sequence shown; no reason to expect that it isn't exactly 1.67, but known higher values would narrow it down.
There is no previous number, as no whole number would satisfy the sequence. The previous "integer" to 16 (80/5) would need to be about 9.58. 10 is too high, 9 is too low to work.
I hope it helps.
===|==============/ Level Head Dividing it by 5 really does remove a lot of the uncertainty. Good eye!
I'd noticed that there's a difference of around 1.28 between each step, but I'd discarded that in favor of trying to find a correction factor
Somewhere in your explanation this time, I was reminded of a class in 2001 -- Computer Engineering 16 in which we figured out a solution for the Fibonacci sequence. I remembered the solution and the interesting bit of trivia, that it involved the golden mean as one of the factors, and that it didn't appear to be something which would return an integer solution. Suddenly all sorts of things came back to me: the master theorem, characteristic equations, and the book for the course which I had sense enough to keep, thankfully.
10 minutes later and it's sitting in front of me. I expect that by the end of the evening, I'll have remembered what would have allowed me to solve this in the first place.
Thanks much for the assistance 8) You're welcome!
===|==============/ Level Head And now I realize why you used 1.28 instead of 1.67 -- you were working on the other sequence I didn't see until just now. I'd thought it was a typo, and forgot about it until ready to close this window down.
Incidentally, what might you have remembered that would have allowed you to solve it?
===|==============/ Level Head What I remembered turned out to be slightly different from what I wanted, but I was still in the right place. I had been thinking of solving it as a linear homogenous recurrence with constant coefficients, but that presumed that I already had a generating function for the sequence I wanted.
The master theorem (which I also remembered) was how to find asymptotic bounds for recurrences. Interesting, but not really what I wanted either (after all, I already knew the bounds from all the work I'd scribbled out on the side trying to figure out how to solve it).
What I wanted was to find the generating function for that sequence and, on doing that, solve the relation. It *is* the magic number. 'cause three times ten is...thiiirty and three times nine is TWENTY SEVEN three times eight is TWENTY FOUR three times seven is TWENTY ONE.
three times six is eiiiighteen. three times five is fiffffteeen. three times four is twelve and threetimesthreeisnineandthreetimestwo is siiiix
and, three times one is three of couuuuuuuuuuuuuuuurse.
(this was more for me than you) I was thinking more De La Soul than Schoolhouse Rock, but it's all good 8) |
|
