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

Benoît Jubin benoit.jubin at gmail.com
Tue May 21 23:26:25 CEST 2013

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