[seqfan] Re: Interesting sequence

[David Wilson]

Yes, your observation of the connection of f to A000960 is correct.  Here is a proof.

Let [x] = floor(x).

Let a(0) be the sequence of nonnegative integers, indexed starting at 0.
For k > 1 let a(k) be the sequence gotten by sieving out every nth element of a(k-1).
We then have:

a(0) = (0,   1,   2,   3,   4,   5,   6,   7,   8,   9, ...)
a(1) = (0,   2,   4,   6,   8,  10,  12,  14,  16,  18, ...)
a(2) = (0,   2,   6,   8,  12,  14,  18,  20,  24,  26, ...)
a(3) = (0,   2,   6,  12,  14,  18,  24,  26,  30,  36, ...)
a(4) = (0,   2,   6,  12,  18,  24,  26,  30,  38,  42, ...)
a(5) = (0,   2,   6,  12,  18,  26,  30,  38,  42,  48, ...)
a(6) = (0,   2,   6,  12,  18,  26,  38,  42,  48,  60, ...)
a(7) = (0,   2,   6,  12,  18,  26,  38,  48,  60,  62, ...)
a(8) = (0,   2,   6,  12,  18,  26,  38,  48,  62,  66, ...)
a(9) = (0,   2,   6,  12,  18,  26,  38,  48,  62,  78, ...)
...

which is described by the following recursive definition:

a(0, n) = n for n >= 0.
a(k, n) = a(k - 1, [n *(k + 1)/k]) for k > 0 and n >= 0.

If we expand, say, a(5, 5), we get

a(5, 5)
= a(4, [5 *6/5])
= a(3, [[5 *6/5] * 5/4])
= a(2, [[[5 *6/5] * 5/4] * 4/3])
= a(1, [[[[5 *6/5] * 5/4] * 4/3] * 3/2])
= a(0, [[[[[5 *6/5] * 5/4] * 4/3] * 3/2] * 2/1])
= [[[[[5 *6/5] * 5/4] * 4/3] * 3/2] * 2/1]
= 26.

In other words, a(5, 5) = 26 is exactly the f(5) I described in my original post.
In general, f(n) = a(n, n), which I am sure can be proved by a straightforward if tedious inductive argument.

Finally, since the sieve used to define a is the same sieve used to define A000960, another tedious induction gives:

a(n, n)  = A000960(n + 1) - 1, from which f(n) = A000960(n + 1) - 1.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Chris
> Thompson
> Sent: Tuesday, November 22, 2016 9:07 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Re: Interesting sequence
> 
> On Nov 22 2016, David Wilson wrote:
> 
> >Starting with integer n,  multiply by ((n+1)/n), take the floor,
> >multiply by (n/(n-1), take the floor, all the way down to 2/1, call the result
> f(n).
> >
> >For example, starting with n = 5
> >
> >floor(5*(6/5)) = 6,
> >floor(6*(5/4)) = 7,
> >floor(7*(4/3)) = 9,
> >floor(9*(3/2)) = 13,
> >floor(14*(2/1)) = 26.
> >
> >so f(5) = 26.
> >
> >Starting at n = 1, we have
> >
> >f = (2, 6,  12, 18, 26, 38, 48, 62, 78, 90, ...)
> >
> >It's trivial that all elements are even, given the final multiplier 2/1.
> >
> >It looks to me as if f(n) ~ pi*n^2/4, but I couldn't begin to prove this.
> 
> This reminds me a lot of A000960, discussed briefly here a year ago [
> http://list.seqfan.eu/pipermail/seqfan/2015-November/015706.html ].
> In fact it seems that ThisSeries(n) = A000960(n+1)-1. Can anyone provide a
> proof?
> 
> --
> Chris Thompson
> Email: cet1 at cam.ac.uk
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/