A055881 a(n) = largest m such that m! divides n.

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1

Offset: 1

Author

Leroy Quet and Labos Elemer, Jul 16 2000

Keywords

• easy
• nonn

Comments

Number of factorial divisors of n. - Amarnath Murthy, Oct 19 2002

The sequence may be constructed as follows. Step 1: start with 1, concatenate and add +1 to last term gives: 1,2. Step 2: 2 is the last term so concatenate twice those terms and add +1 to last term gives: 1, 2, 1, 2, 1, 3 we get 6 terms. Step 3: 3 is the last term, concatenate 3 times those 6 terms and add +1 to last term gives: 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, iterates. At k-th step we obtain (k+1)! terms. - Benoit Cloitre, Mar 11 2003

From Benoit Cloitre, Aug 17 2007, edited by M. F. Hasler, Jun 28 2016: (Start)

Another way to construct the sequence: start from an infinite series of 1's:

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... Replace every second 1 by a 2 giving:

1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ... Replace every third 2 by a 3 giving:

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, ... Replace every fourth 3 by a 4 etc. (End)

This sequence is the fixed point, starting with 1, of the morphism m, where m(1) = 1, 2, and for k > 1, m(k) is the concatenation of m(k - 1), the sequence up to the first k, and k + 1. Thus m(2) = 1, 2, 1, 3; m(3) = 1, 2, 1, 3, 1, 2, 1, 2, 1, 4; m(4) = 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 5, etc. - Franklin T. Adams-Watters, Jun 10 2009

All permutations of n elements can be listed as follows: Start with the (arbitrary) permutation P(0), and to obtain P(n + 1), reverse the first a(n) + 1 elements in P(n). The last permutation is the reversal of the first, so the path is a cycle in the underlying graph. See example and fxtbook link. - Joerg Arndt, Jul 16 2011

Positions of rightmost change with incrementing rising factorial numbers, see example. - Joerg Arndt, Dec 15 2012

Records appear at factorials. - Robert G. Wilson v, Dec 21 2012

One more than the number of trailing zeros (A230403(n)) in the factorial base representation of n (A007623(n)). - Antti Karttunen, Nov 18 2013

A062356(n) and a(n) coincide quite often. - R. J. Cano, Aug 04 2014

For n>0 and 1<=j<=(n+1)!-1, (n+1)^2-1=A005563(n) is the number of times that a(j)=n-1. - R. J. Cano, Dec 23 2016

Examples

			a(12) = 3 because 3! is highest factorial to divide 12.
From _Joerg Arndt_, Jul 16 2011: (Start)
All permutations of 4 elements via prefix reversals:
   n:   permutation  a(n)+1
   0:   [ 0 1 2 3 ]  -
   1:   [ 1 0 2 3 ]  2
   2:   [ 2 0 1 3 ]  3
   3:   [ 0 2 1 3 ]  2
   4:   [ 1 2 0 3 ]  3
   5:   [ 2 1 0 3 ]  2
   6:   [ 3 0 1 2 ]  4
   7:   [ 0 3 1 2 ]  2
   8:   [ 1 3 0 2 ]  3
   9:   [ 3 1 0 2 ]  2
  10:   [ 0 1 3 2 ]  3
  11:   [ 1 0 3 2 ]  2
  12:   [ 2 3 0 1 ]  4
  13:   [ 3 2 0 1 ]  2
  14:   [ 0 2 3 1 ]  3
  15:   [ 2 0 3 1 ]  2
  16:   [ 3 0 2 1 ]  3
  17:   [ 0 3 2 1 ]  2
  18:   [ 1 2 3 0 ]  4
  19:   [ 2 1 3 0 ]  2
  20:   [ 3 1 2 0 ]  3
  21:   [ 1 3 2 0 ]  2
  22:   [ 2 3 1 0 ]  3
  23:   [ 3 2 1 0 ]  2
