A090617 -id:A090617 - cp's OEIS frontend

A115627 Irregular triangle read by rows: T(n,k) = multiplicity of prime(k) as a divisor of n!.

1, 1, 1, 3, 1, 3, 1, 1, 4, 2, 1, 4, 2, 1, 1, 7, 2, 1, 1, 7, 4, 1, 1, 8, 4, 2, 1, 8, 4, 2, 1, 1, 10, 5, 2, 1, 1, 10, 5, 2, 1, 1, 1, 11, 5, 2, 2, 1, 1, 11, 6, 3, 2, 1, 1, 15, 6, 3, 2, 1, 1, 15, 6, 3, 2, 1, 1, 1, 16, 8, 3, 2, 1, 1, 1, 16, 8, 3, 2, 1, 1, 1, 1

Offset: 2

Franklin T. Adams-Watters, Jan 26 2006

The factorization of n! is n! = 2^T(n,1)*3^T(n,2)*...*p_(pi(n))^T(n,pi(n)) where p_k = k-th prime, pi(n) = A000720(n).
Nonzero terms of A085604; T(n,k) = A085604(n,k), k = 1..A000720(n). - Reinhard Zumkeller, Nov 01 2013
For n=2, 3, 4 and 5, all terms of the n-th row are odd. Are there other such rows? - Michel Marcus, Nov 11 2018
From Gus Wiseman, May 15 2019: (Start)
Differences between successive rows are A067255, so row n is the sum of the first n row-vectors of A067255 (padded with zeros on the right so that all n row-vectors have length A000720(n)). For example, the first 10 rows of A067255 are
  {}
  1
  0 1
  2 0
  0 0 1
  1 1 0
  0 0 0 1
  3 0 0 0
  0 2 0 0
  1 0 1 0
with column sums (8,4,2,1), which is row 10.
(End)
For all prime p > 7, 3*p > 2*nextprime(p), so for any n > 21 there will always be a prime p dividing n! with exponent 2 and there are no further rows with all entries odd. - Charlie Neder, Jun 03 2019

			From _Gus Wiseman_, May 09 2019: (Start)
Triangle begins:
   1
   1  1
   3  1
   3  1  1
   4  2  1
   4  2  1  1
   7  2  1  1
   7  4  1  1
   8  4  2  1
   8  4  2  1  1
  10  5  2  1  1
  10  5  2  1  1  1
  11  5  2  2  1  1
  11  6  3  2  1  1
  15  6  3  2  1  1
  15  6  3  2  1  1  1
  16  8  3  2  1  1  1
  16  8  3  2  1  1  1  1
  18  8  4  2  1  1  1  1
(End)
m such that 5^m||101!: floor(log(101)/log(5)) = 2 terms. floor(101/5) = 20. floor(20/5) = 4. So m = u_1 + u_2 = 20 + 4 = 24. - _David A. Corneth_, Jun 22 2014

T. D. Noe, Rows n = 2..300, flattened
H. T. Davis, Tables of the Mathematical Functions, Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX. [Annotated scan of pages 204-208 of Volume 2.] See Table 2 on page 206.
Wenguang Zhai, On the prime power factorization of n!, Journal of Number Theory, Volume 129, Issue 8, August 2009, pages 1820-1836.
Index entries for sequences related to factorial numbers

Row lengths are A000720.
Row-sums are A022559.
Row-products are A135291.
Row maxima are A011371.
Columns include A011371, A054861, A027868, A054896, A090617, A064458, A090620.
Cf. A090622, A090623, A000142, A115628.
Cf. A085604, A141809.
Cf. A034876, A067255, A071626, A076934, A322583, A325272, A325273, A325276, A325508, A325509.

a115627 n k = a115627_tabf !! (n-2) !! (k-1)
a115627_row = map a100995 . a141809_row . a000142
a115627_tabf = map a115627_row [2..]
-- Reinhard Zumkeller, Nov 01 2013

A115627 := proc(n,k) local d,p; p := ithprime(k) ; n-add(d,d=convert(n,base,p)) ; %/(p-1) ; end proc: # R. J. Mathar, Oct 29 2010

Flatten[Table[Transpose[FactorInteger[n!]][[2]], {n, 2, 20}]] (* T. D. Noe, Apr 10 2012 *)
T[n_, k_] := Module[{p, jm}, p = Prime[k]; jm = Floor[Log[p, n]]; Sum[Floor[n/p^j], {j, 1, jm}]]; Table[Table[T[n, k], {k, 1, PrimePi[n]}], {n, 2, 20}] // Flatten (* Jean-François Alcover, Feb 23 2015 *)

a(n)=my(i=2);while(n-primepi(i)>1,n-=primepi(i);i++);p=prime(n-1);sum(j=1,log(i)\log(p),i\=p) \\ David A. Corneth, Jun 21 2014

