A367148 -id:A367148 - cp's OEIS frontend

A363760 Cycle lengths obtained by repeated application of Klaus Nagel's strip bijection, as described in A307110.

1, 8, 9, 10, 40, 72, 106, 218, 256, 408, 424, 872, 1178, 2336, 2522, 2952, 4712, 10088, 13290, 26648, 28906, 33784, 53160, 115624, 150842, 303784, 330138, 385624, 603368, 1320552, 1716170, 3462216, 3765322, 4397144, 6864680, 15061288, 19543834, 39454792, 42921274, 50118936, 78175336, 171685096

Offset: 1

Hugo Pfoertner, Jun 26 2023

nonn

Description provided by Klaus Nagel: (Start)
The strip bijection s (A307110) maps a point P[i,j] from a Z X Z grid to Q[u,v] taken from a second grid obtained from the first one by a rotation by Pi/4 around the origin. The coordinates [i,j] and [u,v] refer to the respective grids. If [u,v] also are considered as coordinates of the first grid, the mapping [i,j] --> [u,v] establishes a permutation of the grid points of Z X Z.
Cycles of this permutation are evaluated; the sequence shows the occurring cycle lengths L.
Q[u,v] is located close to P[i,j]. Changing the reference to the other grid causes a rotation by Pi/4. Hence after eight permutation steps any point should return to the vicinity of its starting position. (End)
Therefore the provided visualizations also include graphs showing only every 8th point for cycles with L divisible by 8.
Examples of cycles with lengths > 10^9 are L = 2536863994 for the starting position [1761546, 1379978], L = 5574310746 for start [5207814, 6746677], and L = 6508768664 for start [7983336, 8380845].

			a(1) = 1: p(0, 0) -> [0, 0], p(1, 0) -> [1, 0]. Points mapped onto themselves.
a(2) = 8: [0, 1] -> [-1, 1] -> [-2, 0] -> [-1, -1] -> [0, -1] -> [1, -1] -> [2, 0] -> [1, 1] ->  [0, 1].
a(3) = 9: [1, 6] -> [-3, 5] -> [-6, 2] -> [-6, -2] -> [-3, -5] -> [1, -6] -> [5, -4] -> [6, 0] -> [5, 4] -> [1, 6].
a(4) = 10: [0, 2] -> [-1, 2] -> [-2, 1] -> [-2, -1] -> [-1, -2] -> [0, -2] -> [1, -2] -> [2, -1] -> [2, 1] -> [1, 2] -> [0, 2].
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  10   8   8 40   8   8   8  40   8   8 106   8   8 40  8
   1 | 1   8  10   8   8 40   9  40   8   8 106  40 106   8   8 40  8
   2 | 8  10   8   8   8  8   8   8   8   8  40 106   8   8   8  8 40
   3 | 8   8   8   8  40  9   8   8   8   8   8   8   8 106   8  8  8
   4 | 8   8   8  40   8 40   8   8   8   8   8   8   8   8 106  8  8
   5 | 8  40   8  40   9  8   8   8   8   8   8   8   8   8 106  8  8
   6 | 9  40   9   8   8 40   8  40 106  40 106   8   8   8 106 72  8
   7 | 8   8   8   8   8  8   8   8  40 106   8 106   8 106   8  8 72
   8 |40   8   8   8   8  8  40 106   8 106   8   8   8   8   8  8  8
   9 | 8   8   8   8   8  8 106  40 106   8   8   8   8   8   8  8  8
  10 | 8  40 106   8   8  8   8   8   8   8   8  40   8  40   8  8 72
  11 |40 106  40   8   8  8   8 106   8   8  40   8   8   8  40 72  8
  12 | 8 106   8 106   8  8   8 106   8   8  40   8   8   8  40  8  8
  13 | 8   8   8 106   8  8   8 106   8   8  40   8   8   8  40  8  8
  14 | 8   8   8   8 106  8 106   8   8   8   8  40   8  40   8  8  8
  15 | 8  40   8   8   8  8   8  72   8   8  72   8   8   8   8  8 40
  16 | 8   8  40   8   8  8  72   8   8   8   8  72   8   8   8 40  8
