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!. 39
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

LINKS

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

FORMULA

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

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

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.

MATHEMATICA

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

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

PROG

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

(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

CROSSREFS

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

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

Cf. A011371 for analogue involving powers of 2. See also A027868.

See A004128 for a(3n).

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

A column of A090622.

Sequence in context: A106160 A007614 A113402 * A187324 A086227 A079438

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 | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified June 20 05:50 EDT 2013. Contains 226419 sequences.