wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Growing Number Sequence
(Message started by: James Fingas on Jan 27th, 2003, 2:00pm)

Title: Growing Number Sequence
Post by James Fingas on Jan 27th, 2003, 2:00pm
Can you predict the next value in this number sequence?

1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, ...

Title: Re: Growing Number Sequence
Post by Garzahd on Jan 27th, 2003, 3:19pm
Hmm. I have an answer that works only if the last two numbers are decreased by one... in which case, my sequence goes 76, 88, 103, 121, 139, 161, 188....
Of course, if my sequence is wrong, it could be used as a counter-puzzle :-)

Title: Re: Growing Number Sequence
Post by James Fingas on Jan 28th, 2003, 9:50am
Garzahd,

Very interesting! Your sequence diverges somewhat from mine for the subsequent numbers you list. Now I'm glad I gave so many terms...
[hide] 76, 89, 104, 122, 142, 165, 192 [/hide]

Title: Re: Growing Number Sequence
Post by ndkrempel on Jul 24th, 2003, 4:07pm
... 122, 142, 165, 192, 222, 256, ...

Title: Re: Growing Number Sequence
Post by James Fingas on Jul 28th, 2003, 1:44pm
Seems right ... now if only I could remember what the sequence was ;)

Okay, I remember how I created it now. Just to double-check, what number in the sequence is closest to 100 000?

Title: Re: Growing Number Sequence
Post by SWF on Aug 4th, 2003, 9:02pm
I am not very fond of "what is the next number" problems because an answer can always be claimed to be wrong by adding another number to the list that messes up a proposed solution.

To find the n'th term on the list, plus into the formula:
[hide]0.09*5.57sqrt(n)/n0.427 and round to the nearest integer.

That is pretty simple considering it fits all 30 values given by James and ndkrempel so far.

I have a feeling James Fingas is thinking of a certain 'standard' function (Q), but I don't think that is as simple to compute as the formula above. I guess the best answer depends on opinion, but I prefer simplicity.[/hide]

Title: Re: Growing Number Sequence
Post by wowbagger on Aug 5th, 2003, 3:52am

on 08/04/03 at 21:02:41, SWF wrote:
I guess the best answer depends on opinion, but I prefer simplicity.

Frankly, I don't think your answer is simple. Of course, I don't know James's way to generate this sequence, so your way could well be "simpler".

As an example, consider the Fibonacci sequence:
The explicit formula is definitely more complicated than the recursive description. Let me clarify in advance that I don't talk about simplicity of calculation. It's the generating rule that is simple.

Title: Re: Growing Number Sequence
Post by James Fingas on Aug 5th, 2003, 11:49am
That's an interesting formula, but my sequence is more of a "generation" sequence. The reason it fits a formula like that so well is that it grows rather smoothly. The sequence is actual the first n digits of an O(n2)-length symmetrical sequence (i.e. that reads the same forwards as backwards). At first, I thought it might grow exponentially (sort of like the rows of Pascal's triangle), but it seems to grow more slowly than that.

When I posted the puzzle, I was hoping someone would come up with a simple way to generate the sequence, to shed light onto its growth characteristics, but apparently not.

I am telling you this because I feel this question sucks. The sequence is evidently not unique enough to find just out of the blue. If you would want to discuss the sequence in more depth, I could tell you how to generate it, and then we could talk about its growth rate and behaviour...

Title: Re: Growing Number Sequence
Post by Icarus on Sep 15th, 2003, 4:11pm

on 08/05/03 at 11:49:27, James Fingas wrote:
If you would want to discuss the sequence in more depth, I could tell you how to generate it, and then we could talk about its growth rate and behaviour...


Since it doesn't look like this is going anywhere by other means, that would be a good idea. Who knows - maybe someone will be able see something you haven't.

Title: Re: Growing Number Sequence
Post by SWF on Sep 15th, 2003, 8:42pm
The standard function Q(n) I mentioned above is called 'Partition Function Q' on Mathworld. There are a number of ways to compute it, and I would be interested if James is using a method that is more easily evaluated than the formula I proposed above (or if Q(n) is not what James has in mind). However, my formula only fits the numbers in the original question, and does not equal Q(n) for all larger n.

