

A225660


Number of nonrepeating vectors in a counting procedure that starts with the digits of (n base 2).


8



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



OFFSET

0,1


COMMENTS

An iterative counting procedure, defined below, is applied to the vector consisting of the binary digits of n. The result is a sequence of vectors, of which the first a(n) are distinct and the rest repeat with period 6.
The basic idea of the procedure is to record the frequencies, or counts, of each of the numbers in S, and then to iterate such counting. There are various well known procedures for countsequences, lookandsay sequences, and nounandadjective sequences, but the following procedure seems to be less well known.
Suppose that S = (x(1),..,x(h)) is a vector of nonnegative integers. Let m = max(S) and F(S) = (f(0),..,f(m)), where f(i) is the number of occurrences of i in S. Define H(0) = S, H(1) = F(S), and H(q) = H(H(q1)) for q>=2.
Theorem 1: The sequence H(q) is eventually periodic with period 6. (Proof below.) We shall abbreviate "is eventually periodic with period p" as "has per(p)", meaning that there are numbers i and p such that H(i + p) = H(p). (Theorem 2 is stated at A225869.)
Example: S = (2,2). The vectors H(q) are determined successively:
22 > 002 > 201 > 111 > 03 > 1001 > 22, which shows that H(6) = F(0), so that S has per(6). (This example is a basis to A225869.)
A proof of Theorem 1 uses three lemmas:
Lemma 1. If m>=0 and S = (m,2), then S has per(6). Proof: For m = 0, we have 00 > 2 > 001 > 21 > 011 > 12 > 011, so that (0,0) has per(2), hence per(6). It is easy to check that (m,2) has per(6) for m in {2,3,4}. Assume that m > 4. Then m2 > 0010^(m3)1 > m1,2, so that by induction, S has per(6).
Lemma 2. If m>=0 and S = (m), then S has per(6). Proof: It is easy to verify this for m in {0,1,2}. If m > 2, then m > 0^m 1 > m1 > 010^(m2) 1 > m1 2, so that S has per(6) by Lemma 1.
Lemma 3. If p >= and q >=0, then (p,q) has per(6). Proof: Assume without loss that p<=q. If p is in {0,1,2}, the assertion clearly holds, leaving two cases: first, if 2 < p < q, then pq > 0^p1 1 0^(qp1) 1 > q1,2, and Lemma 2 applies; second, if 2 < p = q, then pp > 0^p 2 > p01 > 110(p2)1 > p2 3, as in the first case.
Proof of Theorem 1: Throughout, it suffices to show that F(S) or F(F(S)) has per(6). The basic idea is induction on the number m = max(S). First, suppose that m = 0. Then S consists of k 0's for some k, so that F(S) = (k), and by Lemma 2, F(S) has per(6). Next, if m = 1, then S consists of p 0's and q 1's for some p >= 0 and q > 0. If p = 0, then F(S) = (q), so that F(S) has per(6) by Lemma 2; if p>0, then F(S) = (p,q), so that F(S) has per(6) by Lemma 3. Next, if m = 2, there are several cases, for which we note that each case easily reduces by applications of F to a vector covered by the lemmas.
Now for the main induction, assume that if R is a vector with maximal term u < m then R is per(6), and suppose that S is a vector for which m>=2. For i = 0..m, let f(i) be the frequency of i in S. Then F(S) = (f(0),...f(m)). Let (y(1),...,y(k)) be the vector of distinct elements, in increasing order, of F(S), and let g(i) be the frequency of y(i) in F(S), so that F(F(S)) = (g(1),...,g(k)). Since g(1) + ... + g(k) = m+1, F(F(S)) is a partition of m+1. Let M = max(F(F(S)). If M < m, then by induction, F(F(S)) has per(6). If M = m, then F(F(S)) = (1,m), and by Lemma 3, F(F(S)) has per(6). The only remaining case is M = m+1, for which F(F(S)) = (m+1), and by Lemma 2, F(F(S)) has per(6).
Conjecture: if n>9, then a(n) is odd.


LINKS

Clark Kimberling, Table of n, a(n) for n = 0..10000


EXAMPLE

To see that a(0) = 6, write 0 > 1 > 01 > 11 > 02 > 101 > 12 > 011 > 12, so that the 6 nonrepeating vectors are (0), (1), (0,1), (1,1), (0,2), (0,1,1). After (0,1,1) the cycle (1,2) > (0,1) has length 2, so that the remainder of the sequence of vectors is periodic with period 2, hence also period 6.


MATHEMATICA

Clear[a, t]; Flatten[Table[a = {t = IntegerDigits[n, 2]}; While[Count[a, t] =!= 2, AppendTo[a, t = BinCounts[t, {0, Max[t] + 1, 1}]]]; First[Position[a, Last[a]]]  1, {n, 0, 180}]] (* Peter J. C. Moses, May 09 2013 *)


CROSSREFS

Cf. A225661 (base 3), A225664 (base 10), A225665 (base 16), A225869.
Sequence in context: A023448 A031055 A249347 * A031056 A226293 A055117
Adjacent sequences: A225657 A225658 A225659 * A225661 A225662 A225663


KEYWORD

nonn,base


AUTHOR

Clark Kimberling, May 12 2013


STATUS

approved



