This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 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 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: A031055 A249347 A284805 * A031056 A226293 A055117 Adjacent sequences:  A225657 A225658 A225659 * A225661 A225662 A225663 KEYWORD nonn,base AUTHOR Clark Kimberling, May 12 2013 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 17 15:15 EST 2018. Contains 317276 sequences. (Running on oeis4.)