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

Author

Henry Bottomley, May 22 2000

Keywords

• nonn
• easy

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

Examples

			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.
		

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

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.

Programs

Magma

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

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 *)

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

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

Extensions

Examples added by Hieronymus Fischer, Jun 06 2012

New name by David A. Corneth, Nov 02 2023