|
| |
|
|
A003558
|
|
Least number m > 0 such that 2^m == +- 1 (mod 2n + 1).
|
|
32
|
|
|
|
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.
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
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(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 2Pi/N trajectory: (x^2-1)/2x. (End)
From Gary W. Adamson, Sep 11 2019: (Start)
Using x^2 - 2 with seed 2*cos(Pi/7), we obtain the period-three trajectory 1.8019377...-> 1.24697...-> -.445041... For an odd prime N, the trajectory terms represent diagonal lengths of regular star 2N-gons, with edge the shortest value (.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)
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...-> .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)
From Gary W. Adamson, Aug 20 2019: (Start)
Terms in the sequence can be obtained by applying the doubling sequence mod (2n + 1), then counting the numbers of 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)
From Gary W. Adamson, Sep 04 2019: (Start)
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: .021021021.... In base 9 the expansion of 1/7 is .125125125... Check: The first few terms are 1/9 + 2/81 + 5/729 = 104/279 = .1426611... (close to 1/7 = .142857). (End)
From Gary W. Adamson, Sep 24 2019: (Start) 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:
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) = .090909 where 1/11 = .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
|
|
|
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, Jstor.
Daniel Gabric, Jeffrey Shallit, Borders, Palindrome Prefixes, and Square Prefixes, arXiv:1906.03689 [cs.DM], 2019.
P. Hilton, J. Pedersen, 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.
Wolfdieter Lang, "The Field Q(2Cos Pi/N), its Galois group and length ratios in the regular n-gon". https://arxiv.org/pdf/1210.1018.pdf
Paul Lévy, Sur quelques classes de permutations, Compositio Math. 8 (1951), 1-48.
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(2*Pi/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(2*Pi)/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: A023160 A085312 A046530 * A216066 A234094 A301853
Adjacent sequences: A003555 A003556 A003557 * A003559 A003560 A003561
|
|
|
KEYWORD
|
nonn,changed
|
|
|
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
|
| |
|
|
