%I #306 Sep 08 2024 12:09:28

%S 1,1,2,3,3,5,6,4,4,9,6,11,10,9,14,5,5,12,18,12,10,7,12,23,21,8,26,20,

%T 9,29,30,6,6,33,22,35,9,20,30,39,27,41,8,28,11,12,10,36,24,15,50,51,

%U 12,53,18,36,14,44,12,24,55,20,50,7,7,65,18,36,34,69,46

%N Least number m > 0 such that 2^m == +-1 (mod 2n + 1).

%C Multiplicative suborder of 2 (mod 2n+1) (or sord(2, 2n+1)).

%C This is called quasi-order of 2 mod b, with b = 2*n+1, for n >= 1, in the Hilton/Pederson reference.

%C For the complexity of computing this, see A002326.

%C Also, the order of the so-called "milk shuffle" of a deck of n cards, which maps cards (1,2,...,n) to (1,n,2,n-1,3,n-2,...). See the paper of Lévy. - _Jeffrey Shallit_, Jun 09 2019

%C It appears that under iteration of the base-n Kaprekar map, for even n > 2 (A165012, A165051, A165090, A151949 in bases 4, 6, 8, 10), almost all cycles are of length a(n/2 - 1); proved under the additional constraint that the cycle contains at least one element satisfying "number of digits (n-1) - number of digits 0 = o(total number of digits)". - _Joseph Myers_, Sep 05 2009

%C From _Gary W. Adamson_, Sep 20 2011: (Start)

%C a(n) can be determined by the cycle lengths of iterates using x^2 - 2, seed 2*cos(2*Pi/N); as shown in the A065941 comment of Sep 06 2011. The iterative map of the logistic equation 4x*(1-x) is likewise chaotic with the same cycle lengths but initiating the trajectory with sin^2(2*Pi/N), N = 2n+1 [Kappraff & Adamson, 2004]. Chaotic terms with the identical cycle lengths can be obtained by applying Newton's method to i = sqrt(-1) [Strang, also Kappraff and Adamson, 2003], resulting in the morphism for the cot(2*Pi/N) trajectory: (x^2-1)/2x. (End)

%C From _Gary W. Adamson_, Sep 11 2019: (Start)

%C Using x^2 - 2 with seed 2*cos(Pi/7), we obtain the period-three trajectory 1.8019377...-> 1.24697...-> -0.445041... For an odd prime N, the trajectory terms represent diagonal lengths of regular star 2N-gons, with edge the shortest value (0.445... in this case.) (Cf. "Polygons and Chaos", p. 9, Fig 4.) We can normalize such lengths by dividing through with the lowest value, giving 3 diagonals of the 14-gon: (1, 2.801937..., 4.048917...). Label the terms ranked in magnitude with odd integers (1, 3, 5), and we find that the diagonal lengths are in agreement with the diagonal formula (sin(j*Pi)/14)/(sin(Pi/14)), with j = (1,3,5). (End)

%C Roots of signed n-th row A054142 polynomials are chaotic with respect to the operation (-2, x^2), with cycle lengths a(n). Example: starting with a root to x^3 - 5x^2 + 6x - 1 = 0; (2 + 2*cos(2*Pi/N) = 3.24697...); we obtain the trajectory (3.24697...-> 1.55495...-> 0.198062...); the roots to the polynomial with cycle length 3 matching a(3) = 3. - _Gary W. Adamson_, Sep 21 2011

%C From _Juhani Heino_, Oct 26 2015: (Start)

%C Start a sequence with numbers 1 and n. For next numbers, add previous numbers going backwards until the sum is even. Then the new number is sum/2. I conjecture that the sequence returns to 1,n and a(n) is the cycle length.

%C For example:

%C 1,7,4,2,1,7,... so a(7) = 4.

%C 1,6,3,5,4,2,1,6,... so a(6) = 6. (End)

%C From _Juhani Heino_, Nov 06 2015: (Start)

%C Proof of the above conjecture: Let n = -1/2; thus 2n + 1 = 0, so operations are performed mod (2n + 1). When the member is even, it is divided by 2. When it is odd, multiply by n, so effectively divide by -2. This is all well-defined in the sense that new members m are 1 <= m <= n. Now see what happens starting from an odd member m. The next member is -m/2. As long as there are even members, divide by 2 and end up with an odd -m/(2^k). Now add all the members starting with m. The sum is m/(2^k). It's divided by 2, so the next member is m/(2^(k+1)). That is the same as (-m/(2^k))/(-2), as with the definition.

%C So actually start from 1 and always divide by 2, although the sign sometimes changes. Eventually 1 is reached again. The chain can be traversed backwards and then 2^(cycle length) == +-1 (mod 2n + 1).

%C To conclude, we take care of a(0): sequence 1,0 continues with zeros and never returns to 1. So let us declare that cycle length 0 means unavailable. (End)

%C From _Gary W. Adamson_, Aug 20 2019: (Start)

%C Terms in the sequence can be obtained by applying the doubling sequence mod (2n + 1), then counting the terms until the next term is == +1 (mod 2n + 1). Example: given 25, the trajectory is (1, 2, 4, 8, 16, 7, 14, 3, 6, 12).

%C The cycle ends since the next term is 24 == -1 (mod 25) and has a period of 10. (End)

%C From _Gary W. Adamson_, Sep 04 2019: (Start)

%C Conjecture of Kappraff and Adamson in "Polygons and Chaos", p. 13 Section 7, "Chaos and Number": Given the cycle length for N = 2n + 1, the same cycle length is present in bases 4, 9, 16, 25, ..., m^2, for the expansion of 1/N.

%C Examples: The cycle length for 7 is 3, likewise for 1/7 in base 4: 0.021021021.... In base 9 the expansion of 1/7 is 0.125125125... Check: The first few terms are 1/9 + 2/81 + 5/729 = 104/279 = 0.1426611... (close to 1/7 = 0.142857...). (End)

%C From _Gary W. Adamson_, Sep 24 2019: (Start)

%C An exception to the rule for 1/N in bases m^2: (when N divides m^2 as in 1/7 in base 49, = 7/49, rational). When all terms in the cycle are the same, the identity reduces to 1/N in (some bases) = .a, a, a, .... The minimal values of "a" for 1/N are provided as examples, with the generalization 1/N in base (N-1)^2 = .a, a, a, ... for N odd:

%C 1/3 in base 4 = .1, 1, 1, ...

%C 1/5 in base 16 = .3, 3, 3, ...

%C 1/7 in base 36 = .5, 5, 5, ...

%C 1/9 in base 64 = .7, 7, 7, ...

%C 1/11 in base 100 = .9, 9, 9, ... (Check: the first three terms are 9/100 +9/(100^2) + 9/(100^3) = 0.090909 where 1/11 = 0.09090909...). (End)

%C For N = 2n+1, the corresponding entry is equal to the degree of the polynomial for N shown in (Lang, Table 2, p. 46). As shown, x^3 - 3x - 1 is the minimal polynomial for N = 9, with roots (1.87938..., -1.53208..., 0.347296...); matching the (abs) values of the 2*cos(Pi/9) trajectory using x^2 - 2. Thus, a(4) = 3. If N is prime, the polynomials shown in Table 2 are the same as those for the same N in A065941. If different, the minimal polynomials shown in Table 2 are factors of those in A065941. - _Gary W. Adamson_, Oct 01 2019