Title: Re: Growing Number Sequence
Post by James Fingas on Sep 16th, 2003, 7:55am
Okay, I'll tell you how to generate it. Define a sequence of numbers Si,j, so that S0,j = 1,0,0,0,... for j = 0,1,2,3,... and is zero for all j<0.

Then let Si,j = S0,j-i + S1,j-i + S2,j-i + ... + Si-1,j-i.

Properties of this sequence:
1) For all j>0, Si,i(i+1)/2+j = 0
2) For all j<0, Si,i-j = 0
3) For all i, Si,j = Si,i(i+3)/2-j
4) For all k>i, if k>j, Sk,j+k = Si,j+i.

So when we choose an i we get a palindrome sequence, with leading and trailing zeros. This sequence's length is the ith triangular number, and its first non-zero digit is in the ith place. To get the next palindrome sequence, we add shifted versions of all the previous palindrome sequences. As we create new sequences, however, the first i numbers don't change from the previous sequence. These first i numbers can be considered to be a sequence in their own right (and that is the sequence I've given above).

No idea if this has any relation to Q.

Title: Re: Growing Number Sequence
Post by Icarus on Sep 16th, 2003, 6:56pm
Interesting. It should be possible to come up with an expression. First thing to do would be to develop if possible, a version of the defining equation which has a fixed index dependence. It is usually possible with these sorts of equations because most of the sum needed for each element is also in nearby elements.

I'll have to look at it a bit.

1 1 1 2 2 3 4 5 6 8 10 12 15 18 22 27 32 38 46 54 64 76 89 104 122 142 165 192 222 256 296 340 390 448 512 585 668 760 864 982 1113 1260 1426 1610 1816 2048 2304

A few more terms.

Title: Re: Growing Number Sequence
Post by Icarus on Sep 16th, 2003, 7:55pm
Okay the necessary formula is (switching from i, j to m, n since i,j in the subscript is very hard to read)

Smn = S(m-1)(n-1) + S(m-1)(n-m)   (m>1)

Now it becomes a Calculus of Finite Differences version of a boundary value problem for a PDE in two variables. In particular, our equation is linear, so we can sum convenient solutions to arrive at the one we want. Unfortunately, that (n-m) subscript plays havoc with finding convenient solutions - separation of variables fails!

Still working...

Title: Re: Growing Number Sequence
Post by James Fingas on Sep 17th, 2003, 5:59am
That expression of the sum makes it obvious why they are all palindromes ...

What I found interesting was to graph these sequences with a linear scale for n and a logarithmic scale for Sm,n. They all have similar graphs, but the graphs don't really hint at the growth of the infinite sequence (or not that I could figure out, anyways).

Title: Re: Growing Number Sequence
Post by Icarus on Sep 18th, 2003, 7:52pm
We can define the sequence actually requested by Tk = Sk+n,2k+n (for any n > 0).

Letting M = [lfloor]k/2[rfloor], it follows that

Tk = [sum]i=0M Sik + [sum]i=M+1k Tk-i

I still haven't decided how to handle that first half - but if it can also be expressed in terms of T rather than S, then we'll have a much simpler situation. Perhaps a comparison of Tk and Tk-1 will be able to remove the first sum. But I don't have time to look at it anymore for a couple days.

Title: Re: Growing Number Sequence
Post by SWF on Sep 28th, 2003, 11:59am
I am unable to clearly follow James Fingas' description of how he generated his series, but based on Icarus' formula for SMN, something like the following should be able to show this sequence is the same as partition function Q.

Define polynomials PM(x)=[sum]SMN*xN where sum is on N=0 to [infty]. If PM(x)=(1+xM)*PM-1(x) and P0(x)=1, then the SMN approach the Q sequence as M increases.

It looks like James' sequence of SMN corresponds to polynomials with a form something like PM(x)=x*(1+xM)*PM-1(x). If so, that means it is the same as Q, except the extra factor of x shifts the sequence on each step. James' method of generating the SMN would then be equivalent to multiplying those polynomials.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board