A011776 a(1) = 1; for n > 1, a(n) is defined by the property that n^a(n) divides n! but n^(a(n)+1) does not.

1, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 5, 1, 2, 3, 3, 1, 4, 1, 4, 3, 2, 1, 7, 3, 2, 4, 4, 1, 7, 1, 6, 3, 2, 5, 8, 1, 2, 3, 9, 1, 6, 1, 4, 10, 2, 1, 11, 4, 6, 3, 4, 1, 8, 5, 9, 3, 2, 1, 14, 1, 2, 10, 10, 5, 6, 1, 4, 3, 11, 1, 17, 1, 2, 9, 4, 7, 6, 1, 19, 10, 2, 1, 13, 5, 2, 3, 8, 1, 21

Offset

1,6

Comments

From Stefano Spezia, Nov 08 2018: (Start)

It appears that for n > 1 a(n) = 1 iff n = 4 or a prime number (see A175787).

It appears that a(n) = 2 iff n is in A074845. (End)

Since a prime p is coprime to all positive integers less than p, a(p)=1. - Robert D. Rosales, Jun 17 2024

If n > 4 is composite then a(n) > 1. Proof: 1) If n is not a square of a prime, then n has a divisor d such that 1 < d < n/d < n, so d, n/d and n appear as different factors in n!, n^2 | n!, and therefore a(n) >= 2. 2) If n = p^2 is a square of a prime, then p, 2*p and p^2 appear as different factors in n! when p > 2, therefore a(n) >= 2 if n != 4. - Amiram Eldar, Jul 06 2024

References

Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory Of Numbers, Fifth Edition, John Wiley and Sons, Inc., NY 1991.

Joe Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 251.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)

Nick MacKinnon, How many times does n go into nǃ, The Mathematical Gazette, Vol. 70, No. 453 (1986), pp. 203-205.

Peter Shui, A footnote on the number of times n goes into n!, The Mathematical Gazette, Vol. 93, No. 528 (2009), pp. 492-495.

Eric Weisstein's World of Mathematics, Factorial.

Index entries for sequences related to factorial numbers.

Example

12^5 divides 12! but 12^6 does not so a(12) = 5.

Maple

a := []; for n from 2 to 200 do i := 0: while n! mod n^i = 0 do i := i+1: od: a := [op(a), i-1]; od: a;
# second Maple program:
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:
a:= n-> min(seq(iquo(f(n, i[1]), i[2]), i=ifactors(n)[2])): a(1):=1:
seq(a(n), n=1..100);  # Alois P. Heinz, Oct 04 2012

Mathematica

Do[m = 1; While[ IntegerQ[ n!/n^m], m++ ]; Print[m - 1], {n, 1, 100} ]
HighestPower[n_, p_] := Module[{r, s=0, k=1}, While[r=Floor[n/p^k]; r>0, s=s+r; k++ ]; s]; SetAttributes[HighestPower, Listable]; Join[{1}, Table[{p, e}=Transpose[FactorInteger[n]]; Min[Floor[HighestPower[n, p]/e]], {n, 2, 100}]] (* T. D. Noe, Oct 01 2008 *)
Join[{1}, Table[IntegerExponent[n!, n], {n, 2, 500}]] (* Vladimir Joseph Stephan Orlovsky, Dec 26 2010 *)
f[n_, p_] := Module[{c=0, k=p}, While[n >= k , c = c + Quotient[n, k]; k = k*p ]; c]; a[1]=1; a[n_] := Min[ Table[ Quotient[f[n, i[[1]]], i[[2]]], {i, FactorInteger[n] }]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Oct 03 2013, after Alois P. Heinz's Maple program *)

Prog

(Haskell)
a011776 1 = 1
a011776 n = length $
   takeWhile ((== 0) . (mod (a000142 n))) $ iterate (* n) n
-- Reinhard Zumkeller, Sep 01 2012
(PARI) a(n)=if(n>1, valuation(n!, n), 1); \\ Charles R Greathouse IV, Apr 10 2014
(PARI) vp(n, p)=my(s); while(n\=p, s+=n); s
a(n)=if(n==1, return(1)); my(f=factor(n)); vecmin(vector(#f~, i, vp(n, f[i, 1])\f[i, 2])) \\ Charles R Greathouse IV, Apr 10 2014

Crossrefs

Cf. A011777, A011778, A133481, A000142, A074845.

Diagonal of A090622.

Cf. A175787 (primes together with 4).

Sequence in context: A324386 A233390 A324114 * A375624 A345182 A297791

Adjacent sequences: A011773 A011774 A011775 * A011777 A011778 A011779

Keyword

nonn,easy,look,nice

Author

Robert G. Wilson v

Status

approved