N-movers: Berapa banyak papan tak terbatas yang bisa saya jangkau?

48

Bergerak tunggal

Papan adalah kotak persegi 2 dimensi tanpa batas, seperti papan catur tanpa batas. Sepotong dengan nilai N ( penggerak N) ) dapat bergerak ke bujur sangkar mana saja yang berjarak tepat dari akar kuadrat N dari bujur sangkar saat ini (jarak Euclidean diukur dari pusat ke pusat).

Sebagai contoh:

  • Penggerak 1 dapat bergerak ke bujur sangkar mana saja yang berdampingan secara horizontal atau vertikal
  • Penggerak 2 dapat bergerak ke bujur sangkar mana saja yang berdekatan secara diagonal
  • Penggerak 5 bergerak seperti ksatria catur

Perhatikan bahwa tidak semua pemindah N dapat bergerak. Penggerak 3 tidak pernah dapat meninggalkan kuadrat saat ini karena tidak ada kuadrat di papan yang berjarak persis akar 3 dari kuadrat saat ini.

Bergerak ganda

Jika dibiarkan bergerak berulang kali, beberapa bagian dapat mencapai bujur sangkar apa saja di papan tulis. Misalnya, penggerak 1 dan penggerak 5 dapat melakukan hal ini. Penggerak 2 hanya bisa bergerak secara diagonal dan hanya bisa mencapai setengah dari kotak. Sepotong yang tidak bisa bergerak, seperti penggerak 3, tidak dapat mencapai salah satu kotak ( kotak awal tidak dihitung sebagai "tercapai" jika tidak ada gerakan terjadi) .

1-penggerak Penggerak 2 Penggerak 3 4-penggerak 5-penggerak 8-penggerak 9-penggerak 10-penggerak 20-penggerak 25-penggerak Penggerak 40 Penggerak 64 Penggerak 65 Penggerak 68

Gambar menunjukkan kotak mana yang bisa dijangkau. Lebih detail tentang hover. Klik untuk gambar yang lebih besar.

  • Kotak yang dapat dijangkau dalam 1 atau lebih gerakan ditandai dengan warna hitam
  • Kotak yang dapat dijangkau dengan tepat 1 gerakan ditunjukkan oleh potongan merah
    (terlepas dari penggerak 3, yang tidak dapat bergerak)

Berapa proporsi papan yang bisa dicapai oleh N-mover?

Memasukkan

  • Bilangan bulat positif N

Keluaran

  • Proporsi dewan yang dapat dijangkau oleh penggerak-N
  • Ini adalah angka dari 0 hingga 1 (keduanya termasuk)
  • Untuk tantangan ini, output sebagai fraksi dalam istilah terendah, seperti 1/4, diperbolehkan

Jadi untuk input 10, baik 1/2dan 0.5adalah output diterima. Output sebagai pembilang dan penyebut yang terpisah juga dapat diterima, termasuk bahasa yang tidak mendukung pecahan atau pecahan. Misalnya, 1 2atau [1, 2].

Untuk output integer (0 dan 1), salah satu dari yang berikut ini adalah format yang dapat diterima:

  • Untuk 0: 0, 0.0, 0/1, 0 1,[0, 1]
  • untuk 1: 1, 1.0, 1/1, 1 1,[1, 1]

Mencetak gol

Ini kode golf. Skor adalah panjang kode dalam byte. Untuk setiap bahasa, kode terpendek menang.

Uji kasus

Dalam format input : output as fraction : output as decimal

  1 : 1     : 1
  2 : 1/2   : 0.5
  3 : 0     : 0
  4 : 1/4   : 0.25
  5 : 1     : 1
  6 : 0     : 0
  7 : 0     : 0
  8 : 1/8   : 0.125
  9 : 1/9   : 0.1111111111111111111111111111
 10 : 1/2   : 0.5
 13 : 1     : 1
 16 : 1/16  : 0.0625
 18 : 1/18  : 0.05555555555555555555555555556
 20 : 1/4   : 0.25
 25 : 1     : 1
 26 : 1/2   : 0.5
 64 : 1/64  : 0.015625
 65 : 1     : 1
 72 : 1/72  : 0.01388888888888888888888888889
 73 : 1     : 1
 74 : 1/2   : 0.5
 80 : 1/16  : 0.0625
 81 : 1/81  : 0.01234567901234567901234567901
 82 : 1/2   : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1     : 1
