Étant donné un entier gaussien $a+bi$ où $a$ , $b$ sont des entiers et $i = \exp\left(\pi i/2\right)$ est l'unité imaginaire, retournez l'entier d'Eisenstein le plus proche (wrt à la distance euclidienne) $k+l\omega$ où $k$ , $l$ sont entiers et $\omega = \exp(2\pi i/3) = (-1+i\sqrt{3})/2$.

Contexte

Il est probablement assez évident que chaque entier gaussien peut uniquement être écrit comme $a+bi$ avec $a$ , $b$ entiers. Ce n'est pas si évident, mais néanmoins vrai: tout entier d'Eisenstein peut uniquement être écrit comme $k+l\omega$ avec $k$ , $l$ entiers. Ils forment tous les deux un module $\mathbb{Z}$ dans les nombres complexes et sont tous les deux des p-èmes nombres cyclotomiques pour $p=2$ ou $3$ respectivement. Notez que $3+2i \neq 3+2\omega$

_{^{Source: commons.wikimedia.org}}

Détails

• Dans le cas où le nombre complexe donné a deux ou trois points les plus proches, n'importe lequel d'entre eux peut être retourné.

• Le nombre complexe est donné en coordonnées rectangulaires (base $(1,i)$ ), mais autre que celui dans n'importe quel format pratique comme (A,B)ou A+Biou A+B*1jetc.

• L'entier d'Eisenstein doit être retourné en tant que coordonnées de la base $(1,\omega)$ mais autre que celui dans n'importe quel format pratique comme (K,L)ou K+Lωou K+L*1ωetc.

Exemples

Tous les entiers réels doivent évidemment être à nouveau mappés aux entiers réels.

  6,14 -> 14,16
  7,16 -> 16,18
-18,-2 ->-19,-2
 -2, 2 -> -1, 2
 -1, 3 -> 1, 4

APL (Dyalog Extended) , 16 octets ^SBCS

⎕0+⌈3÷⍨1 2×⌊⎕×√3

Essayez-le en ligne!

Un programme complet qui prend yensuite xde l'entrée standard et imprime un vecteur d'entiers à 2 éléments.

Comment ça marche: les mathématiques

Tout d'abord, notez que tout entier gaussien sera placé sur la diagonale verticale d'un diamant, avec le point $Z$ placé à$(x,\sqrt3y)$pour un entier$x,y$.

      + W
     /|\
    / | \
   /  |  \
  /   + X \
 /    |    \
+-----|-----+V
 \    |    /
  \   + Y /
   \  |  /
    \ | /
     \|/
      + Z

Sur la figure, $\overline{WZ}=\sqrt3$ et$\overline{WX}=\overline{XY}=\overline{YZ}=\overline{XV}=\overline{YV}=\frac{1}{\sqrt3}$ . Donc, étant donné la position verticale d'un point, nous pouvons identifier le point d'Eisenstein le plus proche comme suit:

