Hintergrund

Ein Dreiecksgitter ist ein Gitter, bei dem die Ebene regelmäßig mit gleichseitigen Dreiecken der Seitenlänge 1 gekachelt wird. Das folgende Bild zeigt ein Beispiel für ein Dreiecksgitter.

Ein dreieckiger Gitterpunkt ist ein Eckpunkt eines Dreiecks, das das Dreiecksgitter bildet.

Der Ursprung ist ein fester Punkt in der Ebene, der einer der dreieckigen Gitterpunkte ist.

Herausforderung

Bestimmen Sie bei einer nicht negativen ganzen Zahl ndie Anzahl der dreieckigen Gitterpunkte, deren euklidischer Abstand vom Ursprung kleiner oder gleich ist n.

Beispiel

Die folgende Abbildung ist ein Beispiel dafür n = 7(sie zeigt der Einfachheit halber nur einen 60-Grad-Bereich, wobei Punkt A der Ursprung ist):

Testfälle

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

Hinweis : Diese Sequenz ist nicht OEIS A003215 .

Regeln

Es gelten die Standardregeln für Code-Golf . Die kürzeste Einsendung gewinnt.

Bitte geben Sie an, wie Sie die Herausforderung gelöst haben.

Python 2 , 43 Bytes

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

Probieren Sie es online!

Das ist schwarze Magie.

Bietet 250 Wiederholungen für einen schriftlichen Nachweis. SieheLynns Antwortfür einen Beweis und eine Erklärung.

Haskell , 48 Bytes

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

Probieren Sie es online!

Verwendet die "schwarze Magie" -Formel von 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$$

Ein Beweis für seine Richtigkeit und eine Erklärung, wie xnor es geschafft hat, es in 43 Bytes Python auszudrücken, finden Sie hier .

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

$1$$n^2$

Wolfram Language (Mathematica) , 53 51 50 Bytes

^{-1 Byte dank @miles}

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

Probieren Sie es online!

Wie?

Anstatt daran zu denken:

Stellen Sie es sich so vor:

Wir wenden also die Transformationsmatrix [[sqrt(3)/2, 0], [1/2, 1]]an, um die zweite Figur in die erste zu transformieren.

Dann müssen wir den Kreis im Dreiecksgitter in kartesischen Koordinaten finden.

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

Also finden wir Gitterpunkte x, yso, dassx^2 + x y + y^2 <= r^2

Zum Beispiel mit r = 3:

Wolfram Language (Mathematica) , 48 Byte

Basierend auf OEIS A004016 .

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

Probieren Sie es online!

CJam (24 Bytes)

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

Dies ist ein anonymer Block (eine Funktion), der ein Argument auf dem Stapel nimmt und das Ergebnis auf dem Stapel belässt. Online-Testsuite . Beachten Sie, dass die beiden größten Fälle zu langsam sind.

Erläuterung

alephalpha stellte in einem Kommentar zur Frage fest, dass

Es ist die Summe der ersten n ^ 2 + 1 Terme von 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$$

Mein Beweis für die Richtigkeit dieser Formel basiert auf einigen Informationen, die ich über den OEIS-Link von alephalpha erhalten habe:

Gf: 1 + 6 * Summe_ {n> = 1} x ^ (3 * n - 2) / (1 - x ^ (3 * n - 2)) - x ^ (3 * n - 1) / (1 - 1) x ^ (3 * n-1)). - Paul D. Hanna, 3. Juli 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$$ $$\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)$$

Code-Zerlegung

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

Probieren Sie es online!

Basierend auf der Methode von JungHwan Min .

Erläuterung

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

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

Probieren Sie es online!

Hommage an Xnors und Lynns Antworten

Der letzte Test wird kommentiert, weil er mehr Speicher benötigt, z. B. MAXWS=200Min der Umgebung

Jelly , 14 Bytes

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

Verwendet die @ JungHwanMin-Methode .

Probieren Sie es online!

Jelly ,  15 bis  13 Bytes

-2 dank Dennis (erhöhe einfach das Quadrat, um die Verkettung einer Null zu vermeiden; vermeide den Kopf, indem du ein Post-Differenz-Modulo-Slice anstelle eines Pre-Differenz-Slice verwendest)

^{Verwendet die "schwarze Magie" -Methode, um die von xnor in ihrer Python-Antwort offen gelegte Antwort zu verfeinern , verwendet jedoch Iteration anstelle von Rekursion (und etwas weniger Berechnung).}

²:Ѐ‘$Im3S×6C

Eine monadische Verknüpfung, die eine nicht negative Ganzzahl akzeptiert und eine positive Ganzzahl zurückgibt.

Probieren Sie es online! Oder schauen Sie sich die Testsuite an .

Wie?

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

Dies ist ein Port der @ JungHwanMin-Lösung .

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

Probieren Sie es online!

---

Ursprüngliche Antwort (ES7), 70 Bytes

Geht einfach durch das Gitter und zählt die passenden Punkte.

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

Probieren Sie es 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 von @xnors Python 2 Antwort .

Probieren Sie es online aus.

Pari / GP , 42 Bytes

Verwendung des eingebauten qfrep.

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

qfrep (q, B, {flag = 0}): Vektor der (halben) Anzahl von Vektoren der Normen von 1 bis B für die ganzzahlige und bestimmte quadratische Form q. Wenn flag 1 ist, werden Vektoren mit gerader Norm von 1 bis 2B gezählt.

Probieren Sie es online!

C # (Visual C # Interactive Compiler) , 68 Byte

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

Probieren Sie es online!

Wie alle anderen auch, leider. Ich weiß, dass es wahrscheinlich eine bessere Möglichkeit gibt, dies zu schreiben, aber das gleichzeitige Deklarieren und Aufrufen eines Lambda in c # ist nicht genau das, was ich tue, naja, jemals. Obwohl mir zu meiner Verteidigung kein guter Grund einfällt (natürlich außerhalb von Code Golf), dies zu tun. Wenn dennoch jemand weiß, wie Sie dies tun können, lassen Sie es mich wissen und / oder stehlen Sie das Guthaben, denke ich.

Wolfram Language (Mathematica) , 39 Byte

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

Probieren Sie es online!

Verwenden der Koordinatentransformation von JungHwan Min und einfaches Zählen der Lösungen über die ganzen Zahlen.

05AB1E , 15 Bytes

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

Port of @JonathanAllans Jelly-Antwort , die wiederum eine Ableitung von @ xnors 'black magic'-Formel ist .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

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)