cp's OEIS Frontend

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

%I A135547 #37 Jan 05 2025 19:51:38
%S A135547 1,1,2,1,2,4,10,1,6,10,4,24,6,298,1096,1,260,526,28,1098,16660,1540,
%T A135547 2050,2744,658,10246,4870,599338,566,8948416,34636834,1,4198408,
%U A135547 8421892,4195604,17043806,21256,3538972,67158052,35791946,26214476,8726292328,805355524,806094340,4296053112,4297066498,8388610,89479864
%N A135547 Number of cycles for vectors of length n under the Ducci map.
%C A135547 The number of different lengths of cycles is given by A111944 and the maximum length by A038553.
%C A135547 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.)
%C A135547 Remarkably, a(n) = A083843(n) for n=4, 7, 8, 14, 16, 23, 28, 31, 32. - _Max Alekseyev_, Oct 11 2013
%H A135547 Max Alekseyev, <a href="/A135547/b135547.txt">Table of n, a(n) for n = 1..420</a>
%H A135547 V. I. Arnold, <a href="http://dx.doi.org/10.1007/s11853-007-0001-0">Complexity of finite sequences of zeros and ones and geometry of finite spaces of functions</a>, Funct. Anal. Other. Math 1(1), 2006, pp. 1-15.
%H A135547 N. J. Calkin, J. G. Stevens, D. M. Thomas, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Papers1/43-1/paper43-1-7.pdf">A characterization for the lengths of cycles of the n-number Ducci game</a>, Fib. Q. 43(1), 2005, 53-59.
%o A135547 (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 */
%Y A135547 Cf. A038553, A111944
%K A135547 nonn
%O A135547 1,3
%A A135547 _N. J. A. Sloane_, Feb 24 2008
%E A135547 a(13)-a(19) from _R. J. Mathar_, Apr 17 2008
%E A135547 Terms a(20) onward added by _Max Alekseyev_, Oct 12 2013