login
Greatest k such that 3^k divides n!.
52

%I #85 Nov 03 2023 08:45:14

%S 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,

%T 14,14,15,15,15,17,17,17,18,18,18,19,19,19,21,21,21,22,22,22,23,23,23,

%U 26,26,26,27,27,27,28,28,28,30,30,30,31,31,31,32,32,32,34,34,34,35,35

%N Greatest k such that 3^k divides n!.

%C Also the number of trailing zeros in the base-3 representation of n!. - _Hieronymus Fischer_, Jun 18 2007

%C Also the highest power of 6 dividing n!. - _Hieronymus Fischer_, Aug 14 2007

%C A column of A090622. - _Alois P. Heinz_, Oct 05 2012

%C The 'missing' values are listed in A096346. - _Stanislav Sykora_, Jul 16 2014

%H Hieronymus Fischer, <a href="/A054861/b054861.txt">Table of n, a(n) for n = 0..10000</a> (first 1000 terms from T. D. Noe)

%H S-C Liu and J. C.-C. Yeh, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Liu2/liu6.html">Catalan numbers modulo 2^k</a>, J. Int. Seq. 13 (2010), 10.5.4, Eq. (5).

%H A. M. Oller-Marcen and J. Maria Grau, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Oller/oller3.html">On the Base-b Expansion of the Number of Trailing Zeros of b^k!</a>, J. Int. Seq. 14 (2011) 11.6.8

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

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

%F a(n+1) = Sum_{k=1..n} A007949(k). - _Benoit Cloitre_, Mar 24 2002

%F From _Hieronymus Fischer_, Jun 18, Jun 25 and Aug 14 2007: (Start)

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

%F a(n) = Sum_{k=3..n} Sum_{j>=3, j|k} (floor(log_3(j)) - floor(log_3(j-1))).

%F 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.

%F 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))).

%F Recurrence:

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

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

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

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

%F Asymptotic behavior:

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

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

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

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

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

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

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

%F a(n) = A007949(n!). - _R. J. Mathar_, Sep 03 2016

%F From _R. J. Mathar_, Jul 08 2021: (Start)

%F a(n) = A122841(n!).

%F Partial sums of A007949. (End)

%F a(n) = A007949(A000142(n)). - _David A. Corneth_, Nov 02 2023

%e a(100) = 48.

%e a(10^3) = 498.

%e a(10^4) = 4996.

%e a(10^5) = 49995.

%e a(10^6) = 499993.

%e a(10^7) = 4999994.

%e a(10^8) = 49999990.

%e a(10^9) = 499999993.

%p A054861 := proc(n)

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

%p end proc:

%p seq(A054861(n),n=0..1000) ; # _Robert Israel_, Jul 17 2014

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

%t FoldList[Plus, 0, IntegerExponent[Range[100], 3]] (* _T. D. Noe_, Apr 10 2012 *)

%t Table[IntegerExponent[n!,3],{n,0,80}] (* _Harvey P. Dale_, Feb 05 2015 *)

%o (PARI) a(n)=my(s);while(n\=3,s+=n);s \\ _Charles R Greathouse IV_, Jul 25 2011

%o (PARI) a(n)=(n - vecsum(digits(n,3)))\2; \\ _Gheorghe Coserea_, Jan 01 2018

%o (Sage)

%o def A054861(n):

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

%o return A004128(n//3)

%o [A054861(i) for i in (0..76)] # _Peter Luschny_, Nov 16 2012

%o (Magma) [Valuation(Factorial(n), 3): n in [0..80]]; // _Bruno Berselli_, Aug 05 2013

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

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

%Y Cf. A000142, A007949, A053735, A054895, A054899, A067080, A096396, A098844, A132027.

%K nonn,easy

%O 0,7

%A _Henry Bottomley_, May 22 2000

%E Examples added by _Hieronymus Fischer_, Jun 06 2012

%E New name by _David A. Corneth_, Nov 02 2023