Author |
Topic: Growing Number Sequence (Read 5389 times) |
|
James Fingas
Uberpuzzler
    


Gender: 
Posts: 949
|
 |
Growing Number Sequence
« on: Jan 27th, 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 27th, 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 counter-puzzle :-)
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
    


Gender: 
Posts: 949
|
 |
Re: Growing Number Sequence
« Reply #2 on: Jan 28th, 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 24th, 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 28th, 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 double-check, 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 4th, 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.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.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
    

Gender: 
Posts: 727
|
 |
Re: Growing Number Sequence
« Reply #6 on: Aug 5th, 2003, 3:52am » |
Quote Modify
|
on Aug 4th, 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 5th, 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 5th, 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(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...
|
|
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 15th, 2003, 4:11pm » |
Quote Modify
|
on Aug 5th, 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 15th, 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 16th, 2003, 7:55am » |
Quote Modify
|
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.
|
|
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 16th, 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 18th, 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 16th, 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) 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...
|
« Last Edit: Sep 18th, 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 17th, 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 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).
|
|
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 18th, 2003, 7:52pm » |
Quote Modify
|
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.
|
|
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 28th, 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 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.
|
|
IP Logged |
|
|
|
|