OFFSET
1,3
COMMENTS
The orbit of i under the action of the modular group (that is, the set {(ai+b)/(ci+d): a,b,c,d in Z, ad-bc=1}) is symmetric with respect to the imaginary axis, and periodic with period 1 relative to horizontal translations. So reflecting the orbit in the strip 0<=Re(z)<=1/2 across the imaginary axis and then translating horizontally by integer amounts gives the complete orbit of i in the complex plane.
The orbit in the strip 0<=Re(z)<=1/2 is the union of finite sets, one for each term of A008784, that correspond to the levels of {a(n)}. Each finite set is made of points with rational coordinates on horizontal lines with equation Im(z)=1/N, where N is a term of A008784. Starting at the top with n=1=A008784(1), we have only k=0, or i itself, corresponding to the identity element of the modular group. Then going down one level, at n=2=A008784(2), we have only k=1, or the element 1/2+i/2 corresponding to the modular group element ((1,0),(1,1)). Then at the next level n=3, we have A008784(3)=5, and we still have only one entry k=2, giving 2/5+i/5, corresponding to the matrix ((0,-1),(1,-2)). Continuing this way we find that all levels up to n=16 have only one term of the sequence. This is because if N=A008784(n), then for 1<=n<=16 the equation x^2+y^2=N has only one solution with (x,y) relatively prime. For n=17, we have A008784(17)=65 and (1,8), (4,7) are two solutions of x^2+y^2=65. So we find two terms of the sequence, 8 and 18, at level 17, corresponding to 8/65+i/65 and 18/65+i/65 in the orbit of i, with matrices ((0,-1),(1,-8)) and ((2,1),(7,4)).
So {a(n)} lists the numerators of the real part of the elements of the orbit of i in 0<=Re(z)<=1/2, as we descend the "floors", moving from left to right.
Here is how the sequence is constructed: Each N = A008784(n) can be expressed as the sum of two relatively prime squares. If N has s prime divisors, and all of them are of form 4k+1, then there will be 2^(s-1) solutions of x^2 + y^2 = N (see the MathStackExchange post cited in the Links section).
Consider one such solution, c^2+d^2=N. Let a,b be the unique integers given by the Euclidean algorithm such that ad-bc=1 (or equivalently, the pair of integers (x,y) at minimal distance from the origin such that cx-dy=1). It can be shown that ac+bd will be in {1,2,...,N-1} and relatively prime to N. Let k=min(ac+bd, N-ac-bd). Then k is in {1,2,...,N/2}. Do this for every possible solution of x^2+y^2=N, then list the resulting numbers (all contained in {1,2,3,...,N/2}) in increasing order. These will be the numerators of the rational numbers that are the real part of the points of the orbit of i with imaginary part 1/N. Row n of the triangle is then k1,k2,...,kr and r is the row length, which will always be a power of 2.
LINKS
MathStackExchange, Representation as a sum of two squares.
EXAMPLE
For each row number n, the table below gives N=A008784(n), the number r of terms in the n-th row, and the values of those terms:
.
terms in row n:
n N r k = 1 2 ... r
-- -- - ---------------
1 1 1 0;
2 2 1 1;
3 5 1 2;
4 10 1 3;
5 13 1 5;
6 17 1 4;
7 25 1 7;
8 26 1 5;
9 29 1 12;
10 34 1 13;
11 37 1 6;
12 41 1 9;
13 50 1 7;
14 53 1 23;
15 58 1 17;
16 61 1 11;
17 65 2 8, 18;
18 73 1 27;
19 74 1 31;
20 82 1 9;
21 85 2 13, 38;
...
For row n=17, N=A008784(17)=65 and 65 has two representations as x^2+y^2: 65 = 1^2 + 8^2 = 7^2 + 4^2. For the pair (1,8), we have (a,b)=(1,7), so ac+bd=57, and -ab-cd = -57 == 8 (mod 65). For the pair (7,4) we have (a,b)=(2,1), so ac+bd=18 and -ac-bd = -18 == 47 (mod 65). Taking the minimum, we find that 8,18 will be consecutive terms in the sequence, and 8/65+i/65, 18/65+i/65 will be all the elements in the orbit of i with imaginary part 1/65 and real part in 0<=Re(z)<=1/2. The next level with two terms is A008784(21)=85.
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Valerio De Angelis, Mar 26 2024
STATUS
approved