Poin Kisi Segitiga dekat dengan Asal

34

Latar Belakang

Sebuah jaringan segitiga adalah grid yang dibentuk oleh ubin pesawat secara teratur dengan segitiga sama sisi dengan panjang sisi 1. Gambar di bawah adalah contoh dari grid segitiga.

Sebuah titik kisi segitiga adalah titik dari segitiga membentuk grid segitiga.

The asal adalah titik tetap di pesawat, yang merupakan salah satu poin kisi segitiga.

Tantangan

Dengan bilangan bulat non-negatif n, temukan jumlah titik kisi segitiga yang jarak Euclidean dari titik asal kurang dari atau sama dengan n.

Contoh

Gambar berikut adalah contoh untuk n = 7(hanya menampilkan area 60 derajat untuk kenyamanan, dengan titik A sebagai asal):

Uji Kasus

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

Petunjuk : Urutan ini bukan OEIS A003215 .

Aturan

Aturan standar untuk berlaku. Pengajuan terpendek menang.

Harap sertakan bagaimana Anda memecahkan tantangan dalam kiriman Anda.

Bubbler
sumber
7
OEIS A053416 adalah urutan jumlah titik yang terkandung dalam lingkaran berdiameter daripada jari-jari n, sehingga memiliki istilah dua kali lebih banyak dari yang Anda inginkan.
Neil
Wikipedia dan Mathworld yang relevan . Berisi formula xnor dan bukan bukti.
user202729
4
Ini adalah jumlah dari n^2+1ketentuan pertama OEIS A004016 .
alephalpha

Jawaban:

49

Python 2 , 43 byte

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

Cobalah online!

Ini adalah ilmu hitam.

Menawarkan 250 rep untuk bukti tertulis. Lihatjawaban Lynnuntuk bukti dan penjelasan.

Tidak
sumber
7
Bagaimana cara kerjanya? Saya telah bertanya-tanya selama 30 menit yang baik ... Kelihatannya sangat sederhana tetapi saya tidak dapat menemukan hubungan antara rekursi dan lingkaran ...
JungHwan Min
7
@JungHwanMin Bukti saya adalah perjalanan epik melalui geometri bidang, bilangan bulat Eisenstein, faktorisasi bidang angka, timbal balik kuadratik, progresi aritmatika, dan penjumlahan yang saling dipertukarkan - semua untuk ekspresi sederhana. Menulis itu semua akan menjadi tugas besar yang saya tidak punya waktu untuk saat ini, jadi saya berharap orang lain akan memberikan bukti, kemungkinan yang lebih sederhana yang saya miliki yang membuat koneksi menjadi lebih jelas.
xnor
14
Bukti . Ini lebih panjang dari Lynn tetapi lebih mandiri: ia tidak menggunakan pernyataan yang tidak terbukti tentang factorisation atas bilangan bulat Eisenstein.
Peter Taylor
2
@PeterTaylor Cheddar Monk? Seperti di Darths & Droids?
Neil
3
@Neil, selamat menjadi orang pertama yang bertanya! Saya mendaftarkan domain untuk menggunakannya sebagai chip tawar untuk Negosiasi, Level 1 di Akademi.
Peter Taylor
30

Haskell , 48 byte

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

Cobalah online!

Menggunakan rumus "ilmu hitam" xnor:

f(n)=1+6Sebuah=0n23Sebuah+1-n23Sebuah+2

Bukti kebenarannya, dan penjelasan tentang bagaimana xnor berhasil mengekspresikannya dalam 43 byte Python, dapat ditemukan di sini .

Singkat cerita: kita menghitung bilangan bulat Eisenstein dari norma , dengan memfaktorkan N =1Nn2 ke dalambilangan prima Eisensteindan menghitung berapa banyak solusi untuk ( x , y ) yang keluar faktorisasi. Kami mengakui jumlah solusi sama denganN=(x+yω)(x+yω)(x,y)

