login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A054861 Highest power of 3 dividing n!. 50
0, 0, 0, 1, 1, 1, 2, 2, 2, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 9, 10, 10, 10, 13, 13, 13, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 18, 19, 19, 19, 21, 21, 21, 22, 22, 22, 23, 23, 23, 26, 26, 26, 27, 27, 27, 28, 28, 28, 30, 30, 30, 31, 31, 31, 32, 32, 32, 34, 34, 34, 35, 35 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

Also the number of trailing zeros in the base-3 representation of n!. - Hieronymus Fischer, Jun 18 2007

Also the highest power of 6 dividing n!. - Hieronymus Fischer, Aug 14 2007

A column of A090622. - Alois P. Heinz, Oct 05 2012

The 'missing' values are listed in A096346. - Stanislav Sykora, Jul 16 2014

LINKS

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

S-C Liu, J. C.-C. Yeh, Catalan numbers modulo 2^k, J. Int. Seq. 13 (2010), 10.5.4, Eq. (5).

A. M. Oller-Marcen, J. Maria Grau, On the Base-b Expansion of the Number of Trailing Zeros of b^k!, J. Int. Seq. 14 (2011) 11.6.8

FORMULA

a(n) = floor(n/3) + floor(n/9) + floor(n/27) + floor(n/81) + ... .

a(n) = (n - A053735(n))/2.

a(n+1) = sum(k=1, n, A007949(k)). - Benoit Cloitre, Mar 24 2002

From Hieronymus Fischer, Jun 18 and Jun 25 and Aug 14 2007: (Start)

G.f.: sum{k>0, x^(3^k)/(1-x^(3^k))}/(1-x).

a(n) = sum{3<=k<=n, sum{j>=3,j|k, floor(log_3(j)) - floor(log_3(j-1))}}.

G.f.: L[b(k)](x)/(1-x), where L[b(k)](x) = sum{k>=0, b(k)*x^k/(1-x^k)} is a Lambert series with b(k) = 1, if k>1 is a power of 3, else b(k)=0.

G.f.: sum{k>0, c(k)*x^k}/(1-x), where c(k) = sum{j>1, j|k, floor(log_3(j)) - floor(log_3(j-1))}.

Recurrence:

a(n) = floor(n/3) + a(floor(n/3));

a(3*n) = n + a(n);

a(n*3^m) = n*(3^m-1)/2 + a(n).

a(k*3^m) = k*(3^m-1)/2, for 0<=k<3, m>=0.

Asymptotic behavior:

a(n) = n/2 + O(log(n)),

a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.

a(n) <= (n-1)/2; equality holds for powers of 3.

a(n) >= (n-2)/2 - floor(log_3(n)); equality holds for n=3^m-1, m>0.

lim inf (n/2 - a(n)) = 1/2, for n-->oo.

lim sup (n/2 - log_3(n) - a(n)) = 0, for n-->oo.

lim sup (a(n+1) - a(n) - log_3(n)) = 0, for n-->oo. (End)

a(n) = A007949(n!). - R. J. Mathar, Sep 03 2016

EXAMPLE

a(100) = 48.

a(10^3) = 498.

a(10^4) = 4996.

a(10^5) = 49995.

a(10^6) = 499993.

a(10^7) = 4999994.

a(10^8) = 49999990.

a(10^9) = 499999993.

MAPLE

A054861 := proc(n)

    (n - convert(convert(n, base, 3), `+`))/2 ;

end proc:

seq(A054861(n), n=0..1000) ; # Robert Israel, Jul 17 2014

MATHEMATICA

(Plus@@Floor[#/3^Range[Length[IntegerDigits[#, 3]]-1]]&)/@Range[0, 100] (* Peter J. C. Moses, Apr 07 2012 *)

FoldList[Plus, 0, IntegerExponent[Range[100], 3]] (* T. D. Noe, Apr 10 2012 *)

Table[IntegerExponent[n!, 3], {n, 0, 80}] (* Harvey P. Dale, Feb 05 2015 *)

PROG

(PARI) a(n)=my(s); while(n\=3, s+=n); s \\ Charles R Greathouse IV, Jul 25 2011

(PARI) a(n)=(n - vecsum(digits(n, 3)))\2; \\ Gheorghe Coserea, Jan 01 2018

(Sage)

def A054861(n):

    A004128 = lambda n: A004128(n//3) + n if n > 0 else 0

    return A004128(n//3)

[A054861(i) for i in (0..76)]  # Peter Luschny, Nov 16 2012

(MAGMA) [Valuation(Factorial(n), 3): n in [0..80]]; // Bruno Berselli, Aug 05 2013

CROSSREFS

Cf. A011371 (for analog involving powers of 2). See also A027868.

Cf. A004128 (for a(3n)).

Cf. A053735, A054895, A054899, A067080, A096396, A098844, A132027.

Sequence in context: A113402 A238726 A240321 * A187324 A086227 A302402

Adjacent sequences:  A054858 A054859 A054860 * A054862 A054863 A054864

KEYWORD

easy,nonn

AUTHOR

Henry Bottomley, May 22 2000

EXTENSIONS

Examples added by Hieronymus Fischer, Jun 06 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 21:09 EDT 2018. Contains 316505 sequences. (Running on oeis4.)