|
|
A135547
|
|
Number of cycles for vectors of length n under the Ducci map.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|