146 : 1/2   : 0.5
148 : 1/4   : 0.25
153 : 1/9   : 0.1111111111111111111111111111
160 : 1/32  : 0.03125
161 : 0     : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0     : 0
164 : 1/4   : 0.25
241 : 1     : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4   : 0.25
245 : 1/49  : 0.02040816326530612244897959184
260 : 1/4   : 0.25
261 : 1/9   : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2   : 0.5
292 : 1/4   : 0.25
293 : 1     : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1     : 1
326 : 0     : 0
360 : 1/72  : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2   : 0.5
369 : 1/9   : 0.1111111111111111111111111111
370 : 1/2   : 0.5
449 : 1     : 1
450 : 1/18  : 0.05555555555555555555555555556
488 : 1/8   : 0.125
489 : 0     : 0
490 : 1/98  : 0.01020408163265306122448979592
520 : 1/8   : 0.125
521 : 1     : 1
522 : 1/18  : 0.05555555555555555555555555556
544 : 1/32  : 0.03125
548 : 1/4   : 0.25
549 : 1/9   : 0.1111111111111111111111111111
584 : 1/8   : 0.125
585 : 1/9   : 0.1111111111111111111111111111
586 : 1/2   : 0.5
592 : 1/16  : 0.0625
593 : 1     : 1
596 : 1/4   : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2   : 0.5
611 : 0     : 0
612 : 1/36  : 0.02777777777777777777777777778
613 : 1     : 1
624 : 0     : 0
625 : 1     : 1
trichoplax
sumber
10
Saya memposting pertanyaan ini di Math.SE: math.stackexchange.com/questions/3108324/…
infmagic2047
Dugaan menarik!
trichoplax
1
"Sepotong yang tidak bisa bergerak, seperti penggerak 3, tidak dapat mencapai salah satu kotak". Cukup menarik, bahkan jika Anda menghitung kuadrat awal, karena papan tidak terbatas, ia masih menyatu dengan 0 sebagai proporsi.
Beefster
@Beefster poin bagus. Saya pergi dengan cara ini untuk membuat batas lebih mudah ditemukan tanpa harus pergi jauh-jauh sampai tak terbatas ...
trichoplax
2
@ infmagic2047 pertanyaan math.se tentang pendekatan anjak utama sekarang memiliki jawaban dengan bukti lengkap .
Ørjan Johansen

Jawaban:

19

JavaScript (Node.js) , 144 138 125 74 73 70 byte

f=(x,n=2,c=0)=>x%n?x-!c?f(x,n+1)/(n%4>2?n/=~c&1:n%4)**c:1:f(x/n,n,c+1)

Cobalah online!

-4 byte terima kasih @Arnauld!

Pendekatan asli, 125 byte

a=>(F=(x,n=2)=>n*n>x?[x,0]:x%n?F(x,n+1):[n,...F(x/n,n)])(a).map(y=>r-y?(z*=[,1,.5,p%2?0:1/r][r%4]**p,r=y,p=1):p++,z=r=p=1)&&z

Cobalah online!

Terinspirasi oleh video Pi bersembunyi dalam keteraturan prima oleh 3Blue1Brown.

pnf(pn)

  • np3 (mod 4)f(pn)=0
  • np3 (mod 4)f(pn)=1pn
  • p=2f(2n)=12n
  • p1 (mod 4)f(pn)=1

Lipat gandakan semua nilai fungsi itu, ini dia.

Memperbarui

Berkat upaya kontributor dari Math.SE, algoritme sekarang didukung oleh bukti

