wu :: forums « wu :: forums - Growing Number Sequence » Welcome, Guest. Please Login or Register. Feb 8th, 2023, 1:08pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: SMQ, Icarus, Grimbal, towr, Eigenray, william wu, ThudnBlunder)    Growing Number Sequence « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Growing Number Sequence  (Read 5276 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

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

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

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

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

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

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

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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »