

A003558


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


60



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, 9, 29, 30, 6, 6, 33, 22, 35, 9, 20, 30, 39, 27, 41, 8, 28, 11, 12, 10, 36, 24, 15, 50, 51, 12, 53, 18, 36, 14, 44, 12, 24, 55, 20, 50, 7, 7, 65, 18, 36, 34, 69, 46
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Multiplicative suborder of 2 (mod 2n+1) (or sord(2, 2n+1)).
This is called quasiorder of 2 mod b, with b = 2*n+1, for n >= 1, in the Hilton/Pederson reference.
For the complexity of computing this, see A002326.
Also, the order of the socalled "milk shuffle" of a deck of n cards, which maps cards (1,2,...,n) to (1,n,2,n1,3,n2,...). See the paper of Lévy.  Jeffrey Shallit, Jun 09 2019
It appears that under iteration of the basen 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 (n1)  number of digits 0 = o(total number of digits)".  Joseph Myers, Sep 05 2009
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*(1x) 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^21)/2x. (End)
Using x^2  2 with seed 2*cos(Pi/7), we obtain the periodthree trajectory 1.8019377...> 1.24697...> 0.445041... For an odd prime N, the trajectory terms represent diagonal lengths of regular star 2Ngons, 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 14gon: (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)
Roots of signed nth 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
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.
For example:
1,7,4,2,1,7,... so a(7) = 4.
1,6,3,5,4,2,1,6,... so a(6) = 6. (End)
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 welldefined 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.
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).
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)
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).
The cycle ends since the next term is 24 == 1 (mod 25) and has a period of 10. (End)
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.
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)
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 (N1)^2 = .a, a, a, ... for N odd:
1/3 in base 4 = .1, 1, 1, ...
1/5 in base 16 = .3, 3, 3, ...
1/7 in base 36 = .5, 5, 5, ...
1/9 in base 64 = .7, 7, 7, ...
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)
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
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 Nth 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, ..., (N1)/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
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.
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)
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


REFERENCES

Peter Hilton and Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, pp. 261264.
Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3952291706).
Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Theory and Experiment; Perseus Books Publishing, 1992, pp. 121126.


LINKS

Jay Kappraff and Gary W. Adamson, Polygons and Chaos, Bridges: Mathematical Connections in Art, Music, and Science, 2001, pages 6780.


FORMULA

a(n1) = card {cos((2^k)*Pi/(2*n1)): k in N} for n >= 1 (see A216066, an essentially identical sequence, for more information).  Roman Witula, Sep 01 2012
a(n) = min{k > 0  q_k = q_0} where q_0 = 1 and q_k = 2*n+1  2*q_{k1} (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(k1) for n=4; q_k=A135449(k) for n=5.)  Jonathan Skowera, Jun 29 2013


EXAMPLE

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.
a(15) = 5 since the iterative map of the logistic equation 4x*(1x) has a period 5 using seed sin^2(2*Pi)/N; N = 31 = 2*15 + 1.


MAPLE

local m, mo ;
if n = 0 then
return 0 ;
end if;
for m from 1 do
mo := modp(2^m, 2*n+1) ;
if mo in {1, 2*n} then
return m;
end if;
end do:
end proc:
f:= proc(n) local t;
t:= numtheory:mlog(1, 2, n);
if t = FAIL then numtheory:order(2, n) else t fi
end proc:


MATHEMATICA

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


PROG

(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
(PARI) isok(m, n) = my(md = Mod(2, 2*n+1)^m); (md==1)  (md==1);
(Python)
m, k = 1, 2 % (c:=(r:=n<<1)+1)
while not (k==1 or k==r):
k = 2*k%c
m += 1


CROSSREFS

A216066 is an essentially identical sequence apart from the offset.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



