login
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
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 count-sequences, look-and-say sequences, and noun-and-adjective 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(q-1)) 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^(m-3)1 -> m-1,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^(m-2) 1 -> m-1 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^p-1 1 0^(q-p-1) 1 -> q-1,2, and Lemma 2 applies; second, if 2 < p = q, then pp -> 0^p 2 -> p01 -> 110(p-2)1 -> p-2 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
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: A031055 A249347 A284805 * A031056 A226293 A055117
KEYWORD
nonn,base
AUTHOR
Clark Kimberling, May 12 2013
STATUS
approved