(End)
From _Joerg Arndt_, Dec 15 2012: (Start)
The first few rising factorial numbers (dots for zeros) with 4 digits and the positions of the rightmost change with incrementing are:
  [ 0]    [ . . . . ]   -
  [ 1]    [ 1 . . . ]   1
  [ 2]    [ . 1 . . ]   2
  [ 3]    [ 1 1 . . ]   1
  [ 4]    [ . 2 . . ]   2
  [ 5]    [ 1 2 . . ]   1
  [ 6]    [ . . 1 . ]   3
  [ 7]    [ 1 . 1 . ]   1
  [ 8]    [ . 1 1 . ]   2
  [ 9]    [ 1 1 1 . ]   1
  [10]    [ . 2 1 . ]   2
  [11]    [ 1 2 1 . ]   1
  [12]    [ . . 2 . ]   3
  [13]    [ 1 . 2 . ]   1
  [14]    [ . 1 2 . ]   2
  [15]    [ 1 1 2 . ]   1
  [16]    [ . 2 2 . ]   2
  [17]    [ 1 2 2 . ]   1
  [18]    [ . . 3 . ]   3
  [19]    [ 1 . 3 . ]   1
  [20]    [ . 1 3 . ]   2
  [21]    [ 1 1 3 . ]   1
  [22]    [ . 2 3 . ]   2
  [23]    [ 1 2 3 . ]   1
  [24]    [ . . . 1 ]   4
  [25]    [ 1 . . 1 ]   1
  [26]    [ . 1 . 1 ]   2
(End)
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10080
• Joerg Arndt, Matters Computational (The Fxtbook), section 10.4, pp.245-248 (prefix reversals); section 10.5, pp. 248-250 (Heap's method).
• R. J. Cano, Alternative sequencer (PARI/GP).
• Claude Lenormand, Comments on this sequence.
• József Sándor, On Additive Analogues of Certain Arithmetic Smarandache Functions.
• Index entries for sequences related to factorial base representation.

Crossrefs

Cf. A055874, A055926, A055770, A062356, A073575, A091131, A230403, A230404, A230405, A076733, A232096, A232098, A233285, A233267, A233269, A231719, A232741, A232742, A232743, A232744, A232745, A060832 (partial sums).

This sequence occurs also in the next to middle diagonals of A230415 and as the second rightmost column of triangle A230417.

Other sequences related to factorial base representation (A007623): A034968, A084558, A099563, A060130, A227130, A227132, A227148, A227149, A153880.

Analogous sequence for binary (base-2) representation: A001511.

Programs

Mathematica

Table[Length[Intersection[Divisors[n], Range[5]!]], {n, 125}] (* Alonso del Arte, Dec 10 2012 *)
f[n_] := Block[{m = 1}, While[Mod[n, m!] == 0, m++]; m - 1]; Array[f, 105] (* Robert G. Wilson v, Dec 21 2012 *)

PARI

See Cano link.

PARI

n=5; f=n!; x='x+O('x^f); Vec(sum(k=1,n,x^(k!)/(1-x^(k!)))) \\ Joerg Arndt, Jan 28 2014

PARI

a(n)=for(k=2,n+1,if(n%k, return(k-1),n/=k)) \\ Charles R Greathouse IV, May 28 2015

Scheme

(define (A055881 n) (let loop ((n n) (i 2)) (cond ((not (zero? (modulo n i))) (- i 1)) (else (loop (/ n i) (+ 1 i))))))

Formula

G.f.: Sum_{k > 0} x^(k!)/(1 - x^(k!)). - Vladeta Jovovic, Dec 13 2002

a(n) = A230403(n)+1. - Antti Karttunen, Nov 18 2013

a(n) = A230415(n-1,n) = A230415(n,n-1) = A230417(n,n-1). - Antti Karttunen, Nov 19 2013

a(m!+n) = a(n) if 1 <= n <= m*m! - 1 = A001563(m) - 1. - R. J. Cano, Jun 27 2016

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = e - 1 (A091131). - Amiram Eldar, Jul 23 2022