6×((# pembagi dari N1 (mod 3))-(# pembagi dari N2 (mod 3)))

dan terapkan trik pintar untuk membuatnya sangat mudah dihitung untuk semua bilangan bulat antara dan n 2 sekaligus. Ini menghasilkan formula di atas. Akhirnya, kami menerapkan beberapa sihir golf Python untuk berakhir dengan solusi yang sangat kecil yang ditemukan.1n2

Lynn
sumber
4
Saya tentu tidak berharap ini ketika xnor berkata "ada beberapa wawasan matematika yang mendalam di balik golf masalah".
Bubbler
29

Bahasa Wolfram (Mathematica) , 53 51 50 byte

-1 byte terima kasih kepada @miles

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

Cobalah online!

Bagaimana?

Alih-alih berpikir dalam hal ini:

masukkan deskripsi gambar di sini

Pikirkan seperti ini:

masukkan deskripsi gambar di sini

Jadi kami menerapkan matriks [[sqrt(3)/2, 0], [1/2, 1]]transformasi untuk mengubah gambar kedua ke yang pertama.

Kemudian, kita harus menemukan lingkaran di kotak segitiga dalam hal koordinat Cartesian.

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

Jadi kami menemukan poin kisi x, ysedemikian rupax^2 + x y + y^2 <= r^2

Misalnya, dengan r = 3:

masukkan deskripsi gambar di sini

JungHwan Min
sumber
1
FYI, rumusnya x^2+x y+y^2juga bisa berasal dari Hukum Cosinus dengan 120 derajat.
Bubbler
3
x^2+x y+y^2-> x(x+y)+y^2menyimpan byte
mil
Rumus x^2 + xy + y^2juga dapat diturunkan dari norma bilangan bulat Eistenstein, yaitu a^2 - ab + b^2. Perhatikan bahwa tanda adan btidak relevan kecuali dalam istilah absehingga memiliki jumlah solusi yang sama.
orlp
7

CJam (24 byte)

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

Ini adalah blok anonim (fungsi) yang mengambil satu argumen di stack dan meninggalkan hasilnya di stack. Test suite online . Perhatikan bahwa dua case terbesar terlalu lambat.

Penjelasan

alephalpha mencatat dalam komentar pada pertanyaan itu

Ini adalah jumlah dari ketentuan n ^ 2 + 1 pertama OEIS A004016

f(n)=1+6Sebuah=0n23Sebuah+1-n23Sebuah+2

Bukti saya tentang kebenaran formula itu didasarkan pada beberapa informasi yang diperoleh dari tautan OEIS alephalpha:

Gf: 1 + 6 * Jumlah_ {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

xSebuah

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

Diseksi kode

{          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
}
Peter Taylor
sumber
4

J , 27 byte

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

Cobalah online!

Berdasarkan metode JungHwan Min .

Penjelasan

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

Jelly ,  15  13 byte

-2 terima kasih kepada Dennis (hanya menambah kuadrat untuk menghindari penggabungan nol; hindari kepala dengan menggunakan modulo-slice post-difference daripada slice pra-perbedaan)

Menggunakan metode "ilmu hitam" untuk mengasah pada jawaban yang diekspos oleh xnor dalam jawaban Python mereka , tetapi menggunakan iterasi daripada rekursi (dan sedikit perhitungan kurang)

²:Ѐ‘$Im3S×6C

Tautan monadik yang menerima bilangan bulat non-negatif dan mengembalikan bilangan bulat positif.

Cobalah online! Atau lihat test-suite .

Bagaimana?

²:Ѐ‘$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
Jonathan Allan
sumber
2

JavaScript (ES6), 65 byte

Ini adalah port dari solusi @ 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))

Cobalah online!


Jawaban asli (ES7), 70 byte

Cukup berjalan melalui grid dan menghitung poin yang cocok.

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

Cobalah online!

Arnauld
sumber
Jawaban Porting xnor lebih pendek: 42 byte (output truebukan 1; 46 jika kita juga integer-bagi). Dan saya tidak tahu JavaScript cukup baik untuk golf divisi-integer ~~(a/b), tapi saya yakin ada cara yang lebih pendek untuk mereka juga ..
Kevin Cruijssen
1

Pari / GP , 42 byte

Menggunakan built-in qfrep.

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

qfrep (q, B, {flag = 0}): vektor (setengah) jumlah vektor norma dari 1 ke B untuk bentuk kuadratik integral dan pasti q. Jika flag adalah 1, hitung vektor norma normal dari 1 hingga 2B.

Cobalah online!

alephalpha
sumber
0

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

Cobalah online!

Sama seperti orang lain, sayangnya. Saya tahu mungkin ada cara yang lebih baik untuk menulis ini, tetapi menyatakan dan memanggil lambda pada saat yang sama dalam c # bukanlah sesuatu yang saya lakukan, yah, pernah. Meskipun dalam pembelaan saya, saya tidak bisa memikirkan alasan yang bagus (di luar kode golf, tentu saja) untuk melakukannya. Namun, jika seseorang tahu bagaimana Anda bisa melakukan ini, beri tahu saya dan / atau mencuri kreditnya, saya kira.

Andrew Baumher
sumber
0

05AB1E , 15 byte

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

Port of @JonathanAllan 's Jelly answer , yang pada gilirannya merupakan turunan dari rumus 'ilmu hitam' @ xnor .

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

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)
Kevin Cruijssen
sumber