T(n,k) = Sum_{i=1..inf} floor(n/(p_k)^i). (Although stated as an infinite sum, only finitely many terms are nonzero.)

T(n,k) = Sum_{i=1..floor(log(n)/log(p_k))} floor(u_i) where u_0 = n and u_(i+1) = floor((u_i)/p_k). - David A. Corneth, Jun 22 2014

A090622 Square array read by antidiagonals of highest power of k dividing n! (with n,k>1).

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 0, 1, 3, 0, 0, 1, 1, 4, 0, 1, 0, 1, 2, 4, 0, 0, 1, 1, 2, 2, 7, 0, 0, 0, 1, 1, 2, 2, 7, 0, 0, 1, 0, 2, 1, 3, 4, 8, 0, 0, 0, 1, 0, 2, 1, 3, 4, 8, 0, 0, 0, 0, 1, 1, 2, 1, 4, 4, 10, 0, 0, 0, 1, 1, 1, 1, 4, 2, 4, 5, 10, 0, 0, 1, 0, 1, 1, 2, 1, 4, 2, 5, 5, 11, 0, 0, 0, 1, 0, 1, 1, 2, 1, 4, 2, 5, 5, 11

Offset: 2

Henry Bottomley, Dec 06 2003

			Square array starts:
1, 0, 0, 0, 0, 0, 0, ...
1, 1, 0, 0, 1, 0, 0, ...
3, 1, 1, 0, 1, 0, 1, ...
3, 1, 1, 1, 1, 0, 1, ...
4, 2, 2, 1, 2, 0, 1, ...
4, 2, 2, 1, 2, 1, 1, ...
7, 2, 3, 1, 2, 1, 2, ...

Alois P. Heinz, Antidiagonals n = 2..142, flattened

Columns include A011371, A054861, A090616, A027868, A054861, A054896, A090617, A090618, A027868, A064458, A090619, A090620, A054896, A027868, A090621.
Cf. A090623, A090624, A115627.
Diagonal gives A011776. - Alois P. Heinz, Oct 04 2012

f:= proc(n, p) local c, k; c, k:= 0, p;
       while n>=k do c:= c+iquo(n, k); k:= k*p od; c
    end:
T:= (n, k)-> min(seq(iquo(f(n, i[1]), i[2]), i=ifactors(k)[2])):
seq(seq(T(n, 2+d-n), n=2..d), d=2..20);  # Alois P. Heinz, Oct 04 2012

f[n_, p_] := Module[{c = 0, k = p}, While[n >= k , c = c + Quotient[n, k]; k = k*p ]; c ]; t[n_, k_] := Min[ Table[ Quotient[f[n, i[[1]]], i[[2]]], {i, FactorInteger[k]}]]; Table[ Table[t[n, 2 + d - n], {n, 2, d}], {d, 2, 20}] // Flatten (* Jean-François Alcover, Oct 03 2013, translated from Alois P. Heinz's Maple program *)

For k=p prime: T(n,p) = [n/p] + [n/p^2] + [n/p^3] + .... For k = p^m a prime power: T(n,p^m) = [T(n,p)/m]. For k = b*c with b and c coprime: T(n,a*b) = min(T(n,a), T(n,b)). T(n,k) is close to, but below, n/A090624(k).

A054897 a(n) = Sum_{k>0} floor(n/8^k).

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12

Offset: 0

Henry Bottomley, May 23 2000

nonn

Different from the highest power of 8 dividing n!, A090617.

			a(100) = 13.
a(10^3) = 141.
a(10^4) = 1427.
a(10^5) = 14284.
a(10^6) = 142855.
a(10^7) = 1428569.
a(10^8) = 14285710.
a(10^9) = 142857138.

Hieronymus Fischer, Table of n, a(n) for n = 0..10000

Cf. A011371 and A054861 for analogs involving powers of 2 and 3.

Cf. A054899, A067080, A098844, A132032.

m:=8;
function a(n) // a = A054897
  if n eq 0 then return n;
  else return a(Floor(n/m)) + Floor(n/m);
  end if;
end function;
[a(n): n in [0..103]]; // G. C. Greubel, Apr 28 2023

Table[t=0; p=8; While[s=Floor[n/p]; t=t+s; s>0, p *= 8]; t, {n,0,100}]

def A054897(n): return (n-sum(int(d) for d in oct(n)[2:]))//7 # Chai Wah Wu, Jul 09 2022

