Trójkątne punkty kratowe w pobliżu źródła


34

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 . Najkrótsze zgłoszenie wygrywa.

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


7
OEIS A053416 jest sekwencją liczby punktów zawartych w okręgu o średnicy zamiast promienia n, więc ma dwa razy więcej terminów, niż chcesz.
Neil

Odpowiednie Wikipedia i Mathworld . Zawiera formułę xnor, a nie dowód.
user202729,

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

Odpowiedzi:


49

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.


7
Jak to działa? Zastanawiam się od dobrych 30 minut ... Wygląda to tak prosto, ale nie mogę znaleźć związku między tą rekurencją a kręgami ...
JungHwan Min.

7
@JungHwanMin Mój dowód to epicka podróż przez geometrię płaszczyzny, liczby całkowite Eisensteina, rozkład na pola liczbowe, kwadratową wzajemność, postęp arytmetyczny i zamiany sum - wszystko to dla tak prostego wyrażenia. Napisanie tego wszystkiego byłoby dużym przedsięwzięciem, na które nie mam teraz czasu, więc mam nadzieję, że ktoś inny przedstawi dowód, prawdopodobnie łatwiejszy od mojego, który sprawi, że połączenie będzie wyraźniejsze.
xnor

14
Dowód . Jest to dłuższe niż Lynn, ale bardziej samodzielne: nie korzysta z niepotwierdzonych twierdzeń na temat faktoryzacji nad liczbami całkowitymi Eisensteina.
Peter Taylor,

2
@PeterTaylor Cheddar Monk? Jak w Darths & Droids?
Neil

3
@Neil, gratuluję bycia pierwszą osobą, która kiedykolwiek zapytała! Zarejestrowałem domenę, aby używać jej jako karty przetargowej do negocjacji, poziom 1 w Akademii.
Peter Taylor

30

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+6a=0n23a+1n23a+2

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ą1Nn2N=(x+yω)(x+yω)(x,y)

6×((# of divisors of N1 (mod 3))(# of divisors of N2 (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 21n2


4
Z pewnością nie spodziewałem się tego, gdy xnor powiedział „istnieje głęboki matematyczny wgląd w grę w golfa”.
Bubbler,

29

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:

wprowadź opis zdjęcia tutaj

Pomyśl o tym w ten sposób:

wprowadź opis zdjęcia tutaj

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:

wprowadź opis zdjęcia tutaj


1
FYI, formuła x^2+x y+y^2może również pochodzić z prawa cosinusów o 120 stopniach.
Bubbler

3
x^2+x y+y^2-> x(x+y)+y^2zapisuje bajt
mile

Wzór ten x^2 + xy + y^2można również wyprowadzić z normy liczby całkowitej Eistensteina, którą jest a^2 - ab + b^2. Zauważ, że znak ai bjest nieistotny, z wyjątkiem terminu, abwięc ma taką samą ilość rozwiązań.
orlp


7

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+6a=0n23a+1n23a+2

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ćxa

k=0(1qk+1)(1+xqk+1)(1+x1qk)=kZqk(k+1)/2xk
m,nZωmnqm2+mn+n2=k=1(1qk)31q3k
ω
m,nZqm2+mn+n2=1+6k0(q3k+11q3k+1q3k+21q3k+2)

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
}

4

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



3

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

2

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!


Odpowiedź na przeniesienie xnora jest krótsza: 42 bajty (wyjścia truezamiast 1; 46, jeśli podzielimy ją również na liczby całkowite). I nie znam JavaScript na tyle dobrze, by grać w podziały na liczby całkowite ~~(a/b), ale jestem pewien, że jest też krótsza droga dla tych.
Kevin Cruijssen


1

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!


0

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.



0

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)
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.