A257694 -id:A257694 - cp's OEIS frontend

A034968 Minimal number of factorials that add to n.

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, 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, 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

Offset: 0

Erich Friedman

nonn

Equivalently, sum of digits when n is written in factorial base (A007623).
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
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.)

			a(205) = a(1!*1 + 3!*2 + 4!*3 + 5!*1) = 1+2+3+1 = 7. [corrected by Shin-Fu Tsai, Mar 23 2021]
From _Joerg Arndt_, Jun 17 2011: (Start)
   n:    permutation   inv. table a(n)  cycles
   0:    [ 0 1 2 3 ]   [ 0 0 0 ]   0    (0) (1) (2) (3)
   1:    [ 0 1 3 2 ]   [ 0 0 1 ]   1    (0) (1) (2, 3)
   2:    [ 0 2 1 3 ]   [ 0 1 0 ]   1    (0) (1, 2) (3)
   3:    [ 0 2 3 1 ]   [ 0 1 1 ]   2    (0) (1, 2, 3)
   4:    [ 0 3 1 2 ]   [ 0 2 0 ]   2    (0) (1, 3, 2)
   5:    [ 0 3 2 1 ]   [ 0 2 1 ]   3    (0) (1, 3) (2)
   6:    [ 1 0 2 3 ]   [ 1 0 0 ]   1    (0, 1) (2) (3)
   7:    [ 1 0 3 2 ]   [ 1 0 1 ]   2    (0, 1) (2, 3)
   8:    [ 1 2 0 3 ]   [ 1 1 0 ]   2    (0, 1, 2) (3)
   9:    [ 1 2 3 0 ]   [ 1 1 1 ]   3    (0, 1, 2, 3)
  10:    [ 1 3 0 2 ]   [ 1 2 0 ]   3    (0, 1, 3, 2)
  11:    [ 1 3 2 0 ]   [ 1 2 1 ]   4    (0, 1, 3) (2)
  12:    [ 2 0 1 3 ]   [ 2 0 0 ]   2    (0, 2, 1) (3)
  13:    [ 2 0 3 1 ]   [ 2 0 1 ]   3    (0, 2, 3, 1)
  14:    [ 2 1 0 3 ]   [ 2 1 0 ]   3    (0, 2) (1) (3)
  15:    [ 2 1 3 0 ]   [ 2 1 1 ]   4    (0, 2, 3) (1)
  16:    [ 2 3 0 1 ]   [ 2 2 0 ]   4    (0, 2) (1, 3)
  17:    [ 2 3 1 0 ]   [ 2 2 1 ]   5    (0, 2, 1, 3)
  18:    [ 3 0 1 2 ]   [ 3 0 0 ]   3    (0, 3, 2, 1)
  19:    [ 3 0 2 1 ]   [ 3 0 1 ]   4    (0, 3, 1) (2)
  20:    [ 3 1 0 2 ]   [ 3 1 0 ]   4    (0, 3, 2) (1)
  21:    [ 3 1 2 0 ]   [ 3 1 1 ]   5    (0, 3) (1) (2)
  22:    [ 3 2 0 1 ]   [ 3 2 0 ]   5    (0, 3, 1, 2)
  23:    [ 3 2 1 0 ]   [ 3 2 1 ]   6    (0, 3) (1, 2)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000
F. T. Adams-Watters and F. Ruskey, Generating Functions for the Digital Sum and Other Digit Counting Sequences, JIS 12 (2009) 09.5.6.
Joerg Arndt, Matters Computational (The Fxtbook), fig.10-1.B on p.234.
Tyler Ball, Joanne Beckford, Paul Dalenberg, Tom Edgar, and Tina Rajabi, Some Combinatorics of Factorial Base Representations, J. Int. Seq., Vol. 23 (2020), Article 20.3.3.
FindStat - Combinatorial Statistic Finder, The number of inversions of a permutation
Index entries for sequences related to factorial base representation

