Fondo

Una cuadrícula triangular es una cuadrícula formada al enlosar el plano regularmente con triángulos equiláteros de longitud lateral 1. La siguiente imagen es un ejemplo de una cuadrícula triangular.

Un punto reticular triangular es un vértice de un triángulo que forma la cuadrícula triangular.

los origen es un punto fijo en el plano, que es uno de los puntos reticulares triangulares.

Reto

Dado un número entero no negativo n, encuentre el número de puntos reticulares triangulares cuya distancia euclidiana desde el origen es menor o igual quen .

Ejemplo

La siguiente figura es un ejemplo para n = 7(que muestra solo un área de 60 grados por conveniencia, siendo el punto A el origen):

Casos de prueba

Input | Output
---------------
    0 |       1
    1 |       7
    2 |      19
    3 |      37
    4 |      61
    5 |      91
    6 |     127
    7 |     187
    8 |     241
    9 |     301
   10 |     367
   11 |     439
   12 |     517
   13 |     613
   14 |     721
   15 |     823
   16 |     931
   17 |    1045
   18 |    1165
   19 |    1303
   20 |    1459
   40 |    5815
   60 |   13057
   80 |   23233
  100 |   36295
  200 |  145051
  500 |  906901
 1000 | 3627559

Sugerencia : esta secuencia no es OEIS A003215 .

Reglas

Reglas estándar para el código de golf . La presentación más corta gana.

Incluya cómo resolvió el desafío en su envío.

Python 2 , 43 bytes

f=lambda n,a=1:n*n<a/3or n*n/a*6-f(n,a+a%3)

Pruébalo en línea!

Esto es magia negra.

Ofreciendo 250 repeticiones para una prueba escrita. Veala respuesta de Lynnpara una prueba y explicación.

Haskell , 48 bytes

f n=1+6*sum[(mod(i+1)3-1)*div(n^2)i|i<-[1..n^2]]

Pruébalo en línea!

Utiliza la fórmula de "magia negra" de xnor:

$$f(n)=1+6\sum_{a=0}^\infty \left\lfloor \frac{n^2}{3a+1}\right\rfloor - \left\lfloor \frac{n^2}{3a+2}\right\rfloor$$

Aquí puede encontrar una prueba de su corrección y una explicación de cómo xnor logró expresarlo en 43 bytes de Python .