%C The terms in the 2*cos(Pi/N) trajectory (roots to the minimal polynomials in A187360 and (Lang)), are quickly obtained from the doubling trajectory (mod N) by using the operation L(m) 2*cos(x)--> 2*cos(m*x), where L(2), the second degree Lucas polynomial (A034807) is x^2 - 2. Relating to the heptagon and using seed 2*cos(Pi/7), we obtain the trajectory 1.8019..., 1.24697..., and 0.445041....; cyclic with period 3. All such roots can be derived from the N-th roots of Unity and can be mapped on the Vesica Piscis. Given the roots of Unity (Polar 1Angle(k*2*Pi/N), k = 1, 2, ..., (N-1)/2) the Vesica Piscis maps these points on the left (L) circle to the (R) circle by adding 1A(0) or (a + b*I) = (1 + 0i). But this operation is the same as vector addition in which the resultant vector is 1 + 1A(k*(2*Pi/N)). Example: given the radius at 2*Pi/7 on the left circle, this maps to (1 + 1A(2*Pi/7)) on the right circle; or 1A(2*Pi/7) --> (1.8019377...A(Pi/7). Similarly, 1 + 1A((2)*2*Pi/7)) maps to (1.24697...A (2*Pi/7); and 1 + 1A(3*2*Pi/7) maps to (.0445041...A(3*Pi/7). - _Gary W. Adamson_, Oct 23 2019

%C From _Gary W. Adamson_, Dec 01 2021: (Start)

%C As to segregating the two sets: (A014659 terms are those N = (2*n+1), N divides (2^m - 1), and (A014657 terms are those N that divide (2^m + 1)); it appears that the following criteria apply: Given IcoS(N, 1) (cf. Lang link "On the Equivalence...", p. 16, Definition 20), if the number of odd terms is odd, then N belongs to A014659, otherwise A014657. In IcoS(11, 1): (1, 2, 4, 3, 5), three odd terms indicate that 11 is a term in A014657. IcoS(15, 1) has the orbit (1, 2, 4, 7) with two odd terms indicating that 15 is a term in A014659.

%C It appears that if sin(2^m * Pi/N) has a negative sign, then N is in A014659; otherwise N is in A014657. With N = 15, m is 4 and sin(16 * Pi/15) is -0.2079116... If N is 11, m is 5 and sin(32 * Pi/11) is 0.2817325. (End)

%C On the iterative map using x^2 - 2, (Devaney, p. 126) states that we must find the function that takes 2*cos(Pi) -> 2*cos(2*Pi). "However, we may write 2*cos(2*Pi) = 2*(2*cos^2(Pi) - 1) = (2*cos(Pi))^2 - 2. So the required function is x^2 - 2." On the period 3 implies chaos theorem of James Yorke and T.Y. Li, proved in 1975; Devaney (p. 133) states that if F is continuous and we find a cycle of period 3, there are infinitely many other cycles for this map with every possible period. Check: The x^2 - 2 orbit for 7 has a period of 3, so this entry has periodic points of all other periods. - _Gary W. Adamson_, Jan 04 2023

%D Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. 261-264.

%D Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6).

%D Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Theory and Experiment; Perseus Books Publishing, 1992, pp. 121-126.

%H T. D. Noe, <a href="/A003558/b003558.txt">Table of n, a(n) for n = 0..1000</a>

%H R. Bekes, J. Pedersen, and B. Shao, <a href="http://web.archive.org/web/1id_/http://math.scu.edu/~jpederse/papers/No.207partitions.pdf">Mad tea party cyclic partitions</a>, Coll. Math. J. 43 (1) (2012) 25-36, <a href="https://www.jstor.org/stable/10.4169/college.math.j.43.1.025">Jstor</a>.

%H William Q. Erickson, Daniel Herden, Jonathan Meddaugh, Mark R. Sepanski, Mitchell Minyard, and Kyle Rosengartner, <a href="https://arxiv.org/abs/2409.02306">Limits and Periodicity of Metamour 2-Distance Graphs</a>, arXiv:2409.02306 [math.CO], 2024. See p. 9.

%H Daniel Gabric and Jeffrey Shallit, <a href="https://arxiv.org/abs/1906.03689">Borders, Palindrome Prefixes, and Square Prefixes</a>, arXiv:1906.03689 [cs.DM], 2019.

%H P. Hilton and J. Pedersen, <a href="https://openjournals.libs.uga.edu/tme/article/view/1778/1686">On Factoring 2^k+-1</a>, The Math. Educ. 5 (1) (1994) 29-31.

%H Jay Kappraff and Gary W. Adamson, <a href="http://archive.bridgesmathart.org/2001/bridges2001-67.html">Polygons and Chaos</a>, Bridges: Mathematical Connections in Art, Music, and Science, 2001, pages 67-80.

%H Anthony Kay and Katrina Downes-Ward, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL25/Kay/kay5.html">Fixed Points and Cycles of the Kaprekar Transformation: 1. Odd Bases</a>, J. Int. Seq., Vol. 25 (2022), Article 22.6.7.

%H Anthony Kay and Katrina Downes-Ward, <a href="https://arxiv.org/abs/2408.12257">Fixed Points and Cycles of the Kaprekar Transformation: 2. Even bases</a>, arXiv:2408.12257 [math.CO], 2024. See p. 6.

%H Torleiv Klove, <a href="https://doi.org/10.1007/s12095-015-0154-5">On covering sets for limited-magnitude errors</a>, Cryptogr. Commun. 8 (3) (2016) 415-433

%H Wolfdieter Lang, <a href="https://arxiv.org/abs/1210.1018">The Field Q(2Cos Pi/N), its Galois group and length ratios in the regular n-gon</a>, arXiv:1210.1018 [math.GR], 2012-2017.

%H Wolfdieter Lang, <a href="https://arxiv.org/abs/2008.04300">On the Equivalence of Three Complete Cyclic Systems of Integers</a>, arXiv:2008.04300 [math.NT], 2020.

%H Paul Lévy, <a href="http://www.numdam.org/item?id=CM_1951__8__1_0">Sur quelques classes de permutations</a>, Compositio Mathematica, 8 (1951), 1-48.

%H Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, <a href="https://doi.org/10.1007/BF01223745">Algebraic Properties of Cellular Automata</a>, Communications in Mathematical Physics, volume 93, number 2, June 1984, pages 219-258, appendix B part C sord_N(2). Also <a href="https://content.wolfram.com/uploads/sites/34/2020/07/algebraic-properties-cellular-automata.pdf">third author's copy</a> (and <a href="http://web.archive.org/web/1id_/http://www.stephenwolfram.com/publications/articles/ca/84-properties/9/text.html">text</a>).

%H H. J. Smith, <a href="http://harry-j-smith-memorial.com/download.html#XICalc">XICalc - Extra Precision Integer Calculator</a>. [Broken link]

%H Gilbert Strang, <a href="http://www.math.drexel.edu/~tolya/i-strang.pdf">A Chaotic Search for i</a>, College Mathematics Journal 22, 3-12, (1991) <a href="http://www.jstor.org/stable/2686733">[JSTOR]</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MultiplicativeOrder.html">Multiplicative Order</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SuborderFunction.html">Suborder Function</a>.

%F a(n) = log_2(A160657(n) + 2) - 1. - _Nathaniel Johnston_, May 22 2009

%F a(n-1) = card {cos((2^k)*Pi/(2*n-1)): k in N} for n >= 1 (see A216066, an essentially identical sequence, for more information). - _Roman Witula_, Sep 01 2012

%F a(n) <= n. - _Charles R Greathouse IV_, Sep 15 2012 [For n >= 1]

%F a(n) = min{k > 0 | q_k = q_0} where q_0 = 1 and q_k = |2*n+1 - 2*q_{k-1}| (cf. [Schick, p. 4]; q_k=1 for n=1; q_k=A010684(k) for n=2; q_k=A130794(k) for n=3; q_k=|A154870(k-1)| for n=4; q_k=|A135449(k)| for n=5.) - _Jonathan Skowera_, Jun 29 2013

%F 2^(a(n)) == A332433(n) (mod (2*n+1)), and (2^(a(n)) - A332433(n))/(2*n+1) = A329593(n), for n >= 0. - _Wolfdieter Lang_, Apr 09 2020

%e a(3) = 3 since f(x) = x^2 - 2 has a period of 3 using seed 2*cos(2*Pi/7), where 7 = 2*3 + 1.

%e a(15) = 5 since the iterative map of the logistic equation 4x*(1-x) has a period 5 using seed sin^2(2*Pi)/N; N = 31 = 2*15 + 1.

%p A003558 := proc(n)

%p local m,mo ;

%p if n = 0 then

%p return 0 ;

%p end if;

%p for m from 1 do

%p mo := modp(2^m,2*n+1) ;

%p if mo in {1,2*n} then

%p return m;

%p end if;

%p end do:

%p end proc:

%p seq(A003558(n),n=0..20) ; # _R. J. Mathar_, Dec 01 2014

%p f:= proc(n) local t;

%p t:= numtheory:-mlog(-1,2,n);

%p if t = FAIL then numtheory:-order(2,n) else t fi

%p end proc:

%p 0, seq(f(2*k+1),k=1..1000); # _Robert Israel_, Oct 26 2015

%t Suborder[a_,n_]:=If[n>1&&GCD[a,n]==1,Min[MultiplicativeOrder[a,n,{-1,1}]],0];

%t Join[{1},Table[Suborder[2,2n+1],{n,100}]] (* _T. D. Noe_, Aug 02 2006 *) (* revised by _Vincenzo Librandi_, Apr 11 2020 *)

%o (PARI) a(n) = {m=1; while(m, if( (2^m) % (2*n+1) == 1 || (2^m) % (2*n+1) == 2*n, return(m)); m++)} \\ _Altug Alkan_, Nov 06 2015

%o (PARI) isok(m, n) = my(md = Mod(2, 2*n+1)^m); (md==1) || (md==-1);

%o A003558(n) = my(m=1); while(!isok(m,n) , m++); m; \\ _Michel Marcus_, May 06 2020

%o (Python)

%o def A003558(n):

%o m, k = 1, 2 % (c:=(r:=n<<1)+1)

%o while not (k==1 or k==r):

%o k = 2*k%c

%o m += 1

%o return m # _Chai Wah Wu_, Oct 09 2023

%Y Cf. A054142, A065941, A085478, A160657, A179480, A135303 (coach numbers), A216371 (odd primes with one coach), A000215 (Fermat numbers).

%Y A216066 is an essentially identical sequence apart from the offset.

%Y Cf. A329593, A332433 (signs).

%Y Cf. A014657, A014659.

%K nonn

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Harry J. Smith_, Feb 11 2005

%E Entry revised by _N. J. A. Sloane_, Aug 02 2006 and again Dec 10 2017