# [seqfan] Re: Hofstadter's A005228, differences=complement

Benoît Jubin benoit.jubin at gmail.com
Wed May 22 00:55:24 CEST 2013

Thanks, I'll do it before the weekend (formulas on the sequence pages
and attached file with the proofs).

Benoit

On Wed, May 22, 2013 at 12:33 AM, Neil Sloane <njasloane at gmail.com> wrote:
> Benoit,
>
> That is really excellent work - thanks!
>
> Could you add this information to A005228 and A030124?
>
> It could take the form of a plain text file or a pdf file attached
> to those entries.
>
> Neil
>
>
> On Tue, May 21, 2013 at 5:26 PM, Benoît Jubin <benoit.jubin at gmail.com>wrote:
>
>> I obtained an asymptotic expansion for these sequences to arbitrary
>> order: let u(n) = A030124(n) - n. Then
>> u(n) ~ \sum_{k>=1} c(k) (n/2)^{1/2^k}
>> where
>> c(k) = (-1)^{k+1} 2^Fibo(k+1) / (prod_{m=1}^{k-1} (2^m+1)).
>> One then finds the asymptotic expansion of A005228 by integration.
>>
>> I used the relation
>> A005228(u_n) = n + O(u_n),
>> which follows from the partition condition, to obtain via integration
>> u_n^2 + 2 \sum_{k=1}^{u_n} u_k = 2n + O(\sqrt{n}).
>> From this formula, one obtains the above expansion by induction.
>>
>> Benoît Jubin
>>
>>
>> On Mon, May 20, 2013 at 4:35 AM, Neil Sloane <njasloane at gmail.com> wrote:
>> > I also thought the offset was strange, and since
>> > you said the same thing, I just changed it!
>> >
>> >
>> > On Sun, May 19, 2013 at 10:15 PM, Benoît Jubin <benoit.jubin at gmail.com
>> >wrote:
>> >
>> >> > Right now I don't even know a proof that A030124(n) is asymptotic to
>> n,
>> >> although this should not be too difficult.
>> >>
>> >> This has probably been noticed by the interested parties already, but
>> >> here it is:
>> >> Since the sequence of first differences of A005228 is strictly
>> >> increasing, one has A005228(n) >= n(n+1)/2. Therefore A030124(n-1) is
>> >> bounded by the complement of the sequence (n(n+1)/2), call it b.
>> >> If (n-1)n/2 < k <= n(n+1)/2, then b(k) = (n+1)(n+2)/2 - 1 - ( n(n+1)/2
>> >> - k) = n + k, so computing n in terms of k, one has
>> >> A030124(k-1) <= k + ceil( sqrt(2k+1/4) - 1/2)
>> >> and for k large enough (for instance k>100), one has
>> >> k < A030124(k-1) < k + sqrt(2k)
>> >>
>> >> (the offset of A030124 is peculiar)
>> >>
>> >> Benoît
>> >>
>> >>
>> >> On Sun, May 19, 2013 at 5:17 PM, Neil Sloane <njasloane at gmail.com>
>> wrote:
>> >> > Alan, thanks for telling me. In fact both b-files (A005228 and
>> A030124)
>> >> > were wrong, and I have now corrected them.
>> >> >
>> >> > Right now I don't even know a proof that A030124(n) is
>> >> > asymptotic to n, although this should not be too difficult.
>> >> > I still don't have any rigorous bounds for either sequence.
>> >> >
>> >> > Neil
>> >> >
>> >> >
>> >> > On Sun, May 19, 2013 at 9:33 AM, Allan Wechsler <acwacw at gmail.com>
>> >> wrote:
>> >> >
>> >> >> I don't have an answer to the question, but the graph at A005228
>> looks
>> >> >> wrong. It looks like the graph for A030124 instead.
>> >> >>
>> >> >>
>> >> >> On Wed, May 15, 2013 at 7:25 PM, Neil Sloane <njasloane at gmail.com>
>> >> wrote:
>> >> >>
>> >> >> > Has anyone seen any rigorous bounds on A005228(n)
>> >> >> > or A030124(n)?
>> >> >> > Neil
>> >> >> >
>> >> >> > _______________________________________________
>> >> >> >
>> >> >> > 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
>> >> > Email: njasloane at gmail.com
>> >> >
>> >> > _______________________________________________
>> >> >
>> >> > 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
>> > Email: njasloane at gmail.com
>> >
>> > _______________________________________________
>> >
>> > 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