Jump to content
BrainDen.com - Brain Teasers
  • 0


Guest
 Share

Question

If we have a sequence of numbers that follow a formula related to n (the position in the formula) eg for the sequence 1, 4, 9, 16, 25, 36... the numbers follow the formula n2. If we say the highest power of n in the formula is x (eg for n3+n+1 x=3) then how many numbers do we need in the sequence to be sure of being able to derive the formula?

Bare minimum terms to be able to do it, no extra ones to ensure the proof.

Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 0

x+1?

reasoning:

if x = 0, you'd only need 1 term to determine the constant number (e.g. 3,3,3,3,... f(n) = a*n^0 a=3)

if x=1 you'd only need 2 terms (e.g. 1,3,5,7,9 f(n) = a*n^1+b*n^0 use two equations)

x=2, use three equations to solve for unknown coefficients

this assumes that f(n) will always be a polynomial and not include, i dunno, sines or something heh.

Link to comment
Share on other sites

  • 0
x+1?

reasoning:

if x = 0, you'd only need 1 term to determine the constant number (e.g. 3,3,3,3,... f(n) = a*n^0 a=3)

if x=1 you'd only need 2 terms (e.g. 1,3,5,7,9 f(n) = a*n^1+b*n^0 use two equations)

x=2, use three equations to solve for unknown coefficients

this assumes that f(n) will always be a polynomial and not include, i dunno, sines or something heh.

That's not the answer I was thinking of (not saying it's necessarily wrong).

To clarify what I meant was how many terms in the series do you need to be able to work it out without knowing what x is so you wouldn't be able to set up simultaneous equations.

On a side note I only put relatively easy because I didn't want people mocking me if everyone got it right away

Link to comment
Share on other sites

  • 0

...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an2+bn+c (a!=zero)

a sequence of 3 zeros with a formula an3+bn2+cn+d (a!=zero)

a sequence of x zeros with a formula anx+bnx-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

Link to comment
Share on other sites

  • 0
...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an2+bn+c (a!=zero)

a sequence of 3 zeros with a formula an3+bn2+cn+d (a!=zero)

a sequence of x zeros with a formula anx+bnx-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

non zero powers of n

Link to comment
Share on other sites

  • 0
...that if you don't know what x is, there is no length of sequence that will give you the answer for certain. Unless I'm mistaken, you can create...

a sequence of 2 zeros with a formula an2+bn+c (a!=zero)

a sequence of 3 zeros with a formula an3+bn2+cn+d (a!=zero)

a sequence of x zeros with a formula anx+bnx-1....(a!=zero)

(I haven't verified that but I think it works that way)

...so generally if you have a sequence with i items in it, you cannot know what x is, because you could always generate a sequence with i (or more) zeros with a higher power of x and add it to the first sequence without changing the first i members. So you never know that x is not a higher value than you think.

i agree, if what octopuppy is trying to solve is indeed what you're going for,

it will be impossible to determine the equation without knowing x.

lets say given the sequence 0, 1. this works with f(n) = n, n^2, n^3, etc..., therefore x is unknown

so lets up it to three, 0, 1, 4. now we've eliminated f(n) = n, but that still means that f(n) = an^2+b*n+c is viable, as is a*n^3+b*n^2+c*n+d, you just have to solve for the variables (which i admit will be rather annoying with x much greater than 5.

so by increasing the number of terms, we only eliminate lower functions, we never hit a ceiling of higher power functions.

Edited by hombreduffo
Link to comment
Share on other sites

  • 0
i agree, if what octopuppy is trying to solve is indeed what you're going for,

it will be impossible to determine the equation without knowing x.

lets say given the sequence 0, 1. this works with f(n) = n, n^2, n^3, etc..., therefore x is unknown

so lets up it to three, 0, 1, 4. now we've eliminated f(n) = n, but that still means that f(n) = an^2+b*n+c is viable, as is a*n^3+b*n^2+c*n+d, you just have to solve for the variables (which i admit will be rather annoying with x much greater than 5.

so by increasing the number of terms, we only eliminate lower functions, we never hit a ceiling of higher power functions.

apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (anx) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n3

series - n3

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n2

series - (n3 + 2n2)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n3 + 2n2 + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart ;)

Link to comment
Share on other sites

  • 0
apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (anx) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n3

series - n3

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n2

series - (n3 + 2n2)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n3 + 2n2 + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart ;)

Taking your example of the sequence:

11, 24, 53, 104, 183

How do you know that wasn't produced by the polynomial:

n5-15n4+86n3-223n2+274n-112 for example? (or infinitely many other polynomials of even higher orders which I can't be bothered to work out)

Link to comment
Share on other sites

  • 0

If you take the difference between the polynomial I gave you and the one you had you get n5-15n4+85n3-225n2+274n-120, a tricky little polynomial which evaluates to:

0,0,0,0,0,120,720,2520... for n from 1 to 8. You can come up with something like that which gives you as many zeroes as you like, which is why no finite sequence has a unique polynomial.

I think my notation was a bit confusing in the earlier post. By "a!=zero" I meant "a != zero" (a<>0) not "a! = zero". Maybe not all that clear!

Link to comment
Share on other sites

  • 0
apologies for posting the solution to this so early but it's the first brain teaser I've ever posted and I don't want it to get too close to farce

I originally intended the answer to be x+2, however given the OP x+1 might be better (my mistake)

My method of doing this based on looking at the diference (it's the first step along the way to calculus) between the terms for example in sequence 1,2,3,4,5,6 the difference between the terms is 1 obviously.

If we the take the series 1, 4, 9, 16, 25, 36 then the differences form another series in this case 5, 7, 9, 11 then the difference in this series (the second difference) is 2.

for 1, 8, 27, 64, 125, 216 differences are 7, 19, 37. 61, 91, 2nd differences 12, 18, 24, 30, 3rd difference is 6

you can keep going but I won't, suffice to say that in a sequence where the highest power of n is x so (anx) the xth difference will be ax!

So by comparing the differences until we find one which is a constant we can calculate the highest power of n and it's coefficient. you then take that away from each number in the sequence and repeat for each lower power of n. The question then is how many terms do we need to have to calculate the xth difference, the reason I went with x+2 is that x+1 will only give one value for the xth difference so there's no way to know if it's constant or not, x+2 gives 2 values so we can be sure it is the highest power. However just taking the 1 value x+1 gives and using it as the value ax! does work.

Example

11, 24, 53, 104, 183

3rd difference is 6, 6 divided by 3! is 1 so highest term is n3

series - n3

10, 16, 26, 40, 58

2nd difference is 4, 4 divided by 2! is 2 so 2nd term is 2n2

series - (n3 + 2n2)

8, 8, 8, 8, 8

so last term is 8

makes the polynomial n3 + 2n2 + 8

in conclusion it's x+1 terms to be able to work it out, x+2 to be able to do it and know you aren't going to be wasting your time doing the subtractions.

feel free to mercilessly rip it apart ;)

You can find an exact fit to any set of n x,y-ordered points with a polynomial of order n+1 or greater. So, if you know its order is 5, you can solve it with any 6 different points, but finding an exact fit through 6 points does not guarantee the series is a 5th order polynomial.

One of the many reasons why high-order polynomial curve fits are dangerous, and why I avoid them like the plague.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...