

A060502


a(n) = number of occupied digit slopes in the factorial base representation of n (see comments for the definition); number of drops in the nth permutation of list A060117.


23



0, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 3, 2, 2, 2, 3, 3, 4, 3, 3, 2, 3, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 2, 3, 3, 2, 2, 1, 2, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

From Antti Karttunen, Aug 1124 2016: (Start)
a(n) gives the number of occupied "digit slopes" in the factorial base representation of n, or more formally, the number of distinct elements in a multiset [(i_x  d_x)  where d_x ranges over each nonzero digit present in factorial base representation of n and i_x is that digit's position from the right]. Here onebased indexing is used, thus the least significant digit is in position 1. Each value {digit's position}  {digit's value} determines on which slope that particular nonzero digit is. The nonzero digits for which (position  digit) = 0, are said to be on the "maximal slope" (see A260736), those with value 1 on "submaximal", etc.
The number of occupied digit slopes translates directly to the number of drops in the nth permutation as given in the list A060117 because only the largest (and thus leftmost) of all nonzero digits on any particular slope adds a (single) drop to the permutation, when constructed by the unranking algorithm employed in A060117.
The original definition of this sequence is (essentially):
a(n) = the average of digits (where "digits" may eventually obtain also any values > 9) in each siteswap pattern A060498(n) constructed from each permutation in list A060117, which is equal to number of balls used in that pattern.
The equivalence of the old and the new definitions is seen from the following (as kindly pointed by Olivier Gérard in personal mail): For any permutation p of [1..n], Sum(i=1..n) p(i)i = 0 (whether taken modulo n or not), thus Sum(i=1..n) (p(i)i modulo n) = Sum(i={set of nondrops}) (p(i)i) + Sum(i={set of drops}) (n + (p(i)i)) = 0 + n * #{set of drops}, where drops is the set of those i where p[i] < i and nondrops are those i for which p[i] >= 1.
Involution A225901 maps this metric to another metric A275806 which gives the number of distinct nonzero digits in factorial base representation of n. See also A275811.
A007489 (repunits in this context) gives the positions where a(n) = A084558(n) (the length of factorial base representation of n). These are also the positions of records.
(End)


LINKS

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


FORMULA

From Antti Karttunen, Aug 1121 2016: (Start)
The following formula reflects the original definition of computing the average, with a few unnecessary steps eliminated:
a(n) = 1/s * Sum_{i=1..s} ((p[i]i) modulo s), where p is the permutation of rank n as ordered in the list A060117, and s is its size (the number of its elements) computed as s = 1+A084558(n).
a(n) = Sum_{i=1..s} [p[i]<i]. [This is equal to the number of drops in permutation p (see comments).]
a(n) = 1/s * Sum_{i=1..s} ((ip[i]) modulo s). [If inverse permutations from list A060118 are used, then we just flip the order of difference that is used in the first formula].
Following formulas do not need intermediate construction of permutation lists:
a(n) = A001221(A275734(n)).
a(n) = A275806(A225901(n)).
a(n) = A000120(A276010(n)).
Other identities and observations. For all n >= 0:
a(n) = A275946(n) + A275947(n).
a(n) = A060500(A060125(n)).
a(n) = A060128(n) + A276004(n).
a(n) = A060129(n)  A060500(n).
a(n) = A084558(n)  A275849(n) = 1 + A084558(n)  A060501(n).
a(A007489(n)) = n. [Particularly, A007489(n) gives the position of the first occurrence of each n.]
A060128(n) <= a(n) <= A060129(n).
a(n!) = 1.
a(A033312(n)) = 1 for all n > 1.
a(A059590(n)) = A000120(n).
a(A060112(n)) = A007895(n).
a(n) = a(A153880(n)) = a(A255411(n)). [The shiftoperations do not change the number of distinct slopes.]
a(A275804(n)) = A060130(A275804(n)). [A275804 gives all the positions where this coincides with A060130.]
(End)


EXAMPLE

For n=23 ("321" in factorial base representation, A007623), all the digits are maximal for their positions (they occur on the "maximal slope"), thus there is only one distinct digit slope present and a(23)=1. Also, for the 23rd permutation in the ordering A060117, [2341], there is just one drop, as p[4] = 1 < 4.
For n=29 ("1021"), there are three nonzero digits, where both 2 and the rightmost 1 are on the maximal slope, while the most significant 1 is on the "subsubsubmaximal", thus there are two occupied slopes in total, and a(29) = 2. In the 29th permutation of A060117, [23154], there are two drops as p[3] = 1 < 3 and p[5] = 4 < 5.
For n=37 ("1201"), there are three nonzero digits, where the rightmost 1 is on the maximal slope, 2 is on the submaximal, and the most significant 1 is on the "subsubsubmaximal", thus there are three occupied slopes in total, and a(37) = 3. In the 37th permutation of A060117, [51324], there are three drops at indices 2, 4 and 5.


MAPLE

# The following program follows the original 2001 interpretation of this sequence:
A060502 := n > avg(Perm2SiteSwap3(PermUnrank3R(n)));
with(group);
permul := (a, b) > mulperms(b, a);
# factorial_base(n) gives the digits of A007623(n) as a list, uncorrupted even when there are digits > 9:
factorial_base := proc(nn) local n, a, d, j, f; n := nn; if(0 = n) then RETURN([0]); fi; a := []; f := 1; j := 2; while(n > 0) do d := floor(`mod`(n, (j*f))/f); a := [d, op(a)]; n := n  (d*f); f := j*f; j := j+1; od; RETURN(a); end;
# PermUnrank3R(r) gives the permutation with rank r in list A060117:
PermUnrank3R := proc(r) local n; n := nops(factorial_base(r)); convert(PermUnrank3Raux(n+1, r, []), 'permlist', 1+(((r+2) mod (r+1))*n)); end;
PermUnrank3Raux := proc(n, r, p) local s; if(0 = r) then RETURN(p); else s := floor(r/((n1)!)); RETURN(PermUnrank3Raux(n1, r(s*((n1)!)), permul(p, [[n, ns]]))); fi; end;
Perm2SiteSwap3 := proc(p) local ip, n, i, a; n := nops(p); ip := convert(invperm(convert(p, 'disjcyc')), 'permlist', n); a := []; for i from 1 to n do if(0 = ((ip[i]i) mod n)) then a := [op(a), 0]; else a := [op(a), n((ip[i]i) mod n)]; fi; od; RETURN(a); end;
avg := a > (convert(a, `+`)/nops(a));


PROG

(Scheme, different versions)
(define (A060502 n) (A001221 (A275734 n)))
(define (A060502 n) (A275806 (A225901 n)))
;; This version follows the original definition (where we count the average of siteswap"digits", that is, the number of balls. A few unnecessary twists of the original Mapleprograms have been optimized away:
(define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060118permvecshort n))) (let loop ((a 0) (i 1)) (if (> i s) (/ a s) (loop (+ a (modulo ( i (vectorref p ( i 1))) s)) (+ 1 i))))))
(define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060117permvecshort n))) (let loop ((a 0) (i 1)) (if (> i s) (/ a s) (loop (+ a (modulo ( (vectorref p ( i 1)) i) s)) (+ 1 i))))))
;; By the proof given in comments, that average is equal to the number of drops in permutations obtained from list A060117:
(define (A060502 n) (let ((s (+ 1 (A084558 n))) (p (A060117permvecshort n))) (let loop ((d 0) (i 1)) (if (> i s) d (loop (+ d (if (< (vectorref p ( i 1)) i) 1 0)) (+ 1 i))))))
(define (A060117permvecshort rank) (permvec1inverseof (permuteA060118 (makeinitializedvector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank)))
(define (permvec1inverseof permvec) (makeinitializedvector (vectorlength permvec) (lambda (i) (permvec1findposofifrom (+ 1 i) permvec))))
(define (permvec1findposofifrom i permvec) (let loop ((k 0)) (cond ((= k (vectorlength permvec)) #f) ((= i (vectorref permvec k)) (+ 1 k)) (else (loop (+ k 1))))))
(define (A060118permvecshort rank) (permuteA060118 (makeinitializedvector (+ 1 (A084558 rank)) 1+) (+ 1 (A084558 rank)) rank))
(define (permuteA060118 elems size permrank) (let ((p (vectorhead elems size))) (let unrankA060118 ((r permrank) (i 1)) (cond ((zero? r) p) (else (let* ((j (1+ i)) (m (modulo r j))) (cond ((not (zero? m)) (let ((orgi (vectorref p i))) (vectorset! p i (vectorref p ( i m))) (vectorset! p ( i m) orgi)))) (unrankA060118 (/ ( r m) j) j)))))))


CROSSREFS

Cf. A000120, A001221, A007489, A007623, A033312, A060117, A060118, A060130, A060498, A225901, A275734, A275806.
Cf. A007489 (positions of records, the first occurrence of each n).
Cf. A276001, A276002, A276003 (positions where a(n) obtains values 1, 2, 3).
Cf. also A060500, A060501, A060125, A084558, A153880, A255411, A260736, A273670, A275804, A275811, A275946, A275947, A275849, A275956, A276004,
A276005, A276010.
Sequence in context: A029386 A277325 A240837 * A035439 A059111 A103502
Adjacent sequences: A060499 A060500 A060501 * A060503 A060504 A060505


KEYWORD

nonn,base


AUTHOR

Antti Karttunen, Mar 22 2001


EXTENSIONS

Entry revised, with a new interpretation and formulas. Maplecode cleaned up.  Antti Karttunen, Aug 11 2016
Another new interpretation added and the original definition moved to the comments  Antti Karttunen, Aug 24 2016


STATUS

approved



