Find the pattern: 12, 44, 130, 342, 840

[beamthegreat]

Hi I need help finding the pattern of the following sequence:

12, 44, 130, 342, 840, 1976, 4518, 10130, 22396, 48996

Any help will be appreciated. Thanks.

 

[Raghav Gupta]

Hi I need help finding the pattern of the following sequence:

12, 44, 130, 342, 840, 1976, 4518, 10130, 22396, 48996

Have you rechecked the terms carefully and if possible can you give a reference from where you have taken the problem?

 

[Suraj M]

Are you sure that there is a pattern? I mean solved question by someone else,is it??

 

[beamthegreat]

Yes I am very certain these sequences are correct. Here are the first 20 terms:

2
12
44
130
342
840
1976
4518
10130
22396
48996
106314
229166
491280
1048304
2227918
4718250
9961092
20971100

Here's a graph of these points plotted in excel:

 

[beamthegreat]

Here's another graph plotted on a logarithmic scale (base 10)

 

[Raghav Gupta]

Yes I am very certain these sequences are correct. Here are the first 20 terms:

2
12
44
130
342
840
1976
4518
10130
22396
48996
106314
229166
491280
1048304
2227918
4718250
9961092
20971100

Here's a graph of these points plotted in excel:

You have not given 2 in the question
And from where you have taken the question?
It might be that you have made up your own numbers and then asking for a pattern?

 

[beamthegreat]

You have not given 2 in the question
And from where you have taken the question?
It might be that you have made up your own numbers and then asking for a pattern?

Look, if you're not going to help me then why do you even bother posting? The pattern clearly follows an exponential trend and I need to find a method to convert a set of numbers I have into a polynomial function.

 

[beamthegreat]

Are you sure that there is a pattern? I mean solved question by someone else,is it??

Could you clarify what you mean? If its already solved by someone else then why would I post this question?

Also, if the pattern can't be expressed by any function, can anyone tell me the best fit curve to extrapolate the data? I tried using one in excel but its really bad.

 

[micromass]

beamthegreat, you absolutely need to tell us where you got these numbers. If you don't, then we can't help you.

 

[beamthegreat]

Its the population growth from one of a mod in Civilization V. If your not familiar with it, its basically a turn-based computer game. I recorded the values and want to find a function for it.

 

[Raghav Gupta]

As I suspected it could have been a random data from game and I bothered posting because I like finding pattern in sequences but it can become hard when you take any kind of numbers.
In this case software would be helpful, giving you approximate answers as it is difficult to do by hand.
See this

 

[micromass]

As I suspected it could have been a random data from game and I bothered posting because I like finding pattern in sequences but it can become hard when you take any kind of numbers.
In this case software would be helpful, giving you approximate answers as it is difficult to do by hand.
See this

Yeah, but that wolframalpha program calculate a polynomial fit. But it's clear from the data that you want exponentials in there. Basically, it could be a formula of the form
(\alpha x^2 + \beta x + \gamma)e^{\delta x +\varphi} + (\mu x^2 + \nu x + \sigma)
or something very different or more complicated. If you know the exact form of the function, it's not so difficult to find the exact fit. But you don't know which functions are involved.

 

[Pythagorean]

Using cftool in matlab, I get:

f(x) = a*exp(b*x)
a = 14.61
b = 0.7462

 

[Raghav Gupta]

Using cftool in matlab, I get:

f(x) = a*exp(b*x)
a = 14.61
b = 0.7462

I may be misunderstanding this but when we are giving x=1 we are getting f(x) = 30 (approximately) which is not in sequence. So is it a wrong function for the pattern?

 

[Svein]

OK. I have found it. If we count the numbers from 1 upwards, the n'th number is given by (n+1)(2^{n+1}-2-n)

 

[zoki85]

So is it a wrong function for the pattern?

Not necessarily. There's possibility no analytical function that coincides with all terms exactly but just functions that describe general trend of growth.

 

[Raghav Gupta]

OK. I have found it. If we count the numbers from 1 upwards, the n'th number is given by (n+1)(2^{n+1}-2-n)