Shieru Asakoto
sumber
Apakah video berisi bukti? Saya sudah mencoba membuktikan hasil ini selama beberapa jam sekarang tetapi saya tidak bisa mengetahuinya.
infmagic2047
1
n
3
q=pPp{2,3} (mod 4)pep
1
@ infmagic2047 pertanyaan math.se tentang pendekatan ini sekarang memiliki jawaban dengan bukti lengkap .
Ørjan Johansen
11

Mathematica, 80 byte

d[n_]:=If[#=={},0,1/Det@LatticeReduce@#]&@Select[Tuples[Range[-n,n],2],#.#==n&];

Kode ini sebagian besar bergantung pada teorema matematika. Ide dasarnya adalah bahwa kode meminta kepadatan kisi yang diberikan beberapa set pembangkit.

Lebih tepatnya, kita diberi beberapa koleksi vektor - yaitu, mereka yang panjangnya kuadrat adalah N - dan diminta untuk menghitung kepadatan himpunan jumlah yang mungkin dari vektor-vektor ini, dibandingkan dengan semua vektor bilangan bulat. Matematika yang dimainkan adalah kita selalu dapat menemukan dua vektor (dan kebalikannya) yang "menghasilkan" (yaitu jumlah penjumlahannya) sama dengan kumpulan aslinya. LatticeReduce melakukan hal itu.

Jika Anda hanya memiliki dua vektor, Anda dapat membayangkan menggambar jajaran genjang identik yang berpusat pada setiap titik yang dapat dijangkau, tetapi yang panjang tepinya adalah vektor yang diberikan, sehingga bidang tersebut benar-benar ubin oleh jajaran genjang ini. (Bayangkan, misalnya, kisi bentuk "berlian" untuk n = 2). Luas setiap jajar genjang adalah penentu dari dua vektor penghasil. Proporsi yang diinginkan dari pesawat adalah kebalikan dari area ini, karena setiap jajaran genjang hanya memiliki satu titik yang dapat dijangkau di dalamnya.

Kode adalah implementasi yang cukup mudah: Hasilkan vektor, gunakan LatticeReduce, ambil determinan, lalu ambil resiprokal. (Tapi mungkin bisa bermain golf lebih baik)

Milo Brandt
sumber
76 byte:d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
u54112
11

Bersih , 189 185 172 171 byte

import StdEnv
$n#r=[~n..n]
#p=[[x,y]\\x<-r,y<-r|x^2+y^2==n]
=sum[1.0\\_<-iter n(\q=removeDup[k\\[a,b]<-[[0,0]:p],[u,v]<-q,k<-[[a+u,b+v]]|all(\e=n>=e&&e>0)k])p]/toReal(n^2)

Cobalah online!

Temukan setiap posisi yang dapat dijangkau dalam nkuadrat sisi panjang terpojok pada asal di kuadran pertama, lalu n^2bagi dengan membagi untuk mendapatkan bagian dari semua sel yang bisa dijangkau.

Ini berfungsi karena:

  • Seluruh bidang yang dapat dijangkau dapat dianggap sebagai salinan tumpang tindih dari nbujur sangkar panjang ini, masing-masing terpojok pada titik yang dapat dijangkau dari asal seolah-olah itu adalah asal.
  • Semua gerakan datang dalam kelompok empat dengan tanda-tanda ++ +- -+ --, memungkinkan ubin yang tumpang tindih diperpanjang melalui tiga kuadran lainnya dengan mirroring dan rotasi.
Suram
sumber
Permintaan maaf saya - saya melihat kasus uji yang berubah dari N = 10 ke N = 13, sedangkan kasus uji Anda termasuk N = 11 dan N = 12 juga. Anda memang benar untuk N = 13. +1 dari saya :)
trichoplax
1
@trichoplax Saya telah mengubah tes sesuai dengan pertanyaan untuk menghindari kebingungan yang sama lagi
Οurous
Saya sudah menguji lebih lanjut hingga N = 145 dan semuanya benar. Saya tidak bisa menguji 146 pada TIO karena batas waktu 60 detik. Saya mengharapkan jawaban jangka panjang di sini ...
trichoplax
1
Karena saya perlu waktu untuk menyadari hal ini: Alasan mengapa sudut kuadrat dapat dijangkau jika setidaknya ada satu gerakan (a, b), adalah persamaan kompleks (a + bi) (a-bi) = a ^ 2 + b ^ 2, yang dalam bentuk vektor menjadi (N, 0) = a (a, b) + b (b, -a).
Ørjan Johansen
5

