[seqfan] Re: Exponent of highest power of 2 dividing n is equal to exponent of highest power of 3 dividing n

Chris Thompson cet1 at cam.ac.uk
Sat Sep 3 18:54:16 CEST 2016

On Sep 1 2016, Charles Greathouse wrote:
>Juri-Stepan Gerasimov submitted a nice sequence which turned out to be a
>duplicate of https://oeis.org/A064615
>It's not hard to prove that a(n) ~ 5n/2. But I can't find a reasonable
>error term. Can anyone help?
>For example, a(174142594) = 435356467 is at a record distance of 18 from
>the asymptotic at 435356485, and this is suggestive of a logarithmic error
>(which is what I would naively expect).

and on Sep 2 2016, israel at math.ubc.ca wrote:

>The number of members of the sequence <= N is the sum over k>=0 of the 
>number of positive integers <= N/6^k congruent to 1 or 5 mod 6, thus
>Sum_{k=0 .. log_6(N)} floor((N/6^k+5)/6) 
>+ Sum_{k=0 .. log_6(N/5)} floor((N/6^k+1)/6)
>This is within O(log N) of 2 Sum_{k>=0} N/6^(k+1) = 2*N/5.
>So you should indeed get an error term O(log n).

For a tighter limit, it seems best to follow Robert Israel's line
and use the inverse function b(n) = (# of terms of A064615 <= n),
and look at n-(5/2)b(n) rather than a(n)-(5n/2). 

If n is expressed in base 6 as Sum_i{6^i*n_i}, 0<=n_i<=5, then one has

 b(n) = (n + Sum_i{f_1(n_i)})/5     [count of terms 6^j*(6k+1)]
       +(n + Sum_i{f_5(n_i)})/5     [count of terms 6^j*(6k+5)]
      = (2n + Sum_i{f(n_i)})/5

where f_1(0,1,2,3,4,5) = (0,4,3,2,1,0),
      f_5(0,1,2,3,4,5) = (0,-1,-2,-3,-4,0),
  and f(0,1,2,3,4,5)   = (0,3,1,-1,-3,0) respectively.

It's straightforward to prove these formulae by induction on n.

So the most negative values of n-(5/2)b(n) occur for the all-1's
values n=(6^k-1)/5 where it is -3k/2. [Charles Greathouse's example
is the case k=12.] The most positive values occur for the all-4's
values n=4(6^k-1)/5 where it is +3k/2, but if one insists on a
value of n that actually occurs in A064615 then for n=1+4(6^k-1)/5
one has only +3(k-1)/2 instead.
Chris Thompson
Email: cet1 at cam.ac.uk

More information about the SeqFan mailing list