[seqfan] Re: Two interesting integer sequences that could use some help.

[Max Alekseyev]

On Mon, Feb 11, 2013 at 8:57 AM, Neil Sloane <njasloane at gmail.com> wrote:
> Here are two interesting integer sequences in the OEIS that could use some
> help.
>
> 1. Sequence A114183, contributed by Franklin Adams-Watters:
> a(1)=1; thereafter a(n) = floor(sqrt(a(n-1))) if that is not already
> in the sequence, otherwise a(n) = 2a(n-1):
> 1, 2, 4, 8, 16, 32, 5, 10, 3, 6, 12, 24, 48, 96, 9, 18, 36, 72, 144, 288,
> 576,...
> This consists of a sequence of "doubling runs", whose starting points and
> lengths
> are given in A221715 and A221716.
>
> A114183 has a comment:
> "One can prove by induction that n must appear in the sequence after [n/2],
> showing that the sequence is one-to-one; and that frac(log_2(log_2(a(n)))
> is dense in [0,1), from which it follows that a(n) is onto".
>
> I am having trouble filling in all the details of this argument - can
> anyone help?

I  do not understand this argument either (why not ask its author to
clarify?) but here is mine proof that every positive integer appears
in A114183.

First, let us prove that A114183 is unbounded. If it is bounded, let
us consider the maximum integer m that appears in A114183 infinitely
many times. It is clear that starting with the second appearance, the
next term after m must be 2m (as floor(sqrt(m)) is allowed to follow m
at most once). But then 2m appears in A114183 infinitely many times,
which contradicts to maximality of m. This contradiction proves that
A114183 is unbounded.

Second, let us prove that every positive integer appears in A114183.
Assume that some positive integer m does not appear in A114183. Then
neither of m^2, m^2+1, ..., (m+1)^2 - 1 appear in A114183 (as m would
follow each of these numbers). By similar argument, neither of m^4,
m^4+1, ..., (m+1)^4 - 1 appear in A114183. And in general, neither of
m^(2^k), m^(2^k)+1, ..., (m+1)^(2^k) - 1 appear in A114183 for every
k=0,1,2,...
It is clear that (m+1)^(2^k) / m^(2^k) = (1 + 1/m)^(2^k) tends to
infinity as k grows. Therefore, for some k, this ratio is grater than
2. But then all terms of A114183 must be bounded by m^(2^k) as they
cannot "jump over" the interval integers [m^(2^k), (m+1)^(2^k) - 1]
missing in A114183. The contradiction proves that every positive
integer appears in A114183.

Regards,
Max