.
a(9) = 256: See links to animated visualizations.

Hugo Pfoertner, Animated visualization of cycle with L=256, all visited points shown.
Hugo Pfoertner, Animated visualization of cycle with L=256, every 8th visited point shown.
Hugo Pfoertner, Visualization of all terms from L=40 to L=53160. Zoom in to see details.
Hugo Pfoertner, Illustration of a(24) = 115624.
Hugo Pfoertner, Illustration of a(25) = 150842.
Hugo Pfoertner, Illustration of a(26) = 303784.
Hugo Pfoertner, Illustration of a(27) = 330138.
Hugo Pfoertner, Illustration of a(28) = 385624.
Hugo Pfoertner, Illustration of a(29) = 603368.
Hugo Pfoertner, Illustrations of a cycle of length 6508768664, including zoom images of the self-similar path details, December 2023.
Hugo Pfoertner, Examples of starting points for all known cycle lengths, July 2023.

Cf. A362955, A362956, A367146, A367893.

Cf. A367148 (analog of this sequence, but for the triangular lattice).

C=cos(Pi/8); S=sin(Pi/8); T=S/C; \\ Global constants
\\ The mapping function p
\\ PARI's default precision of 38 digits is sufficient up to abs({x,y})<10^17
p(i,j) = {my (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};
\\ cycle length
cycle(v) = {my (n=1, w=p(v[1],v[2])); while (w!=v, n++; w=p(w[1],w[2])); n};
a363760 (rmax) = {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};
a363760(500) \\ takes a few minutes, terms up to a(19), check completeness of list with larger rmax

A367147 Index of matching grid point in the bijection between two infinite triangular grids with one grid rotated by Pi/6 around the common point (0,0), using an enumeration of the grid points by A307014 and A307016.

Original entry on oeis.org

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

Offset: 0

Klaus Nagel and Hugo Pfoertner, Nov 06 2023

nonn

The methods used to achieve a distance-limited bijection of the points of two square grids (see A307110) are applied here to triangular grids. The two grids, which are rotated by 30 degrees = Pi/6 from each other, are assigned the colors red and blue to distinguish them, which are also used in the illustrations. The blue triangular grid is turned clockwise by 15 degrees = Pi/12, all points are lined up on parallel lines with inclination Pi/12 towards the vertical axis. These are called blue lines. The vertical distance between adjacent points is cos(Pi/12). The same is done for the red grid with a CCW rotation of Pi/12. The whole plane is divided into stripes with a width of cos(Pi/12) ~= 0.9659. Every blue line and every red line contains exactly one grid point of its color in each stripe. The blue and red lines alternately intersect the horizontal centerline of a stripe. The distance between two intersections of the same color is d = sqrt(3)/(2*cos(Pi/12)). The bijection maps the section of a blue line in a stripe to the section of the unique red line, that intersects the centerline less than d/2 away. The grid points on these two line sections are the partners of the tile bijection.
While the method described only finds a minimum of the maximum distance of approximately 0.9659 by assigning the bijection partners using tiles, applying the Hopcroft-Karp algorithm to the bipartite graph corresponding to a sufficiently large section of the two infinite grids achieves significantly lower maximum distances. We conjecture that an upper bound for the maximum distance is sqrt(2)/2~=0.7071. See the corresponding link.
A method that reduces the maximal occurring bijection distance to its conjectured minimum, and only requires local rearrangements, as described for the square grids in A307731, is currently not known in the present case of the triangular grids.

			   n  A307014(n)        Bijection partner
   |  |  A307016(n)     in rotated grid
   |  |  |                          rotated by Pi/6
   |  |  |   x    y     i  j  a(n)   u      v   Distance([x,y],[u,v])
   0  0  0  0.0  0.0    0  0   0    0.0    0.0  0.0
   1  1  0  1.0  0.0    1  0   1    0.866  0.5  0.51764
   2  0  1  0.5  0.866  0  1   2    0.0    1.0  0.51764
   3 -1  1 -0.5  0.866 -1  1   3   -0.866  0.5  0.51764
   4 -1  0 -1.0  0.0   -1  0   4   -0.866 -0.5  0.51764
   5  0 -1 -0.5 -0.866  0 -1   5    0.0   -1.0  0.51764
   6  1 -1  0.5 -0.866  1 -1   6    0.866 -0.5  0.51764
   7  1  1  1.5  0.866  2 -1  12    1.732  0.0  0.89658
   8 -1  2  0.0  1.732  0  2  14    0.0    2.0  0.26795
   9 -2  1 -1.5  0.866 -2  2  15   -1.732  1.0  0.26795
  10 -1 -1 -1.5 -0.866 -2  1   9   -1.732  0.0  0.89658
  11  1 -2  0.0 -1.732  0 -2  17    0.0   -2.0  0.26795
  12  2 -1  1.5 -0.866  2 -2  18    1.732 -1.0  0.26795
  13  2  0  2.0  0.0    3 -2  29    2.598 -0.5  0.77955
  14  0  2  1.0  1.732  1  1   7    0.866  1.5  0.26795
  15 -2  2 -1.0  1.732 -1  2   8   -0.866  1.5  0.26795

Klaus Nagel, Stripes and tiles used for mapping.
Hugo Pfoertner, Numbering of points in red and blue grid.
Hugo Pfoertner, Notes on the minimum achievable bijection distance, Nov 2023.
Hugo Pfoertner, PARI program.
Wikipedia, Hopcroft-Karp algorithm

Cf. A307014, A307016, A307110, A307731, A367148.

\\ See linked file; function call to output data:
a367147(70)

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

Original entry on oeis.org

1, 10, 12, 56, 110, 37, 278, 60, 398, 72, 36, 154, 1114, 370, 2336, 168, 614, 444, 516, 1786, 192, 660, 600, 1128, 84, 156, 120, 2952, 492, 1574, 961, 3456, 2100, 10790, 564, 2604, 12110, 10440, 1500, 3924, 4882, 25570, 1668, 16524, 1164, 12876, 9610, 9420, 22906, 7008, 10716

Offset: 1

Hugo Pfoertner, Dec 08 2023

nonn

			See the linked file with list of points at minimum radius.

Hugo Pfoertner, Examples of points at minimum radius.
Hugo Pfoertner, Illustration of all cycles with minimum radius up to 700. Zoom into the images to see details, e.g., the green line that connects every 12th point visited.

A permutation of A367148.

Cf. A367147.

\\ Bijection function Q provided in A367147
cycle(v, upto=oo)= {my (n=1, w=Q(v)); while (w!=v, n++; if (n>upto,return(0)); w=Q(w)); n};
\\ upto can be used to ignore longer cycles
a367149(Points, upto=oo) =
{ my (L=LL=List());
  for (n=1, #Points,
       my (c=cycle(Points[n],upto));
       if (c>0 && setsearch(LL,c)==0,
       \\ deactivate print to mute diagnostic printout
       print ([c, Points[n], sqrt(Points[n][1]^2 + Points[n][2]^2 + Points[n][1] *Points[n][2])]);
       listput(L,c);
       listput(LL,c); listsort(LL,1))
      ); L};
\\ Function a307014_16 provided in A307014
\\ Enumeration of grid points of triangular lattice by increasing radius
Plist = a307014_16(120,-46); \\ creates list of 52218 grid points
a367149(Plist) \\ all cycles having a point with R < 120 (a(1)-a(28)); takes 2 to 4 minutes

cp's OEIS Frontend

A363760 Cycle lengths obtained by repeated application of Klaus Nagel's strip bijection, as described in A307110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A367147 Index of matching grid point in the bijection between two infinite triangular grids with one grid rotated by Pi/6 around the common point (0,0), using an enumeration of the grid points by A307014 and A307016.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI