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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003558 Least number m > 0 such that 2^m == +- 1 (mod 2n + 1). 31

%I

%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 in the Hilton/Pederson reference.

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

%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 2Pi/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 obtain by applying Newton's method to i = sqrt(-1) [Strang, also Kappraff and Adamson, 2003], resulting in the morphism for the cot 2Pi/N trajectory: (x^2-1)/2x. (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 2Pi/N = 3.24697...); we obtain the trajectory (3.24697...-> 1.55495...-> .198062...); the roots to the polynomial with cycle length 3 matching a(3) = 3. - _Gary W. Adamson_, Sep 21 2011

%C Also 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

%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: 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)

%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, Zurich, 2003.

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

%H R. Bekes, J. Pedersen, B. Shao, <a href="http://math.scu.edu/~jpederse/papers/No.207partitions.pdf">Mad tea party cyclic partitions</a>, Coll. Math. J. 43 (1) (2012) 25-36

%H P. Hilton, J. Pederson, <a href="http://math.coe.uga.edu/tme/issues/v05n1/hiltonPederson.pm.pdf">On Factoring 2^k+-1</a>, The Math. Educ. 5 (1) (1994) 29-31

%H Jay Kappraff and Gary W. Adamson, <a href="http://www.scipress.org/journals/forma/pdf/1804/18040249.pdf">The Relationship of the Cotangent Function to Special Relativity Theory, Silver Means, p-cycles, and Chaos Theory</a>; FORMA, Vol. 18, No. 3, pp. 249-262 (2003).

%H Jay Kappraff and Gary W. Adamson, <a href="https://doi.org/10.1080/1726037X.2004.10698481">Polygons and Chaos</a>, Journal of Dynamical Systems and Geometric Theories, Vol 2 (2004), p 65.

%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>

%H S. Wolfram, <a href="http://www.stephenwolfram.com/publications/articles/ca/84-properties/9/text.html">Algebraic Properties of Cellular Automata (1984)</a>, Appendix B.

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

%F a(n) <= n. - _Charles R Greathouse IV_, Sep 15 2012

%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

%e a(3) = 3 since f(x), x^2 - 2 has a period of 3 using seed 2*cos 2Pi/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 2Pi/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 Table[Suborder[2,2n+1], {n,0,100}] (* _T. D. Noe_, Aug 02 2006 *)

%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

%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.

%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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 05:40 EST 2019. Contains 320245 sequences. (Running on oeis4.)