|
| |
|
|
A003558
|
|
Least number m > 0 such that 2^m == +- 1 (mod 2n + 1).
|
|
31
|
|
|
|
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 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
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
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.
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).
Jay Kappraff and Gary W. Adamson, Polygons and Chaos, Journal of Dynamical Systems and Geometric Theories, Vol 2 (2004), p 65.
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 is an essentially identical sequence apart from the offset.
Sequence in context: A085312 A046530 * A216066 A234094 A301853 A141419
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 and again Dec 10 2017
|
|
|
STATUS
|
approved
|
| |
|
|
