A060130 - OEIS

%I #38 Dec 30 2017 10:01:10

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

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

%U 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

%N 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.

%H Antti Karttunen, <a href="/A060130/b060130.txt">Table of n, a(n) for n = 0..40320</a>

%H <a href="/index/Fa#facbase">Index entries for sequences related to factorial base representation</a>

%F a(0) = 0; for n > 0, a(n) = 1 + a(A257687(n)).

%F a(0) = 0; for n > 0, a(n) = A257511(n) + a(A257684(n)).

%F a(n) = A060129(n) - A060128(n).

%F a(n) = A084558(n) - A257510(n).

%F a(n) = A275946(n) + A275962(n).

%F a(n) = A275948(n) + A275964(n).

%F a(n) = A055091(A060119(n)).

%F a(n) = A069010(A277012(n)) = A000120(A275727(n)).

%F a(n) = A001221(A275733(n)) = A001222(A275733(n)).

%F a(n) = A001222(A275734(n)) = A001222(A275735(n)) = A001221(A276076(n)).

%F a(n) = A046660(A275725(n)).

%F a(A225901(n)) = a(n).

%F A257511(n) <= a(n) <= A034968(n).

%F A275806(n) <= a(n).

%F a(A275804(n)) = A060502(A275804(n)). [A275804 gives all the positions where this coincides with A060502.]

%F a(A276091(n)) = A260736(A276091(n)). [A276091 gives all the positions where this coincides with A260736.]

%e 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.

%p A060130(n) = count_nonfixed(convert(PermUnrank3R(n), 'disjcyc'))-nops(convert(PermUnrank3R(n), 'disjcyc')) or nops(fac_base(n))-nops(positions(0, fac_base(n)))

%p 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;

%p count_nonfixed := l -> convert(map(nops, l), `+`);

%p 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;

%p # For procedure PermUnrank3R see A060117

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

%o (Scheme)

%o (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)))))))

%o ;; Two other implementations, that use memoization-macro definec:

%o (definec (A060130 n) (if (zero? n) n (+ 1 (A060130 (A257687 n)))))

%o (definec (A060130 n) (if (zero? n) n (+ (A257511 n) (A060130 (A257684 n)))))

%o ;; _Antti Karttunen_, Dec 30 2017

%Y Cf. A007623, A034968, A055091, A060117, A060118, A060128, A060129, A060131, A060502, A257687, A275734, A275735, A276076.

%Y Cf. A227130 (positions of even terms), A227132 (of odd terms).

%Y Cf. also A225901, A232094, A257694, A257695.

%Y The topmost row and the leftmost column in array A230415, the left edge of triangle A230417.

%Y Differs from similar A267263 for the first time at n=30.

%K nonn

%O 0,4

%A _Antti Karttunen_, Mar 02 2001

%E 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