Cf. A368342 (partial sums), A001809 (sums of n! terms).
Cf. A000142, A007489, A007623, A033312, A055091, A139365.
Cf. A000217, A001222, A056019, A060130, A099563, A225901, A257684, A257687, A257694, A276076, A276146.
Cf. A227148 (positions of even terms), A227149 (of odd terms).
Cf. also A219650, A219651, A219666, A230423.
Differs from analogous A276150 for the first time at n=24.
Positions of records are A200748.

[seq(convert(fac_base(j),`+`),j=0..119)]; # fac_base and PermRevLexUnrank given in A055089. Perm2InversionVector in A064039
Or alternatively: [seq(convert(Perm2InversionVector(PermRevLexUnrank(j)),`+`),j=0..119)];
# third Maple program:
b:= proc(n, i) local q;
      `if`(n=0, 0, b(irem(n, i!, 'q'), i-1)+q)
    end:
a:= proc(n) local k;
      for k while k!Alois P. Heinz, Nov 15 2012

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 *)

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

def a(n):
    k=2
    r=0
    while n>0:
        r+=n%k
        n=n//k
        k+=1
    return r
print([a(n) for n in range(201)]) # Indranil Ghosh, Jun 19 2017, after PARI program

def A034968(n, p=2): return n if nA034968(n//p, p+1) + n%p
print([A034968(n) for n in range(106)]) # Michael S. Branicky, Oct 27 2024

(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)))))))
;; Antti Karttunen, Aug 29 2016

a(n) = n - Sum_{i>=2} (i-1)*floor(n/i!). - Benoit Cloitre, Aug 26 2003
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
From Antti Karttunen, Aug 29 2016: (Start)
a(0) = 0; for n >= 1, a(n) = A099563(n) + a(A257687(n)).
a(0) = 0; for n >= 1, a(n) = A060130(n) + a(A257684(n)).
Other identities. For all n >= 0:
a(n) = A001222(A276076(n)).
a(n) = A276146(A225901(n)).
a(A000142(n)) = 1, a(A007489(n)) = n, a(A033312(n+1)) = A000217(n).
a(A056019(n)) = a(n).
A219651(n) = n - a(n).
(End)

Additional comments from Antti Karttunen, Aug 23 2001

A060130 Number of nonzero digits in factorial base representation (A007623) of n; minimum number of transpositions needed to compose each permutation in the lists A060117 & A060118.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Mar 02 2001

nonn

			19 = 3*(3!) + 0*(2!) + 1*(1!), thus it is written as "301" in factorial base (A007623). The count of nonzero digits in that representation is 2, so a(19) = 2.

Antti Karttunen, Table of n, a(n) for n = 0..40320
Index entries for sequences related to factorial base representation

Cf. A007623, A034968, A055091, A060117, A060118, A060128, A060129, A060131, A060502, A257687, A275734, A275735, A276076.
Cf. A227130 (positions of even terms), A227132 (of odd terms).
Cf. also A225901, A232094, A257694, A257695.
The topmost row and the leftmost column in array A230415, the left edge of triangle A230417.
Differs from similar A267263 for the first time at n=30.

A060130(n) = count_nonfixed(convert(PermUnrank3R(n), 'disjcyc'))-nops(convert(PermUnrank3R(n), 'disjcyc')) or nops(fac_base(n))-nops(positions(0, fac_base(n)))
fac_base := n -> fac_base_aux(n, 2); fac_base_aux := proc(n, i) if(0 = n) then RETURN([]); else RETURN([op(fac_base_aux(floor(n/i), i+1)), (n mod i)]); fi; end;
count_nonfixed := l -> convert(map(nops, l), `+`);
positions := proc(e, ll) local a, k, l, m; l := ll; m := 1; a := []; while(member(e, l[m..nops(l)], 'k')) do a := [op(a), (k+m-1)]; m := k+m; od; RETURN(a); end;
# For procedure PermUnrank3R see A060117