Larga historia corta: contamos los enteros de Eisenstein de la norma , factorizando N = ( x + y ω ) ( x + $1 \le N \le n^2$ ennúmeros primos de Eisensteiny contando cuántas soluciones para ( x , y ) salen de la factorización. Reconocemos que el número de soluciones es igual a$N = (x+y\omega)(x+y\omega^*)$$(x,y)$

$$6 \times ((\text{# of divisors of }N \equiv 1\space(\text{mod }3)) - (\text{# of divisors of }N \equiv 2\space(\text{mod }3)))$$

y aplique un truco inteligente para que sea realmente fácil de calcular para todos los enteros entre y n 2 a la vez. Esto produce la fórmula anterior. Finalmente, aplicamos un poco de magia de golf de Python para terminar con la solución realmente pequeña que xnor encontró.$1$$n^2$

Wolfram Language (Mathematica) , 53 51 50 bytes

^{-1 byte gracias a @miles}

Sum[Boole[x(x+y)+y^2<=#^2],{x,-2#,2#},{y,-2#,2#}]&

Pruébalo en línea!

¿Cómo?

En lugar de pensar en esto:

Piensa en esto, de esta manera:

Entonces aplicamos la matriz de transformación [[sqrt(3)/2, 0], [1/2, 1]] de transformación para transformar la segunda figura en la primera.

Luego, debemos encontrar el círculo en la cuadrícula triangular en términos de coordenadas cartesianas.

(sqrt(3)/2 x)^2 + (1/2 x + y)^2 = x^2 + x y + y^2

Entonces encontramos puntos de red x, ytales quex^2 + x y + y^2 <= r^2

Por ejemplo, con r = 3:

Wolfram Language (Mathematica) , 48 bytes

Basado en OEIS A004016 .

1+6Sum[DivisorSum[i,#~JacobiSymbol~3&],{i,#^2}]&

Pruébalo en línea!

CJam (24 bytes)

{_*_,f{)_)3%(@@/*}1b6*)}

Este es un bloque anónimo (función) que toma un argumento en la pila y deja el resultado en la pila. Conjunto de pruebas en línea . Tenga en cuenta que los dos casos más grandes son demasiado lentos.

Explicación

alephalpha señaló en un comentario sobre la pregunta que

Es la suma de los primeros n ^ 2 + 1 términos de OEIS A004016

$$f(n) = 1 + 6 \sum_{a=0}^\infty \left\lfloor\frac{n^2}{3a+1}\right\rfloor - \left\lfloor\frac{n^2}{3a+2}\right\rfloor$$

Mi prueba de exactitud de esa fórmula se basa en cierta información obtenida del enlace OEIS de alephalpha:

Gf: 1 + 6 * Suma_ {n> = 1} x ^ (3 * n-2) / (1-x ^ (3 * n-2)) - x ^ (3 * n-1) / (1- x ^ (3 * n-1)). - Paul D. Hanna, 03 jul 2011

$x^a$

$$\prod_{k=0}^\infty (1-q^{k+1})(1 + xq^{k+1})(1 + x^{-1}q^k) = \sum_{k\in \mathbb{Z}} q^{k(k+1)/2}x^k$$ Eso luego prueba una prueba de que $$\sum_{m,n \in \mathbb{Z}} \omega^{m-n} q^{m^2+mn+n^2} = \prod_{k=1}^\infty \frac{(1-q^k)^3}{1-q^{3k}}$$ dónde $\omega$es una raíz cúbica primitiva de la unidad. El gran paso final es usar esto para mostrar que $$\sum_{m,n \in \mathbb{Z}} q^{m^2+mn+n^2} = 1 + 6 \sum_{k \ge 0} \left(\frac{q^{3k+1}}{1-q^{3k+1}} - \frac{q^{3k+2}}{1-q^{3k+2}} \right)$$

Disección de código

{          e# Define a block. Stack: ... r
  _*       e#   Square it
  _,f{     e#   Map with parameter: invokes block for (r^2, 0), (r^2, 1), ... (r^2, r^2-1)
    )      e#     Increment second parameter. Stack: ... r^2 x with 1 <= x <= r^2
    _)3%(  e#     Duplicate x and map to whichever of 0, 1, -1 is equal to it (mod 3)
    @@/*   e#     Evaluate (r^2 / x) * (x mod 3)
  }
  1b6*     e#   Sum and multiply by 6
  )        e#   Increment to count the point at the origin
}

J , 27 bytes

[:+/@,*:>:(*++&*:)"{~@i:@+:

Pruébalo en línea!

Basado en el método de JungHwan Min .

Explicación

[:+/@,*:>:(*++&*:)"{~@i:@+:  Input: n
                         +:  Double
                      i:     Range [-2n .. 2n]
                  "{~        For each pair (x, y)
                *:             Square both x and y
              +                Add x^2 and y^2
             +                 Plus
            *                  Product of x and y
        >:                   Less than or equal to
      *:                     Square of n
     ,                       Flatten
  +/                         Reduce by addition

APL (Dyalog Classic) , 23 bytes

{1+6×+/-/⌊⍵÷1+3⊥¨⍳⍵2}×⍨

Pruébalo en línea!

homenaje a xnor's y lynn's respuestas

la última prueba se comenta porque necesita más memoria, por ejemplo, MAXWS=200Men el entorno

Jalea , 14 bytes

ḤŒR+²_×ʋþ`F½»ċ

Utiliza el método de @ JungHwanMin .

Pruébalo en línea!

Gelatina ,  15  13 bytes

-2 gracias a Dennis (solo incremente el cuadrado para evitar la concatenación de un cero; evite la cabeza utilizando un módulo de corte posterior a la diferencia en lugar de un corte previo a la diferencia)

^{Utiliza el método de "magia negra" para perfeccionar la respuesta que fue expuesta por xnor en su respuesta de Python , pero usa iteración en lugar de recursión (y un poco menos de cálculo)}

²:Ѐ‘$Im3S×6C

Un enlace monádico que acepta un entero no negativo y devuelve un entero positivo.

Pruébalo en línea! O vea el conjunto de pruebas .

¿Cómo?

²:Ѐ‘$Im3S×6C - Main Link: non-negative integer, n     e.g. 7
²             - square                                     49
     $        - last two links as a monad:
    ‘         -   increment                                50
  Ѐ          -   map across (implicit range of) right with:
 :            -     integer division                       [49,24,16,12,9,8,7,6,5,4,4,4,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0]
      I       - incremental differences                    [-25,-8,-4,-3,-1,-1,-1,-1,-1,0,0,-1,0,0,0,-1,0,0,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1]
       m3     - every third element                        [-25,-3,-1,0,0,-1,0,0,0,0,0,0,0,0,0,0,-1]
         S    - sum (vectorises)                           -31
          ×6  - multiply by six                           -186
            C - complement (1-X)                           187

JavaScript (ES6), 65 bytes

Este es un puerto de la solución de @ JungHwanMin .

f=(n,y=x=w=n*2)=>y-~w&&(x*x+x*y+y*y<=n*n)+f(n,y-=--x<-w&&(x=w,1))

Pruébalo en línea!

---

Respuesta original (ES7), 70 bytes

Simplemente camina por la cuadrícula y cuenta los puntos coincidentes.

f=(n,y=x=n*=2)=>y+n+2&&(x*x*3+(y-x%2)**2<=n*n)+f(n,y-=--x<-n&&(x=n,2))

Pruébalo en línea!

Java 8, 65 bytes

n->f(n,1)int f(int n,int a){return n*n<a/3?1:n*n/a*6-f(n,a+a%3);}

Port of @xnor 's Python 2 respuesta .

Pruébalo en línea.

Pari / GP , 42 bytes

Usando el incorporado qfrep.

n->1+2*vecsum(Vec(qfrep([2,1;1,2],n^2,1)))

qfrep (q, B, {flag = 0}): vector de (mitad) el número de vectores de normas de 1 a B para la forma cuadrática integral y definida q. Si el indicador es 1, cuente los vectores de la norma par de 1 a 2B.

Pruébalo en línea!

C # (compilador interactivo de Visual C #) , 68 bytes

n=>{int g(int x,int y)=>x*x<y/3?1:x*x/y*6-g(x,y+y%3);return g(n,1);}

Pruébalo en línea!

Igual que todos los demás, por desgracia. Sé que probablemente hay una mejor manera de escribir esto, pero declarar y llamar a una lambda al mismo tiempo en C # no es exactamente algo que hago, bueno, nunca. Aunque en mi defensa, no puedo pensar en una buena razón (fuera del código de golf, por supuesto) para hacerlo. Aún así, si alguien sabe cómo puede hacer esto, hágamelo saber y / o robe el crédito, supongo.

Wolfram Language (Mathematica) , 39 bytes

Length@Solve[x(x+y)+y^2<=#^2,Integers]&

Pruébalo en línea!

Usando la transformación de coordenadas de JungHwan Min y simplemente contando las soluciones sobre los enteros.

05AB1E , 15 bytes

nD>L÷¥ā3%ÏO6*±Ì

Puerto de la respuesta Jelly de @JonathanAllan , que a su vez es un derivado de la fórmula de 'magia negra' de @ xnor .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

n                # Square the (implicit) input-integer
 D>              # Duplicate it, and increase the copy by 1
   L             # Create a list in the range [1, input^2+1]
    ÷            # Integer divide input^2 by each of these integers
     ¥           # Take the deltas
      ā          # Push a list in the range [1, length] without popping the deltas itself
       3%        # Modulo each by 3
         Ï       # Only leave the values at the truthy (==1) indices
          O      # Take the sum of this list
           6*    # Multiply it by 6
             ±   # Take the bitwise NOT (-n-1)
              Ì  # And increase it by 2
                 # (after which the result is output implicitly)