This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A034968 #96 Oct 27 2024 13:03:05
%S A034968 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 A034968 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 A034968 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 A034968 Minimal number of factorials that add to n.
%C A034968 Equivalently, sum of digits when n is written in factorial base (A007623).
%C A034968 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 A034968 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 A034968 Alois P. Heinz, <a href="/A034968/b034968.txt">Table of n, a(n) for n = 0..10000</a>
%H A034968 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 A034968 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, fig.10-1.B on p.234.
%H A034968 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 A034968 FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/St000018">The number of inversions of a permutation</a>
%H A034968 <a href="/index/Fa#facbase">Index entries for sequences related to factorial base representation</a>
%F A034968 a(n) = n - Sum_{i>=2} (i-1)*floor(n/i!). - _Benoit Cloitre_, Aug 26 2003
%F A034968 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 A034968 From _Antti Karttunen_, Aug 29 2016: (Start)
%F A034968 a(0) = 0; for n >= 1, a(n) = A099563(n) + a(A257687(n)).
%F A034968 a(0) = 0; for n >= 1, a(n) = A060130(n) + a(A257684(n)).
%F A034968 Other identities. For all n >= 0:
%F A034968 a(n) = A001222(A276076(n)).
%F A034968 a(n) = A276146(A225901(n)).
%F A034968 a(A000142(n)) = 1, a(A007489(n)) = n, a(A033312(n+1)) = A000217(n).
%F A034968 a(A056019(n)) = a(n).
%F A034968 A219651(n) = n - a(n).
%F A034968 (End)
%e A034968 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 A034968 From _Joerg Arndt_, Jun 17 2011: (Start)
%e A034968 n: permutation inv. table a(n) cycles
%e A034968 0: [ 0 1 2 3 ] [ 0 0 0 ] 0 (0) (1) (2) (3)
%e A034968 1: [ 0 1 3 2 ] [ 0 0 1 ] 1 (0) (1) (2, 3)
%e A034968 2: [ 0 2 1 3 ] [ 0 1 0 ] 1 (0) (1, 2) (3)
%e A034968 3: [ 0 2 3 1 ] [ 0 1 1 ] 2 (0) (1, 2, 3)
%e A034968 4: [ 0 3 1 2 ] [ 0 2 0 ] 2 (0) (1, 3, 2)
%e A034968 5: [ 0 3 2 1 ] [ 0 2 1 ] 3 (0) (1, 3) (2)
%e A034968 6: [ 1 0 2 3 ] [ 1 0 0 ] 1 (0, 1) (2) (3)
%e A034968 7: [ 1 0 3 2 ] [ 1 0 1 ] 2 (0, 1) (2, 3)
%e A034968 8: [ 1 2 0 3 ] [ 1 1 0 ] 2 (0, 1, 2) (3)
%e A034968 9: [ 1 2 3 0 ] [ 1 1 1 ] 3 (0, 1, 2, 3)
%e A034968 10: [ 1 3 0 2 ] [ 1 2 0 ] 3 (0, 1, 3, 2)
%e A034968 11: [ 1 3 2 0 ] [ 1 2 1 ] 4 (0, 1, 3) (2)
%e A034968 12: [ 2 0 1 3 ] [ 2 0 0 ] 2 (0, 2, 1) (3)
%e A034968 13: [ 2 0 3 1 ] [ 2 0 1 ] 3 (0, 2, 3, 1)
%e A034968 14: [ 2 1 0 3 ] [ 2 1 0 ] 3 (0, 2) (1) (3)
%e A034968 15: [ 2 1 3 0 ] [ 2 1 1 ] 4 (0, 2, 3) (1)
%e A034968 16: [ 2 3 0 1 ] [ 2 2 0 ] 4 (0, 2) (1, 3)
%e A034968 17: [ 2 3 1 0 ] [ 2 2 1 ] 5 (0, 2, 1, 3)
%e A034968 18: [ 3 0 1 2 ] [ 3 0 0 ] 3 (0, 3, 2, 1)
%e A034968 19: [ 3 0 2 1 ] [ 3 0 1 ] 4 (0, 3, 1) (2)
%e A034968 20: [ 3 1 0 2 ] [ 3 1 0 ] 4 (0, 3, 2) (1)
%e A034968 21: [ 3 1 2 0 ] [ 3 1 1 ] 5 (0, 3) (1) (2)
%e A034968 22: [ 3 2 0 1 ] [ 3 2 0 ] 5 (0, 3, 1, 2)
%e A034968 23: [ 3 2 1 0 ] [ 3 2 1 ] 6 (0, 3) (1, 2)
%e A034968 (End)
%p A034968 [seq(convert(fac_base(j),`+`),j=0..119)]; # fac_base and PermRevLexUnrank given in A055089. Perm2InversionVector in A064039
%p A034968 Or alternatively: [seq(convert(Perm2InversionVector(PermRevLexUnrank(j)),`+`),j=0..119)];
%p A034968 # third Maple program:
%p A034968 b:= proc(n, i) local q;
%p A034968 `if`(n=0, 0, b(irem(n, i!, 'q'), i-1)+q)
%p A034968 end:
%p A034968 a:= proc(n) local k;
%p A034968 for k while k!<n do od; b(n, k)
%p A034968 end:
%p A034968 seq(a(n), n=0..200); # _Alois P. Heinz_, Nov 15 2012
%t A034968 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 A034968 (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 A034968 (Scheme)
%o A034968 (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 A034968 ;; _Antti Karttunen_, Aug 29 2016
%o A034968 (Python)
%o A034968 def a(n):
%o A034968 k=2
%o A034968 r=0
%o A034968 while n>0:
%o A034968 r+=n%k
%o A034968 n=n//k
%o A034968 k+=1
%o A034968 return r
%o A034968 print([a(n) for n in range(201)]) # _Indranil Ghosh_, Jun 19 2017, after PARI program
%o A034968 (Python)
%o A034968 def A034968(n, p=2): return n if n<p else A034968(n//p, p+1) + n%p
%o A034968 print([A034968(n) for n in range(106)]) # _Michael S. Branicky_, Oct 27 2024
%Y A034968 Cf. A368342 (partial sums), A001809 (sums of n! terms).
%Y A034968 Cf. A000142, A007489, A007623, A033312, A055091, A139365.
%Y A034968 Cf. A000217, A001222, A056019, A060130, A099563, A225901, A257684, A257687, A257694, A276076, A276146.
%Y A034968 Cf. A227148 (positions of even terms), A227149 (of odd terms).
%Y A034968 Cf. also A219650, A219651, A219666, A230423.
%Y A034968 Differs from analogous A276150 for the first time at n=24.
%Y A034968 Positions of records are A200748.
%K A034968 nonn
%O A034968 0,4
%A A034968 _Erich Friedman_
%E A034968 Additional comments from _Antti Karttunen_, Aug 23 2001