A363760 -id:A363760 - cp's OEIS frontend

A307110 Index of matching grid point in the bijection between two infinite quadratic grids with one grid rotated by Pi/4 around the common point (0,0), using an enumeration of the grid points by A305575 and A305576.

0, 1, 6, 3, 8, 2, 11, 4, 9, 5, 15, 7, 19, 14, 10, 16, 17, 18, 12, 20, 13, 26, 27, 28, 25, 21, 22, 23, 24, 38, 31, 40, 33, 42, 35, 44, 29, 30, 51, 32, 53, 34, 55, 36, 49, 57, 58, 59, 60, 62, 39, 64, 41, 66, 43, 68, 37, 46, 47, 48, 45, 50, 63, 52, 65, 54, 67

Offset: 0

Hugo Pfoertner, following a proposal by Rainer Rosenthal, Mar 28 2019

nonn

In a discussion in the newsgroup de.sci.mathematik, Klaus Nagel (see links) described a bijection P: G -> H between the grid points of two Cartesian grids G{Z X Z} and H{Z X Z} rotated against each other by Pi/4 around the only common point (0,0). This is a variation of the marriage problem asking for a matching in the infinite bipartite graph of the vertices of G U H with small distance d=|P(g)-g| for all points g in G.
Points within the grids are addressed by (i,j) in grid G and by (k,m) in grid H.
The plane is divided into horizontal strips of width cos(Pi/8) = sqrt(sqrt(2)+2)/2, with the x-axis as centerline of strip 0. Grid G is rotated by Pi/8, grid H by -Pi/8.
Assuming proper boundary conditions, there is exactly one grid point of G per grid line i=const and one grid point of grid H per grid line k=const inside each strip.
The intersections of the grid lines i=const from the rotated grid G and of lines k=const from the rotated grid H with the centerline of the strip are determined. The grid points inside the strip are paired such that the distance of the intersection points of lines i=const of grid G and of lines k=const of grid H with the strip centerline is minimized.
This bijection achieves a maximum of all mutual Euclidean distances of all pairs of cos(Pi/8)=0.9238795... (the strip width).
It is conjectured that the least possible maximum distance within pairs can be reduced to sqrt(5)*sin(Pi/8)=0.855706... (A386241), but not further, and that this can be achieved by "local repairs" of the result of the strip bijection, i.e. by reassigning the connections in groups of 4 pairs, one of which being the pair with d>0.8557... and 3 pairs in the vicinity of the violating pair, but potentially addressing points in neighbor strips. The conjecture is supported by extensive numerical results, but an announced proof by Klaus Nagel remained unpublished.
For the current sequence no repair is applied. The first repairs are required beyond i^2+j^2=40. The affected sequence terms for n>=124 are visible in the b-file of A307731.
The results of the matching are shown by enumerating the grid points of grid G according to the sequence pair A305575(n) for i and A305576(n) for j.
After finding the indices of the bijection partners (k,m) in grid H using Klaus Nagel's method, the position L where A305575(L)=k and A305576(L)=m is determined by table lookups, and the unique result is a(n)=L.
The sequence is a permutation of the natural numbers.

			The following table shows the first few matched pairs of grid points:
    Grid G     Grid H      Grid H rotated
   n  i  j  a(n) k  m  (k,m) rotated by -Pi/4  distance of matched points
   0  0  0    0  0  0    0.000000  0.000000   0.000000
   1  1  0    1  1  0    0.707107 -0.707107   0.765367
   2  0  1    6 -1  1    0.000000  1.414214   0.414214
   3 -1  0    3 -1  0   -0.707107  0.707107   0.765367
   4  0 -1    8  1 -1    0.000000 -1.414214   0.414214
   5  1  1    2  0  1    0.707107  0.707107   0.414214
   6 -1  1   11 -2  0   -1.414214  1.414214   0.585786
   7 -1 -1    4  0 -1   -0.707107 -0.707107   0.414214
   8  1 -1    9  2  0    1.414214 -1.414214   0.585786
   9  2  0    5  1  1    1.414214  0.000000   0.585786
  10  0  2   15 -1  2    0.707107  2.121320   0.717439
  11 -2  0    7 -1 -1   -1.414214  0.000000   0.585786
  12  0 -2   19  1 -2   -0.707107 -2.121320   0.717439
  13  2  1   14  1  2    2.121320  0.707107   0.317025

Hugo Pfoertner and Rainer Rosenthal, Table of n, a(n) for n = 0..10000
H. Carstens, W. Deuber, W. Thumser, and E. Koppenrade, Geometrical Bijections in Discrete Lattices. Combinatorics, Probability and Computing, 8(1-2), 109-129, 1999.
Klaus Nagel, Zwei Gitter, thread in newsgroup de.sci.mathematik, description of bijection (in German), Jan 7 2007.
Klaus Nagel, Zwei Gitter, thread in newsgroup de.sci.mathematik, modification of strip location (in German), Jan 14 2007.
Hugo Pfoertner, Illustration of strip bijection, (2019).
Rainer Rosenthal, Illustrating examples a(0) ... a(29), Nov 29 2023.

