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

Neil Sloane njasloane at gmail.com
Fri Mar 8 02:21:03 CET 2013


Franklin, Thanks for this reply!

So far I just read the first half of the proof, and have a
few minor comments. I'll interpolate them IN CAPS.

I'n still having trouble with the second half of the proof though.

Neil

On Mon, Mar 4, 2013 at 8:51 PM, <franktaw at netscape.net> wrote:

> 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 INDICES OF THE TERMS OF THE sequence,
> not on THE VALUES 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.
>
WE WANT TO SHOW k IS IN THE SEQUENCE BEFORE n.

> The previous term, N, SAY, 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 <- SHOULD M BE K? must be followed by k unless
> k is already present. EITHER WAY k IS IN THE SEQUENCE. 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.
>

(FROM HERE ON NOT CLEAR TO ME!)

> 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/
>
> ______________________________**_________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>



-- 
Dear Friends, I have now retired from AT&T. New coordinates:

Neil J. A. Sloane, President, OEIS Foundation
11 South Adelaide Avenue, Highland Park, NJ 08904, USA
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com



More information about the SeqFan mailing list