wu :: forums
wu :: forums - Growing Number Sequence

Welcome, Guest. Please Login or Register.
Jun 24th, 2018, 4:12am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: ThudnBlunder, Icarus, towr, william wu, Eigenray, Grimbal, SMQ)
   Growing Number Sequence
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Growing Number Sequence  (Read 4379 times)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Growing Number Sequence  
« on: Jan 27th, 2003, 2:00pm »
Quote Quote Modify 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
**





    mlahut


Gender: male
Posts: 130
Re: Growing Number Sequence  
« Reply #1 on: Jan 27th, 2003, 3:19pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Growing Number Sequence  
« Reply #2 on: Jan 28th, 2003, 9:50am »
Quote Quote Modify 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

Email

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

... 122, 142, 165, 192, 222, 256, ...
IP Logged
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: Growing Number Sequence  
« Reply #4 on: Jul 28th, 2003, 1:44pm »
Quote Quote Modify Modify

Seems right ... now if only I could remember what the sequence was Wink
 
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 Quote Modify 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
*****





242002184 242002184    


Gender: male
Posts: 727
Re: Growing Number Sequence  
« Reply #6 on: Aug 5th, 2003, 3:52am »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Growing Number Sequence  
« Reply #7 on: Aug 5th, 2003, 11:49am »
Quote Quote Modify 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: male
Posts: 4863
Re: Growing Number Sequence  
« Reply #8 on: Sep 15th, 2003, 4:11pm »
Quote Quote Modify 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 Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Growing Number Sequence  
« Reply #10 on: Sep 16th, 2003, 7:55am »
Quote Quote Modify 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: male
Posts: 4863
Re: Growing Number Sequence  
« Reply #11 on: Sep 16th, 2003, 6:56pm »
Quote Quote Modify 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: male
Posts: 4863
Re: Growing Number Sequence  
« Reply #12 on: Sep 16th, 2003, 7:55pm »
Quote Quote Modify 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
*****





   
Email

Gender: male
Posts: 949
Re: Growing Number Sequence  
« Reply #13 on: Sep 17th, 2003, 5:59am »
Quote Quote Modify 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: male
Posts: 4863
Re: Growing Number Sequence  
« Reply #14 on: Sep 18th, 2003, 7:52pm »
Quote Quote Modify 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 Quote Modify 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
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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