Cf. A144981, A305575, A305576, A307731, A362955, A362956, A363760, A367150, A386241.

/* It is assumed that the files a305575 and a305576 contain the second column of the corresponding b-files */
a305575=readvec(a305575); a305576=readvec(a305576);
p(i,j)={my(C=cos(Pi/8),S=sin(Pi/8),T=S/C,gx=i*C-j*S,gy=i*S+j*C,k,xm,ym,v=[0,0]);
k=round(gy/C); ym=C*k; xm=gx+(gy-ym)*T;
  v[1]=round((xm-ym*T)*C);  v[2]=round((ym+v[1]*S)/C);  v}
findpos(v)={for(k=1,#a305575,if(v[1]==a305575[k]&&v[2]==a305576[k],return(k-1)))}
for(n=1,67,print1(findpos(p(a305575[n],a305576[n])),", "))

A367146 Cycle lengths obtained by repeated application of the distance-minimizing variant of the strip bijection for the square lattice described in A367150.

Original entry on oeis.org

1, 8, 12, 24, 25, 56, 120, 152, 154, 200, 217, 376, 464, 568, 616, 1242, 1368, 1624, 1736, 1945, 4376, 4968, 5176, 10682, 13016, 14152, 15560, 17497, 40376, 42728, 46648, 94234, 120664, 125320, 139976, 157465, 367544, 376936, 419896, 840570, 1100760, 1119496, 1259720

Offset: 1

Hugo Pfoertner, Nov 25 2023

nonn

See the description in the similar A363760 for more information.

			a(1) = 1: D(0,0) -> [0,0];
a(2) = 8: [1,0] -> [1,1] -> [0,1] -> [-1,1] -> [-1,0] -> [-1,-1] -> [0,-1] -> [1,-1] -> [1,0];
a(3) = 12: [2,0] -> [2,1] -> [1,2] -> [0,2] -> [-1,2] -> [-2,1] -> [-2,0] -> [-2,-1] -> [-1,-2] -> [0,-2] -> [1,-2] -> [2,-1] -> [2,0].
List of start points and corresponding cycle lengths:
    y   0  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
   x \------------------------------------------------------------------
   0 |  1  8  12   8   8   8   8   8   8  25   8   8   8   8   8  24   8
   1 |  8  8  12   8   8   8   8   8   8 154   8   8   8   8   8  24   8
   2 | 12 12   8   8   8   8   8  25  25 154 154   8   8   8   8   8  24
   3 |  8  8   8   8   8   8  25  25   8   8 154 154 154 154   8   8   8
   4 |  8  8   8   8   8   8   8  25   8   8 154   8   8   8 154   8   8
   5 |  8  8   8   8   8   8   8 154 154 154 154   8   8   8 154   8 152
   6 |  8  8   8   8   8   8   8  25   8   8 154   8   8   8 154 152   8
   7 |  8  8  25  25  25  25 154   8   8   8   8 154 154 154   8 152   8
   8 |  8  8  25   8   8 154   8   8   8   8   8   8   8   8   8 152   8
   9 |154 25 154   8   8 154 154   8   8   8   8   8   8   8   8 152   8
  10 |  8  8 154 154 154 154 154   8   8   8   8  24  24  24   8 152   8
  11 |  8  8   8 154   8   8   8 154   8   8  24   8   8   8  24 152   8
  12 |  8  8   8 154   8   8   8 154   8   8  24   8   8   8  24   8 152
  13 |  8  8   8 154   8   8   8 154   8   8  24   8   8   8  24   8   8
  14 |  8  8   8   8 154 154 154   8   8   8   8  24  24  24   8   8   8
  15 | 24 24   8   8   8   8 152 152 152 152 152 152   8   8   8   8  24
  16 |  8  8  24   8   8 152   8   8   8 152   8   8 152   8   8  24   8

Hugo Pfoertner, Examples of starting points for all known cycle lengths, December 2023.
Hugo Pfoertner, Visualization of some selected orbits with lengths from L=24 to L=918330056, December 2023.

Cf. A307110, A363760, A367150, A367894.

\\ It is assumed that the PARI program from A367150 has been loaded and the functions defined there are available.
cycle(v) = {my (n=1, w=BijectionD(v)); while (w!=v, n++; w=BijectionD(w)); n};
a367146(rmax=205) = {my (L=List()); for (x=0, rmax, for(y=x, rmax, my(c=cycle([x, y])); if(setsearch(L, c)==0, listput(L, c); listsort(L, 1)))); L};
a367146() \\ produces terms up to a(18)=1624 in about 5 minutes run time.

A367148 Cycle lengths obtained by repeated application of the strip bijection for the triangular lattice described in A367147.

Original entry on oeis.org

1, 10, 12, 36, 37, 56, 60, 72, 84, 110, 120, 154, 156, 168, 192, 278, 370, 398, 444, 492, 516, 564, 600, 614, 660, 924, 961, 1114, 1128, 1164, 1500, 1574, 1668, 1786, 2052, 2076, 2100, 2220, 2336, 2388, 2604, 2952, 3300, 3456, 3612, 3684, 3924, 4548, 4692, 4882, 4968

Offset: 1

Hugo Pfoertner, Nov 11 2023

nonn

The repeated application of the bijection function Q described in A367147, which maps a pair of triangular coordinates [i,j] to an image point [m,n], returns to the starting point after a number of steps dependent on the starting point. One mapping step leads to a location that approximately corresponds to a rotation of Pi/6, so that often, but not always, the lengths of the orbits created are multiples of 12. The situation is very similar to that described in the comment to A363760 for the analogous process applied to the square grid. As the lengths of the cycles increase, remarkable self-similar structures emerge; see the visualization of a cycle with a length L > 6*10^8.

			a(1) = 1: Starting point [0, 0] trivially mapped to [0, 0]; Q([0, 0]) -> [0, 0], Q([1, 0]) -> [1, 0]. Points exactly mapped to rotated location.
a(2) = 10: [2,0] -> [3,-2] -> [2,-3] -> [1,-3] -> [-1,-2] -> [-2,0] -> [-3,2] -> [-2,3] -> [-1,3] -> [1,2] -> [2, 0];
a(3) = 12: [3,0] -> [4,-2] -> [4,-4] -> [2,-5] -> [-1,-4] -> [-3,-2] -> [-4,0] -> [-5,2] -> [-5, 4] -> [-3,5] -> [0,4] -> [2,2] -> [3,0].
.
List of triangular coordinates [i, j] of start points and corresponding cycle lengths:
.
     j  0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
   i \-------------------------------------------------------------------
   0 |  1   1  10  10  12  12  56  12 110  12  12  12  12 278  12  12  12
   1 |  1  10  10  12  12  12  56  12  12 110  12  12  37 278  12  12 278
   2 | 10  10  12  12  56  56  12 110  12 110  37 278 278  12 278  12 278
   3 | 12  12  12  12  12  56  12 110  12 110  37  12 278 278 278  12  60
   4 | 12  12  12  56  12 110  12 110  12  37 278  12 278  12  60  12  12
   5 | 12  56  56  56  12 110  12  12 110  37 278  12 278  12  12  60  12
   6 | 12  56  12 110  12  12  12  37 278 278 278 278  12  60  12  60  12
   7 | 12 110  12  12 110  12  12  12 278  12  12 278  12  60  12  12  60
   8 | 12  12 110  12 110  37 278  37  12  12  12 278  12  12  60  12 398
   9 |110  12 110  12 110  37 278 278  12  12  12  12 278  12 398  12 398
  10 | 12  12 110  37  12 278  12 278  12  12 278  12 398 398 398  12  12
  11 | 12  37  37 278  12 278 278  12 278  12 278  12 398  12  12  12  12
  12 | 12 278 278 278  12  12 278  12 278  12 398  12  12  12  12  12  72
  13 | 37 278  12 278 278  12  60  12  60  12 398 398  12  12  72  36  72
  14 | 12  12 278  12  60  12  60  12  12 398  12  12  12  36  36  12  12
  15 | 12  12 278  12  60  12  12  60  12 398  12  12  72  72  12  12  12
  16 | 12  12 278  12  12  60  12  60  12 398  12  12 398  72  12  12  72

Klaus Nagel, Illustration of cycle lengths; points that belong to cycles of the same length are shown with the same color. Randomly selected region in grid.
Hugo Pfoertner, Visualization of orbits with L <= 1500.
Hugo Pfoertner, Orbit of length 617818092.

Cf. A003136, A307110, A363760, A367147, A367149.

\\ uses mapping function Q defined in PARI program of A367147
cycle(v) = {my (n=1, w=Q(v)); while (w!=v, n++; w=Q(w)); n};
L = List(); \\ global list to support repeated calls of function a367148
a367148(x10min=2, x10max=3, nrep=10000) = {for (n10=x10min, x10max, my (rmax=10^n10); for (n=1, nrep, my (x=random(rmax), y=random(rmax), c=cycle([x, y])); if(setsearch(L, c)==0, print1([c,x,y],", "); listput(L, c); listsort(L, 1)))); L};
\\ De-activate print to avoid output of starting points
a367148(2,3) \\ usually sufficient to get all terms <= 1500, repeat and increase nrep for confirmation; no shortcut for efficient systematic selection of starting points is known.

cp's OEIS Frontend

A307110 Index of matching grid point in the bijection between two infinite quadratic grids with one grid rotated by Pi/4 around the common point (0,0), using an enumeration of the grid points by A305575 and A305576.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A367146 Cycle lengths obtained by repeated application of the distance-minimizing variant of the strip bijection for the square lattice described in A367150.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A367148 Cycle lengths obtained by repeated application of the strip bijection for the triangular lattice described in A367147.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A367893 Length of cycles obtained by repeated application of the strip bijection for the square lattice (A307110), sorted by increasing minimum radius visited by any cycle of this length.

Views

Author

Keywords

Links

Crossrefs