Retina 0.8.2 , 126 82 byte

.+
$*
+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*
^(?!((^1|11\2)+)\1?$)1+
0
11+
1/$.&

Cobalah online! Tautan termasuk kasus uji. Penjelasan:

.+
$*

Konversikan ke unary.

+`^(1(1111)+)(?<!^\3+(11+))(\1)*$
1$#4$*

Membagi berulang kali dengan faktor-faktor utama formulir 4k+1.

^(?!((^1|11\2)+)\1?$)1+
0

Jika hasilnya bukan kotak atau dua kali kotak maka hasilnya adalah nol.

11+
1/$.&

Hitung timbal balik sebagai pecahan desimal.

Neil
sumber
5

Regex (ECMAScript, timbal balik), 256 163 157 94 83 82 byte

-93 bytes terima kasih kepada Neil
-6 bytes terima kasih lagi untuk Neil
-63 bytes dengan melakukan pembagian tanpa menangkap pembagi
-11 byte terima kasih kepada Grimy opsional opsional-divisi-oleh-konstanta dan akar kuadrat
-1 byte dengan menggerakkan kondisi pertandingan akhir dan mengembalikan tangkapan nilai ke dalam loop sebagai alternatif kedua, terima kasih kepada Grimy

Ini menggunakan matematika yang sama dengan jawaban JavaScript Shieru Asakoto .

Masukannya di unary. Karena regex murni hanya dapat kembali sebagai output substring dari input (yaitu bilangan alami kurang dari atau sama dengan input), atau "tidak cocok", regex ini mengembalikan kebalikan dari proporsi papan yang penggerak N-penggerak dapat meraih. Karena kebalikan dari 0 adalah tak terhingga, ia mengembalikan "tidak cocok" dalam kasus itu.

PERINGATAN SPOILER : Untuk akar kuadrat, regex ini menggunakan varian dari algoritma multiplikasi umum, yang tidak jelas dan bisa menjadi teka-teki yang bermanfaat untuk Anda kerjakan sendiri. Untuk informasi lebih lanjut, lihat penjelasan untuk bentuk algoritma ini di Temukan nomor Rocco .

pp1 (mod 4)mm3 (mod 4)mm/2mm

mm/2p3 (mod 4)

^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1

Cobalah online!
Cobalah online! (hanya kasus uji)

^
(?=
    (                          # Capture return value, which will just be the value
                               # matched by the last iteration of this loop.
    # Divide tail by every one of its prime factors that's ≡1 mod 4, as many times as
    # possible.
        (?=
            (x+)               # \2 = quotient
            (?!(\2+)(\2\3)+$)  # Assert divisor is prime
            ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
        )\5                    # tail = \2
    |
    # When the above alternative has been done as many times as possible:
    # Test if tail or tail/2 is a perfect square. If this test fails, the regex engine
    # will backtrack into the division loop above, and run the same perfect square
    # test on every previous number (effectively "multiplying" it by each previous P
    # in reverse, one at a time). This will not cause a failure of the test to change
    # into a success, however, because the odd power of a prime ≡3 mod 4 will see be
    # present in the number at every step. Allowing this backtracking to happen is a
    # golf optimization, and it does make the regex slower.
    # Failure of this perfect square test results in returning "no match" and indicates
    # a return value of zero.
        (                      # \7 = \8 * sqrt(tail / \8)
            (xx?)              # \8 = control whether to take sqrt(tail)
                               #                         or 2*sqrt(tail/2)
            (\8*)              # \9 = \7 - \8
        )
        (?=
            (\7*)\9+$          # Iff \8 * (\7 / \8)^2 == our number, then the first match
                               # here must result in \10==0
        )
        \7*$\10                # Test for divisibility by \7 and for \10==0
                               # simultaneously
    )+
    $                          # Require that the last iteration of the above loop was
                               # the perfect square test. Since the first alternative,
                               # the division, always leaves >=1 in tail, this guarantees
                               # that the last step is a successful perfect square test,
                               # or else the result will be "no match".
)
\1                             # Return value (which is a reciprocal)

Regex (ECMAScript + (? *), Output timbal balik), 207 138 132 byte

Usang dengan melakukan pembagian tanpa menangkap pembagi (yaitu sekarang identik dengan yang di atas).

Regex (ECMAScript 2018, output timbal balik), 212 140 134 byte

Usang dengan melakukan pembagian tanpa menangkap pembagi (yaitu sekarang identik dengan yang di atas).

Regex (ECMAScript, output fraksi), 80 byte

Dalam versi ini, pembilang dikembalikan dalam \10(nol jika tidak disetel / NPCG) dan penyebut dalam \7.

Berbeda dengan versi keluaran timbal balik:

  • Input nol tidak ditangani dengan benar (mengembalikan "tidak cocok" sama seperti versi itu, tetapi tidak seperti itu, yang tidak sesuai dengan nilai output nol).
  • Jika uji kuadrat sempurna gagal, itu tidak mundur ke loop divisi, sehingga versi ini lebih efisien dalam waktu eksekusi.

Kelemahan besar dari spesifikasi keluaran seperti ini adalah tidak terdapat dalam program itu sendiri.

((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)

Cobalah online!
Cobalah online! (hanya kasus uji)

# No need to anchor, since we return a match for all inputs in the domain.
# Divide tail by every one of its prime factors that's ≡1 mod 4
(
    (?=
        (x+)               # \2 = quotient
        (?!(\2+)(\2\3)+$)  # Assert divisor is prime
        ((\2{4})+$)        # Assert divisor ≡1 mod 4; \5 = tool to make tail = \2
    )\5                    # tail = \2
)*
# Test if tail or tail/2 is a perfect square. If this test succeeds, return tail as
# the denominator and 1 as the numerator.
(                          # \7 = denominator output
    (                      # \8 = \9 * sqrt(tail / \9)
        ((x)x?)            # \9 = control whether to take sqrt(tail) or 2*sqrt(tail/2);
                           # \10 = numerator output (NPCG to represent zero)
        (\9*)              # \11 = \8 - \9
    )
    (?=
        (\8*)\11+$         # Iff \9 * (\8 / \9)^2 == our number, then the first match
                           # here must result in \12==0
    )
    \8*$\12                # Test for divisibility by \8 and for \12==0
                           # simultaneously
|
# Failure of the perfect square test results in returning 0/1 as the answer, so here
# we return a denominator of 1.
    x
)
Kode mati
sumber
1
Maaf, saya jelas tidak mencobanya pada cukup banyak test case.
Neil
1
@trichoplax Bisakah Anda menganggap jawabannya sebagai rasio panjang dua kelompok tangkapan spesifik? (Ini sebenarnya akan membuat jawaban lebih pendek karena butuh kesulitan untuk membuat seluruh pertandingan menjadi hasilnya.)
Neil
1
Mengikuti komentar @ Neil, saya telah diedit untuk mengizinkan output sebagai pembilang dan penyebut yang terpisah, karena itu tampaknya perubahan terkecil yang memungkinkan untuk regex murni. Beri tahu saya jika itu masih menjadi masalah
trichoplax
1
-11 byte dengan menggunakan (((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)untuk memeriksa apakah N atau N / 2 adalah bujur sangkar.
Grimmy
1
@Deadcode pointer ke backrefs tidak boleh diberikan biaya byte, karena mereka diizinkan secara default .
Grimmy
4

Jelly ,  25  24 byte

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P

Tautan monadik menggunakan rute faktor utama.

Cobalah online!

Bagaimana?

ÆFµ%4,2CḄ:3+2Ịị,*/ʋ÷*/)P - Link: integer, n               e.g. 11250
ÆF                       - prime factor, exponent pairs        [[2,1], [3,2], [5,4]]
  µ                   )  - for each pair [F,E]:
    4,2                  -   literal list [4,2]
   %                     -   modulo (vectorises)                [2,1]  [3,0]  [1,0]
       C                 -   complement (1-x)                  [-1,0] [-2,1]  [0,1]
        Ḅ                -   from base 2                         -2     -3      1      
         :3              -   integer divide by three             -1     -1      0
           +2            -   add two (call this v)                1      1      3
                  ʋ      -   last four links as a dyad, f(v, [F,E])
             Ị           -     insignificant? (abs(x)<=1 ? 1 : 0)   1      1      0
                */       -     reduce by exponentiation (i.e. F^E)  2      9     625
               ,         -     pair v with that                   [1,2]  [1,9]  [3,625]
              ị          -     left (Ị) index into right (that)     1      1     625
                    */   -   reduce by exponentiation (i.e. F^E)    2      9     625
                   ÷     -   divide                                1/2    1/9  625/625
                       P - product                                 1/18 = 0.05555555555555555

25 sebelumnya adalah:

ŒRp`²S⁼ɗƇ⁸+€`Ẏ;Ɗ%³QƊÐLL÷²

Forcer brute program penuh ; kode mungkin lebih lama dari rute faktor utama (saya mungkin akan mencoba nanti).

Cobalah online!

Mulai dengan menciptakan gerakan tunggal sebagai koordinat kemudian berulang kali bergerak dari semua lokasi mencapai mengumpulkan hasil, mengambil modulo nmasing-masing koordinat (untuk membatasi ke noleh nkuadran) dan menjaga orang-orang yang berbeda sampai titik tetap tercapai; lalu akhirnya membagi hitungan dengann^2

Jonathan Allan
sumber
4

05AB1E , 27 26 25 byte

ÓεNØ©<iozë®4%D≠iyÈ®ymz*]P

Port dari jawaban JavaScript @ShieruAsakoto , jadi pastikan untuk menambahkannya juga!

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

Ó                   # Get all prime exponent's of the (implicit) input's prime factorization
                    #  i.e. 6 → [1,1]      (6 → 2**1 * 3**1)
                    #  i.e. 18 → [1,2]     (18 → 2**1 * 3**2)
                    #  i.e. 20 → [2,0,1]   (20 → 2**2 * 3**0 * 5**1)
                    #  i.e. 25 → [0,0,2]   (25 → 2**0 * 3**0 * 5**2)
 ε                  # Map each value `n` to:
  NØ                #  Get the prime `p` at the map-index
                    #   i.e. map-index=0,1,2,3,4,5 → 2,3,5,7,11,13
    ©               #  Store it in the register (without popping)
     <i             #  If `p` is exactly 2:
       oz           #   Calculate 1/(2**`n`)
                    #    i.e. `n`=0,1,2 → 1,0.5,0.25
      ë             #  Else:
       ®4%          #   Calculate `p` modulo-4
                    #    i.e. `p`=3,5,7,11,13 → 3,1,3,3,1
          D         #   Duplicate the result (the 1 if the following check is falsey)
           i       #   If `p` modulo-4 is NOT 1 (in which case it is 3):
             yÈ     #    Check if `n` is even (1 if truthy; 0 if falsey)
                    #     i.e. `n`=0,1,2,3,4 → 1,0,1,0,1
             ®ymz   #    Calculate 1/(`p`**`n`)
                    #     i.e. `p`=3 & `n`=2 → 0.1111111111111111 (1/9)
                    #     i.e. `p`=7 & `n`=1 → 0.14285714285714285 (1/7)
              *     #    Multiply both with each other
                    #     i.e. 1 * 0.1111111111111111 → 0.1111111111111111
                    #     i.e. 0 * 0.14285714285714285 → 0
 ]                  # Close both if-statements and the map
                    #  i.e. [1,1] → [0.5,0.0]
                    #  i.e. [1,2] → [0.5,0.1111111111111111]
                    #  i.e. [2,0,1] → [0.25,1.0,1]
                    #  i.e. [0,0,2] → [1.0,1.0,1]
  P                 # Take the product of all mapped values
                    #  i.e. [0.5,0.0] → 0.0
                    #  i.e. [0.5,0.1111111111111111] → 0.05555555555555555
                    #  i.e. [0.25,1.0,1] → 0.25
                    #  i.e. [1.0,1.0,1] → 1.0
                    # (and output implicitly as result)
Kevin Cruijssen
sumber
4

APL (Dyalog Extended) , 21 byte

Program ini menggunakan rute faktor utama. Saya berhutang budi kepada Adám, dzaima, H.PWiz, J.Sallé, dan ngn. APL Orchard adalah tempat yang tepat untuk belajar APL dan mereka selalu bersedia membantu

(×/÷,34|*∘≢⌸)⍭*14|⍭

Cobalah online!

Tidak melakukanolf

Bagian 2 dari kode ini sama dengan dalam versi Dyalog Unicode di bawah ini, dan dalam penjelasan ini, saya akan fokus pada ⍭*1≠4|⍭

⍭*14|⍭

        Gives us a list of the prime factors of our input.
           Example for 45: 3 3 5
  14|   Checks if each prime is of the form 4k+1.
⍭*       Takes each prime to the power of 1 or 0,
           turning all the 4k+1 primes into 1s.
           Example for 45: 3 3 1

APL (Dyalog Unicode) , 41 40 36 35 byte SBCS

Program ini menggunakan rute faktor utama. Belajar beberapa trik saat menulis ini dan saya sangat berhutang budi kepada Adám, dzaima, H.PWiz, J.Sallé, dan ngn. APL Orchard adalah tempat yang tepat untuk belajar APL dan mereka selalu bersedia membantu (atau posting ini tidak akan pernah turun :)

Sunting: -1 byte dari ngn. -2 byte dari Adám dan -2 lebih banyak dari ngn. -1 byte dari ngn.

{(×/÷,34|*∘≢⌸)p*14|p←¯2÷/∪∧\⍵∨⍳⍵}

Cobalah online!

Tidak melakukanolf

Ini adalah program dalam dua bagian:

p*14|p←¯2÷/∪∧\⍵∨⍳⍵  Part 1

      p             We can define variables mid-dfn (a function in {} brackets).
               ⍵∨⍳⍵  We take the GCD of our input 
                       with every member of range(1, input).
            ∪∧\      This returns all the unique LCMs of every prefix
                       of our list of GCDs.
                       Example for 31500: 1 2 6 12 60 420 1260 6300 31500
        ¯2÷/         We divide pairwise (and in reverse)
                       by using a filter window of negative two 2).
                       Example for 31500: 2 3 2 5 7 3 5 5
  14|p              Check if the primes are 1 modulo 4 or not
p*                   And take each prime to the power of the result (1 or 0),
                       turning the 4k+3 primes into 1s
                       and leaving any 2s and 4k+3 primes.
                       Example for 31500: 2 3 2 1 7 3 1 1

(×/÷,34|*∘≢⌸)  Part 2

(            )  We apply all this to the filtered array of primes.
         *∘≢⌸   This takes all of our primes to their exponents
                  (the number of times those primes appear in the factorization).
                  Example for 31500: 4 9 1 7
     34|       Then we take each prime modulo 4 and check if not equal to 3.
                  We will only get a falsey if any 4k+3 primes, as an even number of
                  4k+3 primes multiplied together will result in some 4m+1.
                  Example for 31500: 1 1 1 0
   ÷,           We append the results of the above condition check
                  to the reciprocals of the primes in p.
                  Example for 31500: (1/2) (1/3) (1/2) 1 (1/7) (1/3) 1 1 1 1 1 0
 ×/             We multiply it all together, resulting in a positive fraction or 0
                  depending on our condition check.
                  Example for 31500: 0
                We return the results of all our checks implicitly.
Sherlock9
sumber