[seqfan] Re: Near-linear sequence

[Benoît Jubin]

Here are some drafty computations:
The asymptotic behavior of a is determined, at least at first order,
by its values at the powers of 2, so I concentrate on the latter.
One has
a(2^n) = a(2^{n-1}) + a(2^{n-1}-1)
a(2^{n-1}-1) = a(2^{n-2}) + a(2^{n-2}-2)
...
a(2^{n-k}-k) = a(2^{n-k-1}) + a(2^{n-k-1}-k-1)
...
as long as 2^{n-k-1} < 2^{n-k} - k, that is, k < W_2(2^{n-1}), where
W_2 is the base 2 Lambert function, that is, W_2(x) =
W(x.log(2))/log(2), else, one simply has
a(2^{n-k}-k) = a(2^{n-k-1}).
Putting these together, one obtains:
a(2^n) = a(2^{n-1}) + \dots + a(2^{n-floor(W_2(2^{n-1}))-2}).
In the remaining, I forget the "floor" and the "-2".
Defining the sequence u by u(n) = u(2^n), one obtains
u(n) = u(n-1) + \dots + u(n-W_2(2^{n-1})).
Now, the asymptotic behavior W(x) = ln x - ln ln x + o(1) tells us
(this can be be made rigorous) that
u(n) ~  u(n-1) + \dots + u(log_2 n).
This is the discrete analog of the integral equation
y(t) = \int_{\log_2 t}^t y.
Differentiating and solving the differential equation thus obtained
gives y(t) = K 2^t/t
This gives u(n) ~ K 2^n/n so
a(n) ~ K n/log_2(n).
This looks (a priori) to contradict Charles Greathouse's numerical
experiments, so maybe it's log log... I'll try to check later.

Benoit




On Wed, Aug 27, 2014 at 7:14 PM, Neil Sloane <njasloane at gmail.com> wrote:
> Concerning A101402, the terms fall naturally into blocks of sizes
> 1,1,1,2,4,8,16,32,...:
>
> 0,
>
> 1,
>
> 1,
>
> 1, 2,
>
> 2, 3, 3, 3,
>
> 3, 4, 4, 4, 5, 5, 6, 6,
>
> 6, 7, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12,
>
> 12, 13, 13, 13, 14, 14, ...
>
> Then the definition says that the k-th block is the final term of the
> previous block added to the sequence starting from the beginning.
> (Eg 34445566 = 3+01112233)
>
> The final terms of the blocks, a(2^k), appear to be given by A164363.
> Is that obvious?
>
> Neil
>
> On Wed, Aug 27, 2014 at 12:39 PM, Charles Greathouse
> <charles.greathouse at case.edu> wrote:
>> Sequence A101402 appears to be nearly linear. For the first 10,000 terms
>> there is a constant k such that |a(n) - kn| < 2 (e.g., take k = 0.355). Can
>> anyone prove or disprove that a(n) = kn + O(1) for some constant k? In the
>> (likely?) latter case, can another reasonable bound be found, maybe O(log
>> n)? I can't even think of a technique that would work here.
>>
>> I just checked to a million and it looks like the same holds. Here I used k
>> = 0.3549419505. Probably going to 10 million would require relaxing the
>> bound slightly; already by a million the choice of constant is very
>> constrained.
>>
>> Charles Greathouse
>> Analyst/Programmer
>> Case Western Reserve University
>>
>> _______________________________________________
>>
>> 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.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/