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

[franktaw at netscape.net]

I was out of touch for a while; moving.
I have now recovered my original argument.

We prove that n is in the sequence after
floor(n/2) by induction on the sequence,
not on n. (Strictly speaking, we need to
exclude n = 1 from this result; 0 is not in the
sequence.)

Let n be the first element of the sequence
for which floor(n/2) is not in the sequence.
n must be reached by a square root step,
otherwise n/2 immediately precedes it.
Let n = 2k or 2k+1, so 2k <= n < 2k+2.
The previous term, N, must have n as its
integer square root, so
4k^2 <= N < 4k^2+8k+4. Now, applying the
induction hypothesis twice K = floor(N/4)
must already be in the sequence, and
dividing the preceding inequality by 4 we
get k^2 <= K < k^2+2k+1; hence
floor(sqrt(K)) = k. By the definition of the
sequence, M must be followed by k unless
k is already present. Q.E.D.

>From this result it is immediate that the
sequence is one-to-one; the only way to
duplicate a value is via a doubling step,
and this lemma forbids that.

I think my proof that the sequence is onto
is similar to Max's at a deep level; superficially
it is quite different. We look at frac(lg(lg(a(n))),
where frac is the fractional part, and lg is the
base 2 logarithm. (If you prefer to think in
circles, you can use e^(lg(lg(a(n))*2*pi*i).)

Note that taking the square root of a term
does not change this value; it subtracts
1 from lg(lg(x)), which does not change the
fractional part. Taking the floor does decrease
the value, but this is by a smaller amount than
the increase from a doubling step, and there
are more doubling steps than square root steps.
So the value frac(lg(log(a(n))) increases
cyclically. The size of the increments decreases
to a limit of zero, but their total is infinite; thus the
values are dense in [0,1).

Now if k is the smallest value that has not
appeared, then as soon as we get a value
cyclically between frac(lg(lg(k)) and
frac(lg(lg(k+1))), there will be a sequence of
square root steps leading to k.

Franklin T. Adams-Watters

-----Original Message-----
From: Max Alekseyev <maxale at gmail.com>

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 
toclarify?) but here is mine proof that every positive integer appears 
in A114183.First, let us prove that A114183 is unbounded. If it is 
bounded, letus consider the maximum integer m that appears in A114183 
infinitelymany times. It is clear that starting with the second 
appearance, thenext term after m must be 2m (as floor(sqrt(m)) is 
allowed to follow mat most once). But then 2m appears in A114183 
infinitely many times,which contradicts to maximality of m. This 
contradiction proves thatA114183 is unbounded.Second, let us prove that 
every positive integer appears in A114183.Assume that some positive 
integer m does not appear in A114183. Thenneither of m^2, m^2+1, ..., 
(m+1)^2 - 1 appear in A114183 (as m wouldfollow 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 ofm^(2^k), m^(2^k)+1, ..., (m+1)^(2^k) 
- 1 appear in A114183 for everyk=0,1,2,...It is clear that (m+1)^(2^k) 
/ m^(2^k) = (1 + 1/m)^(2^k) tends toinfinity as k grows. Therefore, for 
some k, this ratio is grater than2. But then all terms of A114183 must 
be bounded by m^(2^k) as theycannot "jump over" the interval integers 
[m^(2^k), (m+1)^(2^k) - 1]missing in A114183. The contradiction proves 
that every positiveinteger appears in 
A114183.Regards,Max_______________________________________________Seqfan 
Mailing list - http://list.seqfan.eu/