Author 
Topic: Growing Number Sequence (Read 5044 times) 

James Fingas
Uberpuzzler
Gender:
Posts: 949


Growing Number Sequence
« on: Jan 27^{th}, 2003, 2:00pm » 
Quote Modify

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, ...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Garzahd
Junior Member
Gender:
Posts: 130


Re: Growing Number Sequence
« Reply #1 on: Jan 27^{th}, 2003, 3:19pm » 
Quote Modify

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 counterpuzzle :)


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Growing Number Sequence
« Reply #2 on: Jan 28^{th}, 2003, 9:50am » 
Quote Modify

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


IP Logged 
Doc, I'm addicted to advice! What should I do?



ndkrempel
Guest


Re: Growing Number Sequence
« Reply #3 on: Jul 24^{th}, 2003, 4:07pm » 
Quote Modify
Remove

... 122, 142, 165, 192, 222, 256, ...


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Growing Number Sequence
« Reply #4 on: Jul 28^{th}, 2003, 1:44pm » 
Quote Modify

Seems right ... now if only I could remember what the sequence was Okay, I remember how I created it now. Just to doublecheck, what number in the sequence is closest to 100 000?


IP Logged 
Doc, I'm addicted to advice! What should I do?



SWF
Uberpuzzler
Posts: 879


Re: Growing Number Sequence
« Reply #5 on: Aug 4^{th}, 2003, 9:02pm » 
Quote Modify

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: 0.09*5.57^{sqrt(n)}/n^{0.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.


IP Logged 



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Growing Number Sequence
« Reply #6 on: Aug 5^{th}, 2003, 3:52am » 
Quote Modify

on Aug 4^{th}, 2003, 9:02pm, 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.

« Last Edit: Aug 5^{th}, 2003, 3:54am by wowbagger » 
IP Logged 
"You're a jerk, <your surname>!"



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Growing Number Sequence
« Reply #7 on: Aug 5^{th}, 2003, 11:49am » 
Quote Modify

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(n^{2})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...


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Growing Number Sequence
« Reply #8 on: Sep 15^{th}, 2003, 4:11pm » 
Quote Modify

on Aug 5^{th}, 2003, 11:49am, 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.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



SWF
Uberpuzzler
Posts: 879


Re: Growing Number Sequence
« Reply #9 on: Sep 15^{th}, 2003, 8:42pm » 
Quote Modify

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.


IP Logged 



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Growing Number Sequence
« Reply #10 on: Sep 16^{th}, 2003, 7:55am » 
Quote Modify

Okay, I'll tell you how to generate it. Define a sequence of numbers S_{i,j}, so that S_{0,j} = 1,0,0,0,... for j = 0,1,2,3,... and is zero for all j<0. Then let S_{i,j} = S_{0,ji} + S_{1,ji} + S_{2,ji} + ... + S_{i1,ji}. Properties of this sequence: 1) For all j>0, S_{i,i(i+1)/2+j} = 0 2) For all j<0, S_{i,ij} = 0 3) For all i, S_{i,j} = S_{i,i(i+3)/2j} 4) For all k>i, if k>j, S_{k,j+k} = S_{i,j+i}. So when we choose an i we get a palindrome sequence, with leading and trailing zeros. This sequence's length is the i^{th} triangular number, and its first nonzero digit is in the i^{th} 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.


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Growing Number Sequence
« Reply #11 on: Sep 16^{th}, 2003, 6:56pm » 
Quote Modify

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.

« Last Edit: Sep 18^{th}, 2003, 6:06pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Growing Number Sequence
« Reply #12 on: Sep 16^{th}, 2003, 7:55pm » 
Quote Modify

Okay the necessary formula is (switching from i, j to m, n since i,j in the subscript is very hard to read) S_{mn} = S_{(m1)(n1)} + S_{(m1)(nm)} (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 (nm) subscript plays havoc with finding convenient solutions  separation of variables fails! Still working...

« Last Edit: Sep 18^{th}, 2003, 6:16pm by Icarus » 
IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Growing Number Sequence
« Reply #13 on: Sep 17^{th}, 2003, 5:59am » 
Quote Modify

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 S_{m,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).


IP Logged 
Doc, I'm addicted to advice! What should I do?



Icarus
wu::riddles Moderator Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863


Re: Growing Number Sequence
« Reply #14 on: Sep 18^{th}, 2003, 7:52pm » 
Quote Modify

We can define the sequence actually requested by T_{k} = S_{k+n,2k+n} (for any n > 0). Letting M = [lfloor]k/2[rfloor], it follows that T_{k} = [sum]_{i=0}^{M} S_{ik} + [sum]_{i=M+1}^{k} T_{ki} 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 T_{k} and T_{k1} will be able to remove the first sum. But I don't have time to look at it anymore for a couple days.


IP Logged 
"Pi goes on and on and on ... And e is just as cursed. I wonder: Which is larger When their digits are reversed? "  Anonymous



SWF
Uberpuzzler
Posts: 879


Re: Growing Number Sequence
« Reply #15 on: Sep 28^{th}, 2003, 11:59am » 
Quote Modify

I am unable to clearly follow James Fingas' description of how he generated his series, but based on Icarus' formula for S_{MN}, something like the following should be able to show this sequence is the same as partition function Q. Define polynomials P_{M}(x)=[sum]S_{MN}*x^{N} where sum is on N=0 to [infty]. If P_{M}(x)=(1+x^{M})*P_{M1}(x) and P_{0}(x)=1, then the S_{MN} approach the Q sequence as M increases. It looks like James' sequence of S_{MN} corresponds to polynomials with a form something like P_{M}(x)=x*(1+x^{M})*P_{M1}(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 S_{MN} would then be equivalent to multiplying those polynomials.


IP Logged 



