A111944 -id:A111944 - cp's OEIS frontend

A038553 Maximum cycle length in differentiation digraph for n-bit binary sequences.

1, 1, 3, 1, 15, 6, 7, 1, 63, 30, 341, 12, 819, 14, 15, 1, 255, 126, 9709, 60, 63, 682, 2047, 24, 25575, 1638, 13797, 28, 475107, 30, 31, 1, 1023, 510, 4095, 252, 3233097, 19418, 4095, 120, 41943, 126, 5461, 1364, 4095, 4094, 8388607, 48, 2097151, 51150, 255, 3276, 3556769739, 27594, 1048575

Offset: 1

N. J. A. Sloane

nonn

Length of longest cycle for vectors of length n under the Ducci map.
Also, the period of polynomial (x+1)^n+1 over GF(2) (cf. A046932). - Max Alekseyev, Oct 12 2013
Per the comment by T. D. Noe originally given in A138006, it appears that for an odd n > 1, a(n) <= n*(2^((n-1)/2)-1). - Max Alekseyev, Jul 10 2025

Simmons, G. J., The structure of the differentiation digraphs of binary sequences. Ars Combin. 35 (1993), A, 71-88. Math. Rev. 95f:05052.

Max Alekseyev, Table of n, a(n) for n = 1..2458
Florian Breuer, Igor E. Shparlinski, Lower bounds for periods of Ducci sequences, arXiv:1909.04462 [math.NT], 2019.
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 (No. 1, 2005), 53-59.
O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, Funct. Anal. Other Math. 1 (2006), 175-180. [Gives incorrect value 4095 for a(46).]

Cf. A111944, A135547, A136043, A119513.

It appears that whenever b(n) = log2(a(n)/n + 1) is an integer and n > 1, b(n) = A119513(n) = A136043(n). - Andrei Zabolotskii, Jul 28 2025

Entry revised by N. J. A. Sloane, Jun 19 2006, Feb 24 2008
a(46) corrected, terms a(51) onward and b-file added by Max Alekseyev, Oct 12 2013
b-file extended by Max Alekseyev, Sep 24 2019

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

Original entry on oeis.org

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

N. J. A. Sloane, Feb 24 2008

nonn

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

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.

Cf. A038553, A111944

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

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

A138004 Odd numbers k for which all nontrivial cycles of the Ducci map on k-tuples modulo 2 have the same length.

Original entry on oeis.org

3, 5, 7, 11, 13, 19, 23, 29, 31, 37, 43, 47, 53, 59, 61, 67, 71, 79, 83, 89, 101, 103, 107, 127, 131, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 197, 199, 211, 223, 227, 233, 239, 251, 263, 269, 271, 281, 283, 293, 307, 311, 313, 317, 347, 349, 359, 367, 373, 379, 383, 389

Offset: 1

T. D. Noe, Feb 26 2008

nonn

All nontrivial cycles have the same length when either k is a prime number with primitive root 2 (see A001122), or when all factors of polynomial ((x+1)^k+1)/x (mod 2) have the same multiplicative order. The corresponding cycle lengths are listed in A138006.
It is conjectured that all terms of this sequence are prime numbers.
Numbers k such that A111944(k) = 2. - Max Alekseyev, Jul 10 2025

Max Alekseyev, Table of n, a(n) for n = 1..310
Florian Breuer, Ernest Lotter and Brink van der Merve, Ducci sequences and cyclotomic polynomials, Finite Fields Appl. 13 (2007), 293-304.
Michal Misiurewicz, John G. Stevens and Diana M. Thomas, Iterations of Linear Maps over Finite Fields, Linear Algebra and its Applications, Vol. 413 (2006), 218-234.

Cf. A001122, A038553, A111944, A138005, A138006.

Edited and terms a(36) onward added by Max Alekseyev, Jul 10 2025

A138005 Odd prime numbers p for which not all nontrivial cycles of the Ducci map on p-tuples modulo 2 have the same length.

Original entry on oeis.org

17, 41, 73, 97, 109, 113, 137, 193, 229, 241, 257, 277, 331, 337, 353, 397, 433, 449, 571, 577, 631, 641, 673, 683, 733, 769, 953, 997, 1009, 1013, 1021, 1033, 1051, 1069, 1093, 1103, 1153, 1181, 1201, 1217, 1297, 1321, 1361, 1429, 1489, 1597, 1601, 1613, 1657, 1709, 1789, 1801, 1831, 1873, 1889, 1933, 2011, 2017, 2081, 2113, 2137, 2143, 2153, 2161, 2179, 2273, 2297, 2341, 2381, 2441, 2521, 2593, 2617, 2633

Offset: 1

T. D. Noe, Feb 26 2008

nonn

Primes p such that A111944(p) > 2. - Max Alekseyev, Jul 10 2025

Cf. A038553, A111944, A138004.

a(8)-a(74) from Max Alekseyev, Jul 10 2025

cp's OEIS Frontend

A038553 Maximum cycle length in differentiation digraph for n-bit binary sequences.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A138004 Odd numbers k for which all nontrivial cycles of the Ducci map on k-tuples modulo 2 have the same length.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A138005 Odd prime numbers p for which not all nontrivial cycles of the Ducci map on p-tuples modulo 2 have the same length.

Views

Author

Keywords

Comments

Crossrefs

Extensions