A054861 Greatest k such that 3^k divides n!.

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

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

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

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

A. M. Oller-Marcen and 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, Jun 25 and Aug 14 2007: (Start)

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

a(n) = Sum_{k=3..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, otherwise b(k)=0.

G.f.: (1/(1-x))*Sum_{k>0} c(k)*x^k, 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

From R. J. Mathar, Jul 08 2021: (Start)

a(n) = A122841(n!).

Partial sums of A007949. (End)

a(n) = A007949(A000142(n)). - David A. Corneth, Nov 02 2023

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. A000142, A007949, A053735, A054895, A054899, A067080, A096396, A098844, A132027.

Sequence in context: A113402 A238726 A240321 * A187324 A334207 A323094

Adjacent sequences: A054858 A054859 A054860 * A054862 A054863 A054864

Keyword

nonn,easy

Author

Henry Bottomley, May 22 2000

Extensions

Examples added by Hieronymus Fischer, Jun 06 2012

New name by David A. Corneth, Nov 02 2023

Status

approved