fundo

Uma grade triangular é uma grade formada pela disposição regular do plano com triângulos equilaterais de comprimento lateral 1. A figura abaixo é um exemplo de uma grade triangular.

Um ponto de rede triangular é um vértice de um triângulo que forma a grade triangular.

A origem é um ponto fixo no plano, que é um dos pontos da estrutura triangular.

Desafio

Dado um número inteiro não negativo n, encontre o número de pontos de rede triangular cuja distância euclidiana da origem é menor ou igual a n.

Exemplo

A figura a seguir é um exemplo de n = 7(mostrando apenas uma área de 60 graus por conveniência, com o ponto A sendo a origem):

Casos de teste

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

Dica : esta sequência não é OEIS A003215 .

Regras

Aplicam -se regras padrão para o código-golfe . A finalização mais curta vence.

Inclua como você resolveu o desafio em sua inscrição.

Python 2 , 43 bytes

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

Experimente online!

Isso é magia negra.

Oferecendo 250 representantes para uma prova de redação. Vejaa resposta de Lynnpara uma prova e explicação.

Haskell , 48 bytes

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

Experimente online!

Usa a fórmula "magia negra" do 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$$

Uma prova de sua correção e uma explicação de como o xnor conseguiu expressá-lo em 43 bytes de Python, podem ser encontradas aqui .

Resumindo a história: contamos inteiros de Eisenstein da norma , fatorando N = ( x + y ω ) ( x + y ω ∗ ) em números primos de Eisenstein e contando quantas soluções para ( x , y ) saem da fatoração. Reconhecemos o número de soluções como sendo igual a$1 \le N \le n^2$$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)))$$

e aplique um truque inteligente para facilitar a computação de todos os números inteiros entre e n $1$$n^2$ uma só vez. Isso produz a fórmula acima. Por fim, aplicamos alguma mágica em golfe do Python para terminar com a solução realmente minúscula encontrada pelo xnor.

Wolfram Language (Mathematica) , 53 51 50 bytes

^{-1 byte graças a @miles}

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

Experimente online!

Quão?

Em vez de pensar nisso:

Pense assim:

Então aplicamos a matriz [[sqrt(3)/2, 0], [1/2, 1]]de transformação para transformar a segunda figura na primeira.

Então, devemos encontrar o círculo na grade triangular em termos de coordenadas cartesianas.

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

Então, encontramos pontos de rede x, ytais quex^2 + x y + y^2 <= r^2

Por exemplo, com r = 3:

Wolfram Language (Mathematica) , 48 bytes

Baseado no OEIS A004016 .

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

Experimente online!

CJam (24 bytes)

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

Este é um bloco anônimo (função) que pega um argumento na pilha e deixa o resultado na pilha. Conjunto de testes online . Observe que os dois casos maiores são muito lentos.

Explicação

alefalpha observou em um comentário sobre a pergunta que

É a soma dos primeiros n ^ 2 + 1 termos de OEIS A004016

e a resposta do xnor implementa essa soma (embora eu não tenha certeza se a prova não publicada a usa explicitamente) como

$$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$$

Minha prova de correção dessa fórmula é baseada em algumas informações obtidas no link OEIS dos alefalpha:

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

para o qual a referência relevante é o artigo de Hirschhorn. Uma prova elementar é possível usando nada além de uma compreensão básica de números complexos (raízes de unidade de cubo, magnitude), o conceito de funções geradoras, a derivada de$x^a$e a regra da cadeia de diferenciação. Em resumo, primeiro provamos, a partir dos primeiros princípios, a identidade do produto triplo Jacobi

$$\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$$ That then bootstraps a proof that $$\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}}$$ where $\omega$ is a primitive cube root of unity. The final big step is to use this to show that $$\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)$$

Code dissection

{          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:@+:

Try it online!

Based on JungHwan Min's method.

Explanation

[:+/@,*:>:(*++&*:)"{~@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}×⍨

Try it online!

tribute to xnor's and lynn's answers

the last test is commented because it needs more memory, e.g. MAXWS=200M in the env

Jelly, 14 bytes

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

Uses @JungHwanMin's method.

Try it online!

Jelly,  15  13 bytes

-2 thanks to Dennis (just increment the square to avoid concatenation of a zero; avoid head by using a post-difference modulo-slice rather than a pre-difference slice)

^{Uses the "black magic" method of honing in on the answer that was exposed by xnor in their Python answer, but uses iteration rather than recursion (and a little less calculation)}

²:Ѐ‘$Im3S×6C

A monadic link accepting a non-negative integer and returning a positive integer.

Try it online! Or see the test-suite.

How?

²:Ѐ‘$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

This is a port of @JungHwanMin's solution.

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))

Try it online!

---

Original answer (ES7), 70 bytes

Simply walks through the grid and counts the matching points.

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))

Try it online!

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 answer.

Try it online.

Pari/GP, 42 bytes

Using the built-in qfrep.

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

qfrep(q,B,{flag=0}): vector of (half) the number of vectors of norms from 1 to B for the integral and definite quadratic form q. If flag is 1, count vectors of even norm from 1 to 2B.

Try it online!

C# (Visual C# Interactive Compiler), 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);}

Try it online!

Same as everyone else, unfortunately. I know there's probably a better way of writing this, but declaring and calling a lambda at the same time in c# is not exactly something I do, well, ever. Though in my defense, I can't think of a good reason (outside code golf, of course) to do so. Still, if someone knows how you can do this, let me know and/or steal the credit, I guess.

Wolfram Language (Mathematica), 39 bytes

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

Try it online!

Using JungHwan Min's coordinate transformation and simply counting the solutions over the integers.

05AB1E, 15 bytes

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

Port of @JonathanAllans Jelly answer, which in turn is a derivative from @xnor's 'black magic' formula.

Try it online or verify all test cases.

Explanation:

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)