login
This site is supported by donations to The OEIS Foundation.

 

Logo


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.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 16 13:28 EDT 2017. Contains 290623 sequences.