OFFSET
1,8
COMMENTS
The Froemke-Grossman 1988 reference is the earliest I have seen. a(n) is the charm bracelet function b(2,2*n+1) in their notation. - N. J. A. Sloane, Feb 28 2023
This sequence is called the "coach numbers" ("c(2*n+1)"), and was studied by J. Pedersen, Byron Walden, Victor Quintanar-Zilinskas and Linda Velarde of Santa Clara University. Coach Theorem: Let b = 2*n+1 > 1 and let phi(b) be the Euler totient function. Let Sigma(b) be the complete symbol of b, let c be the number of coaches in Sigma(b), and let k = Sum_{i=1..r} k(i). Then phi(b) = 2 * c * k [Hilton & Pedersen, p. 262]. The complete symbols for b = 17 and 43 are shown in the examples. - Gary W. Adamson, Aug 15 2012
Conjecture relating to primes with more than one coach: The combined set of integers in the top rows of all coaches of these primes is composed of a permutation of the first q odd integers, where prime p = (4q-1) or (4q+1), (q > 0). Example: As shown for 17, this prime has two coaches with the top rows [1] and [3, 7, 5]. 43 has three coaches with q = 11. The top rows are [1, 21, 11], [3, 5, 19], [7, 9, 17, 13, 15]. The comment of Sep 08 2012 in A216371 applies to primes with one coach, in which case "all coaches" is reduced to one and the set of q odd integers is in the top row of the coach. - Gary W. Adamson, Sep 10 2012
Conjecture [Carl Schick]: If 2*n+1 is prime, then these are the number of distinct cycles of f(k) = |(2*n+1) - 2*k| beginning at an odd number 0 < k < 2*n. - Jonathan Skowera, Aug 03 2013 [See also the Brändli and Beyne link, eq. (2). - Wolfdieter Lang, Feb 08 2020]
From Gary W. Adamson, Oct 04 2019: (Start)
Conjecture of Aug 03 2013 proved by Jean Pedersen. By way of example, take A003558(5) = 11, such that
2^5 == -1 (mod 11). Then Pedersen on p. 98 has:
11 - 1 = 2^1 * 5 (pick "1", odd, the putative seed number)
11 - 5 = 2^1 * 3 (then subtract 3 in the next row)
11 - 3 = 2^3 * 1 (cycle ends). Then Pedersen constructs the "coach" (p. 98) for N= 11: [1, 5, 3]
.......... [1, 1, 3]. The top row represents the angles on the tape used to construct an 11-gon at the operative crease lines beginning with Pi/11. (extract the (1,5,3) column). Then extract the exponents of 2: (1,1,3); which are the bottom row terms. The final result is that at successive creases on the tape are at angles of j*Pi/11, j = (1,5,3); alternatively at the top of the tape, then the bottom. The code U(1), D(1), U(3) is understood to be those numbers of bisections at each vertex. The total numbers of bisections = 5 = (1 + 1 + 3), shown to be the entry for N = 11 in A003558. (End)
REFERENCES
Froemke, Jon, and Jerrold W. Grossman. "An algebraic approach to some number-theoretic problems arising from paper-folding regular polygons." The American mathematical monthly 95.4 (1988): 289-307. See Appendix.
Peter Hilton & Jean Pedersen, A Mathematical Tapestry: Demonstrating the Beautiful Unity of Mathematics; Cambridge University Press, 2010, pages 260-264.
Carl Schick, Trigonometrie und unterhaltsame Zahlentheorie, Bokos Druck, Zürich, 2003 (ISBN 3-9522917-0-6). Tables 3.1 to 3.10, for odd p = 3..113, pp. 158-166.
LINKS
T. D. Noe, Table of n, a(n) for n = 1..10000
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, [in Russian], Problemy Peredachi Informatsii, 43 (No. 3, 2007), 39-53.
V. I. Levenshtein, Conflict-avoiding codes and cyclic triple systems, Probl Inf Transm 43, 199-212 (2007).
FORMULA
EXAMPLE
Refer to A003558 for the J. Pedersen definition of a Coach. a(8) for b = 17 = 2 since 17 has two possible Coaches:
17: [1] and [3, 7, 5]
[4] [1, 1, 2];
where sum of the bottom row terms = k = 4 = A003558(8). For b = 43, a(21) = 3 since there are three possible coaches for 43:
43: [1, 21, 11] [3, 5, 19] [7, 9, 17, 13, 15]
[1, 1, 5], [3, 1, 3], [2, 1, 1, 1, 2],
where k = sum of terms in bottom rows of all possible coaches = 7 = A003558(21). For the coach with a "1" in the top row, the numbers of terms in the rows ("j" in A003558), = A179480(22) = 3. Note that the parity of numbers of terms in the bottom coach rows is the same.
From Gary W. Adamson, Aug 24 2019: (Start)
An alternative to the coach method of Pedersen and Hilton involves the doubling sequence, mod n; (43 in this case). The top row begins (1, 2, 4, 8, 16, ...) but the next number is 11, not 32. 32 == -11 (mod 43). We pick the least (in absolute value) of the two candidates (11 and 32): 11. The top row ends when the rightmost term is (n-1)/2 = 21. In subsequent rows the leftmost term is the least odd number not previously used, in this case 3. Continue with the doubling sequence and stop when the next row produces a term already used.
"20" ends row 2 since (2 * 20) = 40 == -3 (mod 43). 3 has been used so that row ends and our next row begins with the next unused odd term, a 7. That row ends with 18 since 2 * 18 = 36 == -7 (mod 43).
The entire set is complete when every term (1 through (n-1)/2) is present without duplication. In this method, k is likewise 7 but is represented by the numbers of terms in the top row. Pedersen's [1, 21, 11] appears as the only odd terms of the top row. [3, 5, 19] appears as the odd terms of the middle row, and [7, 9, 17, 13, 15] are the only odd terms of the bottom row. The three completed rows are:
[1, 2, 4, 8, 16, 11, 21;
3, 6, 12, 19, 5, 10, 20;
7, 14, 15, 13, 17, 9, 18]
It appears that the numbers of rows is equal to Pedersen's
number of coaches. Another example is the complete system of coaches shown on p. 261 of (Hilton and Pedersen):
31: [1, 15], [3, 7], [5, 13, 9, 11]
[1, 4], [2, 3], [1, 1, 1, 2]
The alternative system, called an r-t table in A065941, is
[1, 2, 4, 8, 15;
3, 6, 12, 7, 14;
5, 10, 11, 9, 13]
The odd terms of the top row (1, 15) appear in the leftmost coach. The odd terms (3, 7) appear in the middle coach, and (5, 11, 9, 13) are shown in the rightmost coach. (End)
Pedersen's coaches can be derived from the alternative system, doubling (mod N) since her coaches are simply another version: (repeated bisections (mod N)). First write out the doubling terms (mod N). Say N = 23: 1, 2, 4, 8, 7, 9, 5, 10, 3, 6, 11, representing the trajectory of terms 2*cos(j*Pi/23), using (x^2-2); j = 1, 2, 4, .... Begin with ("1"), then jump to the next odd term (11), then to each odd term in succession going left, getting: 23: (1, 11, 3, 5, 9, 7); the top row in Pedersen's coach. ....(1, 2, 2, 1, 1, 4) is the bottom row for 23 as shown on p. 105. Those terms are the numbers of term jumps in the previous operation; for example (1 to 11) = 1, (11 to 3) = 2, (3 to 5) = 2; and so on. Note that the number of terms in the doubling trajectory (11) matches the sum of terms in the bottom row of the coach, satisfying 2^11 == 1 (mod 23). - Gary W. Adamson, Oct 23 2019
MAPLE
A135303 := proc(n)
numtheory[phi](2*n+1)/2/A003558(n) ;
end proc:
seq(A135303(n), n=1..40) ; # R. J. Mathar, Dec 01 2014
MATHEMATICA
Array[EulerPhi[#2]/(2 If[#2 > 1 && GCD[#1, #2] == 1, Min[MultiplicativeOrder[#1, #2, {-1, 1}]], 0]) & @@ {2, 2 # + 1} &, 105] (* Michael De Vlieger, Oct 25 2019 *)
PROG
(PARI) isok8(m, n) = my(md = Mod(2, 2*n+1)^m); (md==1) || (md==-1);
A003558(n) = my(m=1); while(!isok8(m, n) , m++); m;
a(n) = eulerphi(2*n+1)/(2*A003558(n)); \\ Michel Marcus, Jun 11 2020
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 05 2007
EXTENSIONS
Title changed by Wolfdieter Lang and M. F. Hasler, Feb 20 2020
STATUS
approved