tło

Trójkątny siatka jest siatką tworzą płaszczyznę płytki z regularnie trójkątów równobocznych o boku 1. Poniższy rysunek przedstawia przykład trójkątnej kratki.

Trójkątny punkt kratowy jest wierzchołkiem trójkąta tworzącego trójkątną siatkę.

Pochodzenie jest stałym punktem na płaszczyźnie, która jest jednym z trójkątnych punktów kratowych.

Wyzwanie

Biorąc pod uwagę nieujemną liczbę całkowitą n, znajdź liczbę trójkątnych punktów sieci, których odległość euklidesowa od początku jest mniejsza lub równa n.

Przykład

Poniższy rysunek jest przykładem n = 7(pokazujący dla wygody tylko obszar 60 stopni, z którego punktem początkowym jest punkt A):

Przypadki testowe

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

Wskazówka : Ta sekwencja nie jest OEIS A003215 .

Zasady

Obowiązują standardowe zasady gry w golfa kodowego . Najkrótsze zgłoszenie wygrywa.

W zgłoszeniu prosimy o uwzględnienie sposobu rozwiązania problemu.

Python 2 , 43 bajty

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

Wypróbuj online!

To jest czarna magia.

Oferowanie 250 powtórzeń za pisemny dowód. Zobaczodpowiedź Lynn,aby uzyskać dowód i wyjaśnienie.

Haskell , 48 bajtów

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

Wypróbuj online!

Wykorzystuje formułę „czarnej magii” 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$$

Dowód jego poprawności oraz wyjaśnienie, w jaki sposób xnor zdołał wyrazić to w 43 bajtach Pythona, można znaleźć tutaj .

Krótko mówiąc: liczymy liczby całkowite Eisensteina z normy , dzieląc na liczby pierwsze Eisensteina i licząc, ile rozwiązań dla pochodzą z faktoryzacji. Uznajemy liczbę rozwiązań za równą$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)))$$

i zastosuj sprytną sztuczkę, aby to naprawdę łatwo obliczyć dla wszystkich liczb całkowitych od do jednocześnie. Daje to powyższy wzór. Wreszcie, stosujemy trochę magii golfa w Pythonie, aby uzyskać naprawdę małe rozwiązanie, które znaleziono xnor.n $1$$n^2$

Wolfram Language (Mathematica) , 53 51 50 bajtów

^{-1 bajt dzięki @miles}

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

Wypróbuj online!

W jaki sposób?

Zamiast myśleć w ten sposób:

Pomyśl o tym w ten sposób:

Dlatego stosujemy macierz [[sqrt(3)/2, 0], [1/2, 1]]transformacji, aby przekształcić drugą cyfrę na pierwszą.

Następnie musimy znaleźć okrąg w trójkątnej siatce pod względem współrzędnych kartezjańskich.

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

Tak więc znajdujemy x, ytakie punkty siatkix^2 + x y + y^2 <= r^2

Na przykład z r = 3:

Wolfram Language (Mathematica) , 48 bajtów

Na podstawie OEIS A004016 .

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

Wypróbuj online!

CJam (24 bajty)

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

Jest to anonimowy blok (funkcja), który pobiera jeden argument ze stosu i pozostawia wynik na stosie. Zestaw testów online . Zauważ, że dwa największe przypadki są zbyt wolne.

Wyjaśnienie

alephalpha zauważył w komentarzu do pytania, że

Jest to suma pierwszych n ^ 2 + 1 warunków OEIS A004016

a odpowiedź xnora implementuje tę sumę (chociaż nie jestem pewien, czy ich nieopublikowany dowód używa jej jawnie) jako

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

Mój dowód poprawności tej formuły opiera się na pewnych informacjach uzyskanych z linku OEIS Alephalpha:

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 lipca 2011 r

dla których odnośnikiem jest artykuł Hirschhorna. Elementarny dowód jest możliwy przy użyciu wyłącznie podstawowego zrozumienia liczb zespolonych (pierwiastki sześcianu jedności, wielkości), koncepcji generowania funkcji, pochodnej i reguły łańcucha różnicowania. Podsumowując, na podstawie pierwszych zasad najpierw potwierdzamy tożsamość potrójnego produktu Jacobi To następnie ładuje dowód, że gdzie jest pierwotnym pierwiastkiem kostki jedności. Ostatnim dużym krokiem jest użycie tego, aby to pokazać$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$$ $$\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}}$$ $\omega$ $$\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)$$

Rozbiór kodu

{          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 bajtów

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

Wypróbuj online!

Na podstawie metody JungHwan Min .

Wyjaśnienie

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

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

Wypróbuj online!

hołd XNOR użytkownika i Lynn odpowiedzi

ostatni test jest komentowany, ponieważ potrzebuje więcej pamięci, np. MAXWS=200Mw env

Galaretka , 14 bajtów

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

Wykorzystuje metodę @ JungHwanMin .

Wypróbuj online!

Galaretka ,  15  13 bajtów

-2 dzięki Dennisowi (wystarczy zwiększyć kwadrat, aby uniknąć konkatenacji zera; unikaj głowy, używając plastra modulo po różnicy zamiast plastra przed różnicą)

^{Używa metody „czarnej magii” do szlifowania odpowiedzi, która została ujawniona przez xnor w odpowiedzi Pythona , ale używa iteracji zamiast rekurencji (i trochę mniej obliczeń)}

²:Ѐ‘$Im3S×6C

Łącze monadyczne akceptuje nieujemną liczbę całkowitą i zwraca dodatnią liczbę całkowitą.

Wypróbuj online! Lub zobacz pakiet testowy .

W jaki sposób?

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

To jest port rozwiązania @ 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))

Wypróbuj online!

---

Oryginalna odpowiedź (ES7), 70 bajtów

Po prostu przechodzi przez siatkę i liczy pasujące punkty.

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

Wypróbuj online!

Java 8, 65 bajtów

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 odpowiedzi @xnor na Python 2 .

Wypróbuj online.

Pari / GP , 42 bajty

Korzystanie z wbudowanego qfrep.

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

qfrep (q, B, {flag = 0}): wektor (połowy) liczby wektorów norm od 1 do B dla integralnej i określonej postaci kwadratowej q. Jeśli flaga ma wartość 1, policz wektory parzystej normy od 1 do 2B.

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 68 bajtów

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

Wypróbuj online!

Niestety tak samo jak wszyscy inni. Wiem, że istnieje prawdopodobnie lepszy sposób na napisanie tego, ale zadeklarowanie i wywołanie lambda w tym samym czasie w c # nie jest dokładnie czymś, co robię, cóż, zawsze. Chociaż w mojej obronie nie mogę wymyślić dobrego powodu (oczywiście poza golfem), aby to zrobić. Jeśli jednak ktoś wie, jak to zrobić, daj mi znać i / lub ukraść kredyt.

Wolfram Language (Mathematica) , 39 bajtów

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

Wypróbuj online!

Za pomocą transformacji współrzędnych JungHwan Min i po prostu zliczając rozwiązania nad liczbami całkowitymi.

05AB1E , 15 bajtów

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

Port @JonathanAllan s Jelly odpowiedzi , który z kolei jest pochodną od użytkownika @ XNOR wzoru „czarna magia” .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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)