?

Log in

No account? Create an account
Ask LJ: Finding how a sequence of numbers grows - CERisE's Testing for L

> Recent Entries
> Archive
> Friends
> Profile

October 13th, 2006


Previous Entry Share Next Entry
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.

(11 comments | Leave a comment)

Comments:


[User Picture]
From:level_head
Date:October 14th, 2006 05:16 am (UTC)
(Link)
Tentatively: The next number is 13475, I believe. One prior number would logically exist in the sequence: 50.

===|==============/ Level Head
[User Picture]
From:testing4l
Date:October 14th, 2006 08:34 pm (UTC)
(Link)
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?
[User Picture]
From:level_head
Date:October 14th, 2006 09:45 pm (UTC)
(Link)
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
[User Picture]
From:testing4l
Date:October 14th, 2006 10:59 pm (UTC)
(Link)
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)
[User Picture]
From:level_head
Date:October 14th, 2006 11:12 pm (UTC)
(Link)
You're welcome!

===|==============/ Level Head
[User Picture]
From:level_head
Date:October 17th, 2006 04:55 am (UTC)
(Link)
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
[User Picture]
From:testing4l
Date:October 17th, 2006 08:10 pm (UTC)
(Link)
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.
[User Picture]
From:watchbobgo
Date:October 15th, 2006 09:13 pm (UTC)
(Link)
THE ANSWER IS 3
[User Picture]
From:testing4l
Date:October 16th, 2006 06:53 pm (UTC)
(Link)
It *is* the magic number.
[User Picture]
From:watchbobgo
Date:October 16th, 2006 11:47 pm (UTC)
(Link)
'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)
[User Picture]
From:testing4l
Date:October 17th, 2006 06:26 pm (UTC)
(Link)
I was thinking more De La Soul than Schoolhouse Rock, but it's all good 8)

> Go to Top
LiveJournal.com