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