Wow, that looks perfectly fine.
It was seeming like a complicated function for the pattern but you showed that it is actually not.
Now a curiosity has grown in me that how you came up with it when software like Wolfram was not able to compute a formula for the sequence. Can you tell? The copyrights are to you if you have not used a software.

 

[zoki85]

I hope we can prove by induction that it is applicable for whole of sequence.

What are you talking about?

 

[Raghav Gupta]

What are you talking about?

Sorry, I was in other state of mind.
I will edit it.

 

[Svein]

Now a curiosity has grown in me that how you came up with it when software like Wolfram was not able to compute a formula for the sequence. Can you tell?

Well, I started out by trying to factorize the numbers. That didn't go well, but I observed that:

• All numbers were even
• All numbers could be factorized

That led me to try dividing all numbers by n - which did not work. But dividing by n+1 gave whole numbers as a result. Calculating the differences between the resulting numbers gave me 1, 3, 7, ... i.e. 2ⁿ-1. From there it was just a question of cleaning up the expression.

 

[Suraj M]

How would you know what to divide by??

 

[Vanadium 50]

Equation 17 is right. This is twice the number of minimal covers of an (n+1)-set by a collection of n subsets. A cover of a set S is a collection of nonempty subsets of S whose union is S. A cover of S is called minimal if none of its proper subsets covers S.

The next one is 44039730.

 

[Raghav Gupta]

Well, I started out by trying to factorize the numbers. That didn't go well, but I observed that:

• All numbers were even
• All numbers could be factorized

That led me to try dividing all numbers by n - which did not work. But dividing by n+1 gave whole numbers as a result. Calculating the differences between the resulting numbers gave me 1, 3, 7, ... i.e. 2ⁿ-1. From there it was just a question of cleaning up the expression.

Brilliant guy.
Got it.

 

[Suraj M]

OP, where did you get this question?
In general where can you get such sequences?Anybody?

 

[Raghav Gupta]

OP, where did you get this question?
In general where can you get such sequences?Anybody?

Refer post 12.

 

[zoki85]

Equation 17 is right. This is twice the number of minimal covers of an (n+1)-set by a collection of n subsets. A cover of a set S is a collection of nonempty subsets of S whose union is S. A cover of S is called minimal if none of its proper subsets covers S.

The next one is 44039730.

https://oeis.org/A003469
Encyclopedia of Integer sequences is a great help with such things

In general where can you get such sequences?Anybody?

You can also use imagination to create new integer sequences.
Here is the sequence I have just made up:

1, 6, 17, 42, 97, 214, 457, 954, 1961,...

Formula is pretty simple. Try to discover it

 

[Raghav Gupta]

1, 6, 17, 42, 97, 214, 457, 954, 1961,...

Formula is pretty simple. Try to discover it

I tried but was not able to find a formula for such a simple thing . How do we tackle such kind of problems? What initial steps should we take?

 

[Svein]

Here is the sequence I have just made up:

1, 6, 17, 42, 97, 214, 457, 954, 1961,...

I almost made it last night through difference analysis. I failed to create a closed form out of it, though (I am no good late at night). So, if anybody want to clean it up:
Assuming that the first element is number one, a formula for element n is: 1+\sum_{k=2}^{n}[2(2^{k}-k)+1]

 

[Mentallic]

I almost made it last night through difference analysis. I failed to create a closed form out of it, though (I am no good late at night). So, if anybody want to clean it up:
Assuming that the first element is number one, a formula for element n is: 1+\sum_{k=2}^{n}[2(2^{k}-k)+1]

Good work! The closed form is then

2^{n+2}-n^2-6

Could I ask, how did you get that?

 

[Svein]

Could I ask, how did you get that?

1. I copy the numbers into Excel.
2. I let Excel calculate the differences (a₂-a₁, a₃-a₂ etc.)
3. I let Excel calculate the differences of the differences (d₂-d₁, d₃-d₂ etc.)
4. Repeat until I see a pattern
5. Rebuild from the pattern upwards.