[seqfan] Re: Problem connected to A000960

[Bob Selcoe]

Hi David and Seqfans,

David - don't know if you received my off-list reply; in any event,
following up on that reply, re:

> d increases at the values k =
> (1,3,7,13,19,27,39,49,63,79,91,109,133,147,181,207,223,253,289,307,349,387,.>
> which I am pretty sure is A000960, but I couldn't prove it.


Yes, I think it is A000960.  To demonstrate, let’s redefine some indices
which were previously used:

i. Let's call the above sequence a(z).
ii. Let s(1) be the starting value in a sequence S such that s(n) = smallest
multiple of n that is >= s(n-1) (n >= 2).
iii. Let m be the first index in S where s(m) <= m^2.

As I believe is well-understood (and is presented unequivocally as a formula
in A000960), we find A000960(z) by taking z^2 as a starting point in
sequence, and finding largest multiple of {z-1, z-2, z-3... 2, 1} < its
predecessor, terminating at 1 (which we will call T(1)).  For example z=8,
A000960(8)=49:

z^2 = T(8) = 64
63 = T(7) = 7g
60 = T(6) = 6f
55 = T(5) = 5e
52 = T(4) = 4d
51 = T(3) = 3c
50 = T(2) = 2b
49 = T(1) = a

A000960(z) therefore is the sequence of T(1)s. By definition, T(1) is odd
and T(2)=T+1.  Note that T(j)-T(j-1) must be < j.

If we were to work in reverse, starting with T(1) followed by T(2), T(3),
etc., we would have condition ii above with T(1)=s(1), except with the
tighter constraint that s(n) = smallest multiple of n that is > s(n-1),
rather than >= s(n-1).

David’s approach is to work in reverse following condition ii precisely
(with the lesser >= constraint).  In the case of s(1)=T(1), we get the same
result as if the tighter constraint applied.  However, this is not
necessarily the case when s(1)<T(1) for a given z; though s(j)-s(j-1) still
must be < j.

Moreover, starting with T(1) we reach s(m)=z^2; if we assume that starting
with s(1)<T(1) we could reach s(m)=z^2, we encounter the following
contradiction (using the lettering system in the above example):

s(1) = T(1)-1:  s(1) is even, so s(2) = s(1) = T(1)-1 = 2*(b-1);  s(3) =
3*(c-1);  s(4) = 4*(d-1)…  Thus, s(m)=z*(z-1).

Since s(m) necessarily is <= z*(z-1) when s(1) < T(1)-1, then the smallest
value of s(1) where s(m)=z^2 is T(1).  However, because s(j)-s(j-1) must
be < j, s(m)=z*(z-1) when A000960(z-1) <= s(1) < A000960(z) (this is David’s
d={1,1, 2,2,2,2,3,3,3,3,3,3,4,4,…}).

Therefore a(z) is the sequence of T(1)s = A000960(z).

Cheers,
Bob Selcoe


--------------------------------------------------
From: "David Wilson" <davidwwilson at comcast.net>
Sent: Friday, November 27, 2015 10:03 AM
To: "'Sequence Fanatics Discussion list'" <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: Problem connected to A000960

> Consider the family of sequences parameterized on integer k > 0:
>
> a(0) = k.
> a(n) = smallest multiple of n that is >= a(n-1) (n >= 1).
>
> For example, starting with a(0) = k = 100, we obtain the sequence
>
> a =
> (100,100,100,102,104,105,108,112,112,117,120,121,132,143,154,165,176,187,198
> ,209,...)
>
> Starting at 121, each successive element is 11 more than the previous. We
> can prove this continues forever, that is, a(n) = 11n for all n >= 11.
>
> For general starting value k, if m is the first element with a(m) <= m^2,
> then the first difference is d = a(m)/m for subsequent elements, so that
> a(n) = d*n for n >= m.
>
> I was interested in d as a function of k, so I computed d(k) for a few 
> small
> values of k >= 1:
>
> d = (1,1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,5,5,6,6,6,6,...)
>
> d increases at the values
>
> k =
> (1,3,7,13,19,27,39,49,63,79,91,109,133,147,181,207,223,253,289,307,349,387,.
> ..)
>
> which I am pretty sure is A000960, but I couldn't prove it.
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>