|
%I #90 Jan 31 2024 21:49:32
%S 0,1,1,2,2,3,1,2,2,3,3,4,2,3,3,4,4,5,3,4,4,5,5,6,1,2,2,3,3,4,2,3,3,4,
%T 4,5,3,4,4,5,5,6,4,5,5,6,6,7,2,3,3,4,4,5,3,4,4,5,5,6,4,5,5,6,6,7,5,6,
%U 6,7,7,8,3,4,4,5,5,6,4,5,5,6,6,7,5,6,6,7,7,8,6,7,7,8,8,9,4,5,5,6,6,7,5,6,6,7
%N Minimal number of factorials that add to n.
%C Equivalently, sum of digits when n is written in factorial base (A007623).
%C Equivalently, a(0)...a(n!-1) give the total number of inversions of the permutations of n elements in lexicographic order (the factorial numbers in rising base are the inversion tables of the permutations and their sum of digits give the total number of inversions, see example and the Fxtbook link). - _Joerg Arndt_, Jun 17 2011
%C Also minimum number of adjacent transpositions needed to produce each permutation in the list A055089, or number of swappings needed to bubble sort each such permutation. (See A055091 for the minimum number of any transpositions.)
%H Alois P. Heinz, <a href="/A034968/b034968.txt">Table of n, a(n) for n = 0..10000</a>
%H F. T. Adams-Watters and F. Ruskey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Ruskey2/ruskey14.html">Generating Functions for the Digital Sum and Other Digit Counting Sequences</a>, JIS 12 (2009) 09.5.6.
%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, fig.10-1.B on p.234.
%H Tyler Ball, Joanne Beckford, Paul Dalenberg, Tom Edgar, and Tina Rajabi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Edgar/edgar3.html">Some Combinatorics of Factorial Base Representations</a>, J. Int. Seq., Vol. 23 (2020), Article 20.3.3.
%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000018">The number of inversions of a permutation</a>
%H <a href="/index/Fa#facbase">Index entries for sequences related to factorial base representation</a>
%F a(n) = n - Sum_{i>=2} (i-1)*floor(n/i!). - _Benoit Cloitre_, Aug 26 2003
%F G.f.: 1/(1-x)*Sum_{k>0} (Sum_{i=1..k} i*x^(i*k!))/(Sum_{i=0..k} x^(i*k!)). - _Franklin T. Adams-Watters_, May 13 2009
%F From _Antti Karttunen_, Aug 29 2016: (Start)
%F a(0) = 0; for n >= 1, a(n) = A099563(n) + a(A257687(n)).
%F a(0) = 0; for n >= 1, a(n) = A060130(n) + a(A257684(n)).
%F Other identities. For all n >= 0:
%F a(n) = A001222(A276076(n)).
%F a(n) = A276146(A225901(n)).
%F a(A000142(n)) = 1, a(A007489(n)) = n, a(A033312(n+1)) = A000217(n).
%F a(A056019(n)) = a(n).
%F A219651(n) = n - a(n).
%F (End)
%e a(205) = a(1!*1 + 3!*2 + 4!*3 + 5!*1) = 1+2+3+1 = 7. [corrected by Shin-Fu Tsai, Mar 23 2021]
%e From _Joerg Arndt_, Jun 17 2011: (Start)
%e n: permutation inv. table a(n) cycles
%e 0: [ 0 1 2 3 ] [ 0 0 0 ] 0 (0) (1) (2) (3)
%e 1: [ 0 1 3 2 ] [ 0 0 1 ] 1 (0) (1) (2, 3)
%e 2: [ 0 2 1 3 ] [ 0 1 0 ] 1 (0) (1, 2) (3)
%e 3: [ 0 2 3 1 ] [ 0 1 1 ] 2 (0) (1, 2, 3)
%e 4: [ 0 3 1 2 ] [ 0 2 0 ] 2 (0) (1, 3, 2)
%e 5: [ 0 3 2 1 ] [ 0 2 1 ] 3 (0) (1, 3) (2)
%e 6: [ 1 0 2 3 ] [ 1 0 0 ] 1 (0, 1) (2) (3)
%e 7: [ 1 0 3 2 ] [ 1 0 1 ] 2 (0, 1) (2, 3)
%e 8: [ 1 2 0 3 ] [ 1 1 0 ] 2 (0, 1, 2) (3)
%e 9: [ 1 2 3 0 ] [ 1 1 1 ] 3 (0, 1, 2, 3)
%e 10: [ 1 3 0 2 ] [ 1 2 0 ] 3 (0, 1, 3, 2)
%e 11: [ 1 3 2 0 ] [ 1 2 1 ] 4 (0, 1, 3) (2)
%e 12: [ 2 0 1 3 ] [ 2 0 0 ] 2 (0, 2, 1) (3)
%e 13: [ 2 0 3 1 ] [ 2 0 1 ] 3 (0, 2, 3, 1)
%e 14: [ 2 1 0 3 ] [ 2 1 0 ] 3 (0, 2) (1) (3)
%e 15: [ 2 1 3 0 ] [ 2 1 1 ] 4 (0, 2, 3) (1)
%e 16: [ 2 3 0 1 ] [ 2 2 0 ] 4 (0, 2) (1, 3)
%e 17: [ 2 3 1 0 ] [ 2 2 1 ] 5 (0, 2, 1, 3)
%e 18: [ 3 0 1 2 ] [ 3 0 0 ] 3 (0, 3, 2, 1)
%e 19: [ 3 0 2 1 ] [ 3 0 1 ] 4 (0, 3, 1) (2)
%e 20: [ 3 1 0 2 ] [ 3 1 0 ] 4 (0, 3, 2) (1)
%e 21: [ 3 1 2 0 ] [ 3 1 1 ] 5 (0, 3) (1) (2)
%e 22: [ 3 2 0 1 ] [ 3 2 0 ] 5 (0, 3, 1, 2)
%e 23: [ 3 2 1 0 ] [ 3 2 1 ] 6 (0, 3) (1, 2)
%e (End)
%p [seq(convert(fac_base(j),`+`),j=0..119)]; # fac_base and PermRevLexUnrank given in A055089. Perm2InversionVector in A064039
%p Or alternatively: [seq(convert(Perm2InversionVector(PermRevLexUnrank(j)),`+`),j=0..119)];
%p # third Maple program:
%p b:= proc(n, i) local q;
%p `if`(n=0, 0, b(irem(n, i!, 'q'), i-1)+q)
%p end:
%p a:= proc(n) local k;
%p for k while k!<n do od; b(n, k)
%p end:
%p seq(a(n), n=0..200); # _Alois P. Heinz_, Nov 15 2012
%t a[n_] := Module[{s=0, i=2, k=n}, While[k > 0, k = Floor[n/i!]; s = s + (i-1)*k; i++]; n-s]; Table[a[n], {n, 0, 105}] (* _Jean-François Alcover_, Nov 06 2013, after _Benoit Cloitre_ *)
%o (PARI) a(n)=local(k,r);k=2;r=0;while(n>0,r+=n%k;n\=k;k++);r \\ _Franklin T. Adams-Watters_, May 13 2009
%o (Scheme)
%o (define (A034968 n) (let loop ((n n) (i 2) (s 0)) (cond ((zero? n) s) (else (loop (quotient n i) (+ 1 i) (+ s (remainder n i)))))))
%o ;; _Antti Karttunen_, Aug 29 2016
%o (Python)
%o def a(n):
%o k=2
%o r=0
%o while n>0:
%o r+=n%k
%o n=n//k
%o k+=1
%o return r
%o print([a(n) for n in range(201)]) # _Indranil Ghosh_, Jun 19 2017, after PARI program
%Y Cf. A368342 (partial sums), A001809 (sums of n! terms).
%Y Cf. A000142, A007489, A007623, A033312, A055091, A139365.
%Y Cf. A000217, A001222, A056019, A060130, A099563, A225901, A257684, A257687, A257694, A276076, A276146.
%Y Cf. A227148 (positions of even terms), A227149 (of odd terms).
%Y Cf. also A219650, A219651, A219666, A230423.
%Y Differs from analogous A276150 for the first time at n=24.
%Y Positions of records are A200748.
%K nonn
%O 0,4
%A _Erich Friedman_
%E Additional comments from _Antti Karttunen_, Aug 23 2001
|
