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

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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.

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.

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: A024739 A024959 A029728 * A146307 A063894 A024500

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

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

Content is available under The OEIS End-User License Agreement .

Last modified April 19 08:09 EDT 2014. Contains 240739 sequences.