$$\text{Given a point }P \in \overline{WZ}, \\ \left\{ \begin{array}{c} P \in \overline{WX} \implies \text{the nearest point is } W \\ P \in \overline{XY} \implies \text{the nearest point is } V \\ P \in \overline{YZ} \implies \text{the nearest point is } Z \end{array} \right.$$

$P$$P$$h$$Z$$x$ axe des .

$$h = \lfloor P.y \div \sqrt3 \rfloor$$

$Z$ sont

$$Z.x_E = P.x+h, \quad Z.y_E = 2h$$

$\overline{WX},\overline{XY},\overline{YZ}$ $P$$w$ comme suit:

$$w = \lfloor P.y \times \sqrt3 \rfloor \% 3$$

$w = 0, 1, 2$ correspond to $\overline{YZ},\overline{XY},\overline{WX}$ respectively. Finally, the nearest Eisenstein point of $P$ (which is one of $Z$, $V$, or $X$) can be calculated as:

$$P_E.x_E = P.x+h+\lceil \frac{w}2 \rceil, \quad P_E.y_E = 2h+w$$

Using the identities for $h$ and $w$, we can further simplify to:

$$y' = \lfloor P.y \times \sqrt3 \rfloor, \quad P_E.x_E = P.x+\lceil y' \div 3 \rceil, \quad P_E.y_E = \lceil 2y' \div 3 \rceil$$

How it works: the code

⎕0+⌈3÷⍨1 2×⌊⎕×√3
           ⌊⎕×√3  ⍝ Take the first input (P.y) and calculate y'
   ⌈3÷⍨1 2×       ⍝ Calculate [ceil(y'/3), ceil(2y'/3)]
⎕0+  ⍝ Take the second input(P.x) and calculate [P.x+ceil(y'/3), ceil(2y'/3)]

JavaScript (ES6), 112 bytes

(a,b,l=b/Math.pow(.75,.5),k=a+l/2,f=Math.floor,x=k-(k=f(k)),y=l-(l=f(l)),z=x+y>1)=>[k+(y+y+z>x+1),l+(x+x+z>y+1)]

ES7 can obviously trim 9 bytes. Explanation: k and l initially represent the floating-point solution to k+ωl=a+ib. However, the coordinates needed to be rounded to the nearest integer by Euclidean distance. I therefore take the floor of k and l, then perform some tests on the fractional parts to determine whether incrementing them would result in a nearer point to a+ib.

MATL, 39 38 35 bytes

t|Ekt_w&:2Z^tl2jYP3/*Zeh*!sbw6#YkY)

Input format is 6 + 14*1j (space is optional). Output format is 14 16.

Try it online!

Explanation

The code first takes the input as a complex number. It then generates a big enough hexagonal grid in the complex plane, finds the point that is closest to the input, and returns its Eisenstein "coordinates".

t         % Take input implicitly. This is the Gauss number, say A. Duplicate
|Ek       % Absolute value times two, rounded down
t_        % Duplicate and negate
w&:       % Range. This is one axis of Eisenstein coordinates. This will generate
          % the hexagonal grid big enough
2Z^       % Cartesian power with exponent 2. This gives 2-col 2D array, say B
t         % Duplicate
l         % Push 1
2jYP3/*   % Push 2*j*pi/3
Ze        % Exponential
h         % Concatenate. Gives [1, exp(2*j*pi/3)]
*         % Multiply by B, with broadcast.
!s        % Sum of each row. This is the hexagonal grid as a flattened array, say C
bw        % Bubble up, swap. Stack contains now, bottom to top: B, A, C
6#Yk      % Index of number in C that is closest to A
Y)        % Use as row index into B. Implicitly display

Haskell, 128 bytes

i=fromIntegral;r=[floor,ceiling];a!k=(i a-k)**2;c(a,b)|l<-2*i b/sqrt 3,k<-i a+l/2=snd$minimum[(x k!k+y l!l,(x k,y l))|x<-r,y<-r]

Try it online!

For input Gaussian integer (a,b), convert it into Eisenstein coordinates, floor and ceil both components to get four candidates for closest Eisenstein integer, find the one with minimal distance and return it.

Tcl, 124 116 106 bytes

{{a b f\ int(floor(2*$b/3**.5)) {l "[expr $f+(1-$f%2<($b-$f)*3**.5)]"}} {subst [expr $l+$a-($f+1)/2]\ $l}}

Try it online!

This is somewhat inspired by the three-year old post from @Neil

The floor function returns the corner of the rhombus whose edges are the vectors 1 and $\omega$. With respect to this rhombus, the Gaussian integer lies on the perpendicular bi-sector of either the top (if l is even) or bottom (if l is odd). This is important because it means that either the lower left corner or the upper right corner will be an acceptable solution. I compute k for the lower left corner, and do one test to see if the Gaussian integer lies above or below the diagonal separating the two corners; I add 1 to k when above the diagonal, and I do likewise for l.

Enregistrement de 10 octets en utilisant le "signe du produit croisé vxd de la diagonale d avec le vecteur v joignant le coin inférieur droit et (a, b)" comme test pour quel côté de la diagonale se situe le point.

Burlesque , 24 octets

pe@3r@2././J2./x/.+CL)R_

Essayez-le en ligne!

Je suis sûr que cela peut être plus court. Entrée lue commea b

pe      # Parse input to two ints
@3r@2./ # sqrt(3)/2
./      # Divide b by sqrt(3)/2
J2./    # Duplicate and divide by 2
x/.+    # swap stack around and add to a
CL      # Collect the stack to a list
)R_     # Round to ints

05AB1E , 13 octets

Réponse APL du port de Bubbler

3t*ïx‚3/îR΂+

Essayez-le en ligne!

L'entrée et la sortie sont toutes les deux y d'abord, x secondes.