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 such that 2^m == +- 1 (mod 2n + 1). 29
0, 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 quasi-order in the Hilton/Pederson reference.

For the complexity of computing this, see A002326.

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

From Gary W. Adamson, Sep 20 2011: (Start)

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)

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

From Gary W. Adamson, Aug 13 2012: (Start)

[Hilton & Pedersen] The Binary Quasi-order Theorem: If the symbol (I) is reduced (i.e. gcd(b, a(i) = 1) and contracted (i.e., the symbol involves no repeated a(i)), then the quasi-order of 2 mod b is k = Sum {i=1...r} k(i) and in fact 2^k == (-1)^r mod b. The symbol (*) is:

b [a(1),...a(2),...a(r)]

..[k(l),...k(2)....k(4)].

For example with b = 41:

41 [1,...5,...9]

...[3....2....5]

where the sum of terms in the bottom row = 10 = a(20). The calculation is (b - a(i) = 2^(k(i) * a(i + 1). Alternatively, terms in the bottom row are highest powers of k, 2^k maximal where we start (41 - 1), then extract 3 powers of 3, recording the remainder of 5 in a(2). Repeat: (41 - 5) = 36, extracting two powers of 2 placing "2" in k(2), with the remainder of 9 as a(3).n. With a "1" in the top row, the numbers of entries in the rows (j) are A179480(n+1) with sum of bottom row terms = A03358(n). The example shows that k = 10 = a(20); r = 3 = A179480(21), that the quasi-order of 2 mod 41 is 10 and further, that 2^10 ==-1 mod 41 so that 41 divides (2^10 + 1). (End)

From Gary W. Adamson, Aug 15 2012: (Start)

The number of possible coaches for b is appropriately called the Coach number of b by [Pedersen et al. - cf. A135303] and is recorded in A135303. For example, b = 17 has two possible coaches:

17 [1], [3, 7, 5],

...[4], [1, 1, 2],

indicated by A135303(8) = 2. Sum of terms in the bottom row = k = a(8) = 4. (End).

From Gary W. Adamson, Aug 16 2012: (Start)

From the [Hilton & Pederson] reference:

provide the case of b = 641 = a(320) as illustrating a factor of a Fermat number. The coach:

641: [1, 5, 159, 241, 25, 77, 141, 125, 129]

.....[7, 2,...1,...4,..3,..2,...2,...2,...9]

shows that the sum of terms in the bottom row (k) = 32. Thus a(320) = 32. The numbers of entries in each row = j = 9 (odd), so that A179480(341) = 9. When k is of the form 2^n, and j is odd (i.e., 32 in this case, j odd); b divides a Fermat number. The example shows that 2^32 == -1 mod 641 or 641 divides (2^32 + 1), the Fermat number 4294967297. (End)

From Gary W. Adamson, Aug 17 2012: (Start)

Note that a(42), b = 85, the Quasi-order symbol is:

85 [ 1, 21]

...[ 2,..6]

with k = 8, r = 2. The corollary 2^k == (-1)^r mod b implies that 85 divides (2^8 - 1) or 3 * 85 = 255. r is even in this case, so 85 does not divide a Fermat number. (End)

From Juhani Heino, Oct 26 2015: (Start)

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)

From Juhani Heino, Nov 06 2015: (Start)

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.

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)

REFERENCES

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

Jay Kappraff and Gary W. Adamson, Polygons and Chaos, Journal of Dynamical Systems and Geometric Theories, Vol 2 (2004), p 65.

Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Zurich, 2003.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

R. Bekes, J. Pedersen, B. Shao, Mad tea party cyclic partitions, Coll. Math. J. 43 (1) (2012) 25-36

P. Hilton, J. Pederson, On Factoring 2^k+-1, The Math. Educ. 5 (1) (1994) 29-31

Jay Kappraff and Gary W. Adamson, The Relationship of the Cotangent Function to Special Relativity Theory, Silver Means, p-cycles, and Chaos Theory; FORMA, Vol. 18, No. 3, pp. 249-262 (2003)

H. J. Smith, XICalc - Extra Precision Integer Calculator. [broken link?]

Gilbert Strang, A Chaotic Search for i, College Mathematics Journal 22, 3-12, (1991) [JSTOR]

Eric Weisstein's World of Mathematics, Multiplicative Order.

Eric Weisstein's World of Mathematics, Suborder Function

S. Wolfram, Algebraic Properties of Cellular Automata (1984), Appendix B.

FORMULA

a(n) = log_2(A160657(n) + 2) - 1. - Nathaniel Johnston, May 22 2009

a(n) <= n. - Charles R Greathouse IV, Sep 15 2012

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

EXAMPLE

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.

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.

MAPLE

A003558 := proc(n)

    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:

seq(A003558(n), n=0..20) ; # R. J. Mathar, Dec 01 2014

f:= proc(n) local t;

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

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

end proc:

0, seq(f(2*k+1), k=1..1000); # Robert Israel, Oct 26 2015

MATHEMATICA

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

Table[Suborder[2, 2n+1], {n, 0, 100}] (* T. D. Noe, Aug 02 2006 *)

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

CROSSREFS

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

Sequence in context: A085312 A046530 * A216066 A234094 A141419 A072451

Adjacent sequences:  A003555 A003556 A003557 * A003559 A003560 A003561

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Harry J. Smith, Feb 11 2005

Entry revised by N. J. A. Sloane, Aug 02 2006

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified April 25 00:46 EDT 2017. Contains 285346 sequences.