m=8 # a = A054897
def a(n): return 0 if (n==0) else a(n//m) + (n//m)
[a(n) for n in range(104)] # G. C. Greubel, Apr 28 2023

a(n) = floor(n/8) + floor(n/64) + floor(n/512) + floor(n/4096) + ....
a(n) = (n - A053829(n))/7.
From Hieronymus Fischer, Aug 14 2007: (Start)
Recurrence:
a(n) = floor(n/8) + a(floor(n/8));
a(8*n) = n + a(n);
a(n*8^m) = n*(8^m-1)/7 + a(n).
a(k*8^m) = k*(8^m-1)/7, for 0 <= k < 8, m >= 0.
Asymptotic behavior:
a(n) = n/7 + O(log(n)),
a(n+1) - a(n) = O(log(n)); this follows from the inequalities below.
a(n) <= (n-1)/7; equality holds for powers of 8.
a(n) >= (n-7)/7 - floor(log_8(n)); equality holds for n=8^m-1, m>0.
lim inf (n/7 - a(n)) = 1/7, for n -> oo.
lim sup (n/7 - log_8(n) - a(n)) = 0, for n -> oo.
lim sup (a(n+1) - a(n) - log_8(n)) = 0, for n -> oo.
G.f.: g(x) = ( Sum_{k>0} x^(8^k)/(1-x^(8^k)) )/(1-x). (End)
Partial sums of A244413. - R. J. Mathar, Jul 08 2021

Examples added by Hieronymus Fischer, Jun 06 2012

A090618 Highest power of 9 dividing n!.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 11, 11, 11, 11, 11, 11, 13, 13, 13, 13, 13, 13, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 17, 17, 17, 17, 17, 17, 18, 18, 18, 20, 20, 20, 20

Offset: 0

Henry Bottomley, Dec 06 2003

nonn

			a(9)=2 since 9!=362880=9^2*4480.

Cf. A011371, A054861, A090616, A027868, A054896, A090617.

IntegerExponent[Range[0,90]!,9] (* Harvey P. Dale, Jun 07 2016 *)

a(n) =A090622(n, 9) =[A054861(n)/2] =[([n/3]+[n/9]+[n/27]+[n/81]+...)/2].

A090619 Highest power of 12 dividing n!.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 5, 6, 6, 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 12, 12, 13, 13, 14, 15, 15, 15, 17, 17, 17, 17, 18, 18, 19, 19, 19, 20, 21, 21, 22, 22, 22, 23, 23, 23, 25, 25, 26, 26, 27, 27, 28, 28, 28, 28, 30, 30, 31, 31, 31, 32, 32, 32, 34, 34, 34, 35, 35

Offset: 0

Henry Bottomley, Dec 06 2003

nonn

Most sequences of the form "highest power of k dividing n!" essentially depend on one of the primes or prime powers dividing k. But in this case, the sequences with k=3 (A054861) and k=4 (A090616) are both close to n/2 and vary in which one is lower for different values of n.

a(2^n) = A090616(2^n) and a(3^n-1) = A090616(3^n-1) while a(2^n-1) = A054861(2^n-1) and a(3^n) = A054861(3^n). - Robert Israel, Mar 25 2018

			a(6)=2 since 6!=720=12^2*5.

Robert Israel, Table of n, a(n) for n = 0..10000

Cf. A011371, A054861, A090616, A027868, A054896, A090617, A090618.

f2:= n -> n - convert(convert(n,base,2),`+`):
f3:= n -> (n - convert(convert(n,base,3),`+`))/2:
f:= n -> min(f3(n), floor(f2(n)/2)):
f(0):= 0:
map(f, [$0..100]); # Robert Israel, Mar 23 2018

Table[IntegerExponent[n!, 12], {n, 0, 100}] (* Jean-François Alcover, Mar 26 2018 *)

a(n) = valuation(n!, 12); \\ Michel Marcus, Mar 24 2018

a(n) =A090622(n, 12) =min(A054861(n), A090616(n)). Close to n/2, indeed for n>3: n/2-log3(n+1) <= a(n) < n/2.

A090621 Exponent of highest power of 16 dividing n!.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19

Offset: 0

Henry Bottomley, Dec 06 2003

nonn

			a(10)=2 since 10! = 3628800 = 16^2 * 14175.

Cf. A011371, A054861, A090616, A027868, A054896, A090617, A090618, A090619, A090620.

a(n) = valuation(n!, 16); \\ Michel Marcus, Jul 10 2022

a(n) = A090622(n, 16) = floor(A011371(n)/4) = floor(A090616(n)/2) = floor((floor(n/2) + floor(n/4) + floor(n/8) + floor(n/16) + ...)/4). Almost n/4.

cp's OEIS Frontend

A115627 Irregular triangle read by rows: T(n,k) = multiplicity of prime(k) as a divisor of n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A090622 Square array read by antidiagonals of highest power of k dividing n! (with n,k>1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A054897 a(n) = Sum_{k>0} floor(n/8^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Python

SageMath

Formula

Extensions

A090618 Highest power of 9 dividing n!.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A090619 Highest power of 12 dividing n!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A090621 Exponent of highest power of 16 dividing n!.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Formula