A135547 Number of cycles for vectors of length n under the Ducci map.

1, 1, 2, 1, 2, 4, 10, 1, 6, 10, 4, 24, 6, 298, 1096, 1, 260, 526, 28, 1098, 16660, 1540, 2050, 2744, 658, 10246, 4870, 599338, 566, 8948416, 34636834, 1, 4198408, 8421892, 4195604, 17043806, 21256, 3538972, 67158052, 35791946, 26214476, 8726292328, 805355524, 806094340, 4296053112, 4297066498, 8388610, 89479864

Offset

1,3

Comments

The number of different lengths of cycles is given by A111944 and the maximum length by A038553.

Also, the number of connected components in Arnold's graph G_n associated with the Ducci map. G_n has 2^n vertices, one for each binary vector x. Each node x has a single directed edge which goes from x to y, where y_1 = x_2-x_1, y_2 = x_3-x_2, ..., y_{n-1} = x_n-x_{n-1}, y_n = x_1-x_n. (Since the vectors are binary, we could use here sums instead of differences.)

Remarkably, a(n) = A083843(n) for n=4, 7, 8, 14, 16, 23, 28, 31, 32. - Max Alekseyev, Oct 11 2013

Links

Max Alekseyev, Table of n, a(n) for n = 1..420

V. I. Arnold, Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions, Funct. Anal. Other. Math 1(1), 2006, pp. 1-15.

N. J. Calkin, J. G. Stevens, D. M. Thomas, A characterization for the lengths of cycles of the n-number Ducci game, Fib. Q. 43(1), 2005, 53-59.

Prog

(C++) #include <iostream> #include <set> #include <vector> using namespace std ; int inComp( const vector< set<unsigned> > & comps, const int n) { for(int i=0; i < comps.size() ; i++) if ( comps[i].find(n) != comps[i].end() ) return i; return -1 ; } int firstd(const unsigned i, const int len, const unsigned allbu1, const unsigned hibit) { unsigned d= i ^ (i>>1) ; if ( (i&1) != (i & hibit) >> (len-1) ) d |= hibit ; else d &= allbu1 ; return d ; } int main(int argc, char*argv[]) { for(int n=1;; n++) { vector< set<unsigned> > comps ; unsigned allbu1 = 0 ; for(int i=0 ; i < n-1 ; i++) allbu1 |= (1 << i) ; const unsigned hibit = 1 <<(n-1) ; for(int i=0; i < 1<<n; i++) { set<unsigned> trac ; for(int ider=i;; ) { int c ; if ( ( c=inComp(comps, ider) ) != -1) { comps[c].insert(ider) ; for(set<unsigned>::const_iterator j=trac.begin() ; j != trac.end() ; j++) comps[c].insert(*j) ; break ; } else if ( trac.find(ider) != trac.end() ) { comps.push_back(trac) ; break ; } else trac.insert(ider) ; ider= firstd(ider, n, allbu1, hibit) ; } } cout << n << " " << comps.size() <<endl ; } } /* R. J. Mathar, Apr 17 2008 */

Crossrefs

Cf. A038553, A111944

Sequence in context: A024959 A029728 A376989 * A146307 A343952 A063894

Adjacent sequences: A135544 A135545 A135546 * A135548 A135549 A135550

Keyword

nonn

Author

N. J. A. Sloane, Feb 24 2008

Extensions

a(13)-a(19) from R. J. Mathar, Apr 17 2008

Terms a(20) onward added by Max Alekseyev, Oct 12 2013

Status

approved