Block[{nn = 105, r}, r = MixedRadix[Reverse@ Range[2, -1 + SelectFirst[Range@ 12, #! > nn &]]]; Array[Count[IntegerDigits[#, r], k_ /; k > 0] &, nn, 0]] (* Michael De Vlieger, Dec 30 2017 *)

(define (A060130 n) (let loop ((n n) (i 2) (s 0)) (cond ((zero? n) s) (else (loop (quotient n i) (+ 1 i) (+ s (if (zero? (remainder n i)) 0 1)))))))
;; Two other implementations, that use memoization-macro definec:
(definec (A060130 n) (if (zero? n) n (+ 1 (A060130 (A257687 n)))))
(definec (A060130 n) (if (zero? n) n (+ (A257511 n) (A060130 (A257684 n)))))
;; Antti Karttunen, Dec 30 2017

a(0) = 0; for n > 0, a(n) = 1 + a(A257687(n)).
a(0) = 0; for n > 0, a(n) = A257511(n) + a(A257684(n)).
a(n) = A060129(n) - A060128(n).
a(n) = A084558(n) - A257510(n).
a(n) = A275946(n) + A275962(n).
a(n) = A275948(n) + A275964(n).
a(n) = A055091(A060119(n)).
a(n) = A069010(A277012(n)) = A000120(A275727(n)).
a(n) = A001221(A275733(n)) = A001222(A275733(n)).
a(n) = A001222(A275734(n)) = A001222(A275735(n)) = A001221(A276076(n)).
a(n) = A046660(A275725(n)).
a(A225901(n)) = a(n).
A257511(n) <= a(n) <= A034968(n).
A275806(n) <= a(n).
a(A275804(n)) = A060502(A275804(n)). [A275804 gives all the positions where this coincides with A060502.]
a(A276091(n)) = A260736(A276091(n)). [A276091 gives all the positions where this coincides with A260736.]

Example-section added, name edited, the old Maple-code moved away from the formula-section, and replaced with all the new formulas by Antti Karttunen, Dec 30 2017

A257684 Discard the rightmost digit from the factorial base representation of n and subtract one from all remaining nonzero digits, then convert back to decimal.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, May 04 2015

In other words, subtract one from all nonzero digits in the factorial base representation (A007623) of n and shift it one step right (i.e., delete the rightmost zero), then convert back to decimal.

			For 4, whose factorial base representation is "20" (as 4 = 2*2! + 0*1!), when we discard the rightmost zero, and subtract 1 from 2, we get "1", thus a(4) = 1.
For 18, whose factorial base representation is "300" (as 18 = 3*3! + 0*2! + 0*1!), when we discard the rightmost zero, and subtract 1 from 3, we get "20", thus a(18) = 4.

Antti Karttunen, Table of n, a(n) for n = 0..10080

Positions of zeros: A059590.
Cf. A007623, A255411, A257685, A257687.
Can be used to define simple recurrences for sequences like A034968, A246359, A257679, A257694, A257695 and A257696.

nn = 95; m = 1; While[Factorial@ m < nn, m++]; m; Map[FromDigits[#, MixedRadix[Reverse@ Range[2, m]]] &[If[# == 0, 0, # - 1] & /@ Most@ IntegerDigits[#, MixedRadix[Reverse@ Range[2, m]]]] &, Range[0, nn]] (* Michael De Vlieger, Aug 11 2016, Version 10.2 *)

from sympy import factorial as f
def a007623(n, p=2):
    return n if n0 else '0' for i in x)[::-1]
    return 0 if n==1 else sum(int(y[i])*f(i + 1) for i in range(len(y)))
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 19 2017

(define (A257684 n) (let loop ((n n) (z 0) (i 2) (f 0)) (cond ((zero? n) z) (else (let ((d (remainder n i))) (loop (quotient n i) (+ z (* f (- d (if (zero? d) 0 1)))) (+ 1 i) (if (zero? f) 1 (* f (- i 1)))))))))

For all n >= 0, a(A255411(n)) = n. [This sequence works as a left inverse of A255411. See A257685 for a "cleaned up" version.]

A278236 Filter-sequence for factorial base (digit values): least number with the same prime signature as A276076(n).

Original entry on oeis.org

1, 2, 2, 6, 4, 12, 2, 6, 6, 30, 12, 60, 4, 12, 12, 60, 36, 180, 8, 24, 24, 120, 72, 360, 2, 6, 6, 30, 12, 60, 6, 30, 30, 210, 60, 420, 12, 60, 60, 420, 180, 1260, 24, 120, 120, 840, 360, 2520, 4, 12, 12, 60, 36, 180, 12, 60, 60, 420, 180, 1260, 36, 180, 180, 1260, 900, 6300, 72, 360, 360, 2520, 1800, 12600, 8, 24, 24, 120, 72, 360, 24, 120, 120, 840, 360, 2520

Offset: 0

Antti Karttunen, Nov 16 2016

This sequence can be used for filtering certain factorial base related sequences, because it matches only with any such sequence b that can be computed as b(n) = f(A276076(n)), where f(n) is any function that depends only on the prime signature of n (some of these are listed under the index entry for "sequences computed from exponents in ...").
Matching in this context means that the sequence a matches with the sequence b iff for all i, j: a(i) = a(j) => b(i) = b(j). In other words, iff the sequence b partitions the natural numbers to the same or coarser equivalence classes (as/than the sequence a) by the distinct values it obtains.
Any such sequence should match where the result is computed from the nonzero digits (that may also be > 9) in the factorial base representation of n, but does not depend on their order. Some of these are listed on the last line of the Crossrefs section.
Note that as A275735 is present in that list it means that the sequences matching to its filter-sequence A278235 form a subset of the sequences matching to this sequence. Also, for A275735 there is a stronger condition that for any i, j: a(i) = a(j) <=> A275735(i) = A275735(j), which if true, would imply that there is an injective function f such that f(A275735(n)) = A278236(n), and indeed, this function seems to be A181821.

Cf. A007623, A046523, A181821, A276076.
Similar sequences: A278222 (base-2 related), A069877 (base-10), A278226 (primorial base), A278225, A278234, A278235 (other variants for factorial base),
Differs from A278226 for the first time at n=24, where a(24)=2, while A278226(24)=16.
Sequences that partition N into same or coarser equivalence classes: A275735 (<=>), A034968, A060130, A227153, A227154, A246359, A257079, A257511, A257679, A257694, A257695, A257696, A264990, A275729, A275806, A275948, A275964, A278235.

a[n_] := Module[{k = n, m = 2, r, s = {}}, While[{k, r} = QuotientRemainder[k, m]; k != 0|| r != 0, AppendTo[s, r]; m++]; s = ReverseSort[s]; Times @@ (Prime[Range[Length[s]]] ^ s)]; Array[a, 100, 0] (* Amiram Eldar, Feb 07 2024 *)

(define (A278236 n) (A046523 (A276076 n)))

a(n) = A046523(A276076(n)).

a(n) = A181821(A275735(n)). [Empirical formula found with the help of equivalence class matching. Not yet proved.]

cp's OEIS Frontend

A034968 Minimal number of factorials that add to n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Scheme

Formula

Extensions

A060130 Number of nonzero digits in factorial base representation (A007623) of n; minimum number of transpositions needed to compose each permutation in the lists A060117 & A060118.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Scheme

Formula

Extensions

A257684 Discard the rightmost digit from the factorial base representation of n and subtract one from all remaining nonzero digits, then convert back to decimal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A278236 Filter-sequence for factorial base (digit values): least number with the same prime signature as A276076(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A257695 a(0) = 1; for n >= 1, a(n) = lcm(A060130(n), a(A257684(n))).

Views

Author

Keywords

Links

Crossrefs

Formula

A257696 a(0) = 0; for n >= 1, a(n) = gcd(A060130(n), a(A257684(n))).

Views

Author

Keywords

Links

Crossrefs

Formula