20

Di Basis-10, semua kuadrat sempurna berakhir dengan 0 , 1 , 4 , 5 , 6 , atau 9 .

Di Basis-16, semua kuadrat sempurna berakhir dengan 0 , 1 , 4 , atau 9 .

Nilknarf menjelaskan mengapa ini dan bagaimana mengerjakannya dengan sangat baik dalam jawaban ini , tetapi saya juga akan memberikan deskripsi singkat di sini:

Saat menguadratkan nomor Base-10, N , digit "yang" tidak terpengaruh oleh apa yang ada di digit "puluhan", atau digit "ratusan", dan sebagainya. Hanya "orang-orang" digit di N mempengaruhi "yang" digit di N ² , sehingga cara mudah (tapi mungkin tidak golfiest) untuk menemukan semua kemungkinan digit terakhir untuk N ² adalah untuk menemukan n ² mod 10 untuk semua 0 <= n < 10 . Setiap hasil adalah kemungkinan digit terakhir. Untuk Base-m, Anda dapat menemukan n ² mod m untuk semua 0 <= n < m .

Tulis sebuah program yang, ketika diberi input N , mengeluarkan semua digit terakhir yang memungkinkan untuk kuadrat sempurna di Base-N (tanpa duplikat). Anda dapat mengasumsikan N lebih besar dari 0 , dan bahwa N cukup kecil sehingga N ² tidak akan meluap (Jika Anda dapat menguji sampai N ² , saya akan memberi Anda jumlah poin brownies yang terbatas, tetapi ketahuilah bahwa nilai tukar poin brownies ke poin nyata adalah infinity ke satu).

Tes:

 Input -> Output
 1     -> 0
 2     -> 0,1
 10    -> 0,1,5,6,4,9
 16    -> 0,1,4,9
 31    -> 0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28
 120   -> 0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105

ini kode-golf , jadi aturan standar berlaku!

(Jika Anda merasa ini terlalu mudah, atau Anda menginginkan pertanyaan yang lebih mendalam tentang topik ini, pertimbangkan pertanyaan ini: Penutup minimal pangkalan untuk pengujian kuadrat residu kuadrat ).

code-golf number-theory abstract-algebra Tuan Farquaad
sumber

1

Apakah array output perlu diurutkan?

Shaggy

@Shaggy Tidak! Mego, Duplikasi tidak diizinkan. Secara teoritis, N bisa jadi sangat besar, sehingga duplikat akan membuat outputnya tidak terbaca. Saya akan mengajukan pertanyaan

Lord Farquaad

Apakah mengeluarkan satu set dapat diterima?

totallyhuman

2

@totallyhuman Mengapa itu tidak valid? Set adalah koleksi yang tidak teratur dan tidak boleh disortir , jadi ...

Tn. Xcoder

8

Jelly , 5 byte

R²%³Q

Cobalah online!

Penjelasan

R²%³Q   Main link, argument: n

R       Range from 1 to n
 ²      Square each
  %³    Mod each by n
    Q   Deduplicate

Kucing Bisnis
sumber

19

Google Sheets, 52 51 47 byte

=ArrayFormula(Join(",",Unique(Mod(Row(A:A)^2,A1

_{^{Disimpan 4 byte berkat Taylor Scott}}

Lembar akan secara otomatis menambahkan 4 tanda kurung tutup ke akhir rumus.

Itu tidak mengembalikan hasil dalam urutan menaik tetapi mengembalikan hasil yang benar.

Toast insinyur
sumber

Sapi suci, manusia yang merupakan pembunuh yang dilukai! Siapa yang akan berpikir? +1

bearacuda13

1

Ini pasti jawaban favorit saya sejauh ini.

Lord Farquaad

@ LordFarquaad Saya terkejut dan senang ini diterima dengan sangat baik. Saya telah mencoba bermain golf lebih banyak di Sheets dan Excel meskipun - dan sebagian karena - mereka memiliki rentang yang terbatas. Itu menyebabkan banyak formula array.

Engineer Toast

Anda harus dapat menghentikan terminating )s untuk -4 byte

Taylor Scott

@TaylorScott Terima kasih! Saya melihat trik itu di suatu tempat baru-baru ini - mungkin pada salah satu jawaban Anda - dan perlu diingat untuk mulai menggunakannya.

Engineer Toast

6

05AB1E , 5 byte

Lns%ê

Cobalah online! atau sebagai Test Suite

L     # Range 1 .. input
 n    # Square each
  s%  # Mod by input
    ê # Uniquify (also sorts as a bonus)

Riley
sumber

Bagaimana cara skerjanya di sini? Apakah input diulang?

Luis Mendo

@LuisMendo sadalah pop a,b; push b,a. Ketika sebuah perintah mencoba mengeluarkan sesuatu dari stack dan tidak ada lagi yang tersisa, input selanjutnya digunakan. Jika tidak ada lagi input, input terakhir digunakan ( ini adalah contoh ). Dalam hal ini saya bisa menggunakan ¹yang mendorong input pertama, tetapi sberfungsi lebih baik untuk test suite.

Riley

Terima kasih. Apakah Anda memiliki info lebih lanjut mengenai kriteria input yang digunakan kembali? (jika ada yang mengatakan tiga input dan Anda mencoba memunculkan dua nilai dari tumpukan kosong)?

Luis Mendo

1

@LuisMendo Input digunakan secara berurutan hingga habis, lalu terus menggunakan elemen terakhir. Anda dapat membayangkannya seperti tumpukan diisi dengan setiap input secara berurutan dan jumlah elemen terakhir yang tidak terbatas.

Riley

@LuisMendo Ln¹%êsetara di sini. s.

Magic Gurita Guci

6

Swift , 47 35 32 * byte

* -3 terima kasih kepada @Alexander.

Mungkin pertama kali dalam sejarah Swift ~~ties~~ mengalahkan Python?

{m in Set((0..<m).map{$0*$0%m})}

Cobalah online!

Penjelasan

(0..<m).map{}- Ulangi kisaran [0...m)dan petakan hasil berikut:
$0*$0%m- Kuadrat dari setiap bilangan bulat modulo basis m.
Set(...) - Menghapus duplikat.
m in - Menetapkan basis ke variabel m

Tuan Xcoder
sumber

Nama pengguna keluar ... tunggu sebentar.

Rohan Jhunjhunwala

1

Lebih seperti itu mengalahkan Python. Itu mengesankan ! Saya pikir saya tidak akan pernah melihat hari yang akan terjadi.

Caleb Kleveter

@ CalebKleveter Terima kasih! Saya senang Anda menemukannya mengesankan :)

Tn. Xcoder

3

C #, 63 byte

using System.Linq;m=>new int[m].Select((_,n)=>n*n%m).Distinct()

Cobalah online!

TheLethalCoder
sumber

3

JavaScript (ES6), 52 byte

f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

Uji kasus

Tampilkan cuplikan kode

f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))

Luaskan cuplikan

Versi non-rekursif, 60 58 byte

Disimpan 2 byte berkat @ThePirateBay

m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

Uji kasus

Tampilkan cuplikan kode

let f =

m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))

Luaskan cuplikan

Arnauld
sumber

Non-rekursif 58 byte:m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

@ThePirateBay Tangkapan yang bagus. Terima kasih.

Arnauld

3

Pyth, 6 byte

{%RQ*R

Cobalah online

Bagaimana itu bekerja

{%RQ*RdQ    implicit variables
       Q    autoinitialized to eval(input())
    *R      over [0, …, Q-1], map d ↦ d times
      d         d
 %R         map d ↦ d modulo
   Q            Q
{           deduplicate

Anders Kaseorg
sumber

3

Brachylog , 10 9 byte

>ℕ^₂;?%≜ᶠ

Cobalah online!

Penjelasan

       ≜ᶠ       Find all numbers satisfying those constraints:
    ;?%           It must be the result of X mod Input where X…
  ^₂              …is a square…
>ℕ                …of an integer in [0, …, Input - 1]

Fatalisasi
sumber

Saya akan menyarankan {>≜^₂;?%}ᵘsebagai alternatif ... kemudian saya menyadari ada angka negatif juga. > _ <

Erik the Outgolfer

1

@EriktheOutgolfer Setelah komit ditarik ke TIO, saya benar-benar dapat mengurangi jawaban ini menjadi 9 byte memang menggunakan ≜.

Fatalkan

OK ... bagaimana cara kerjanya ketika ada angka negatif juga? Apakah itu hanya mengabaikan mereka atau sesuatu?

Erik the Outgolfer

@EriktheOutgolfer mod dapat didefinisikan sebagai sisa pembagian, yang akan menjadi positif (hasil bagi mengambil tanda). SUNTING: juga, kotak positif.

jaxad0127

@ jaxad0127 Saya tidak berpikir itu yang terjadi di sini, karena >masih akan menjelaskan angka negatif afaik.

Erik the Outgolfer

3

Japt , 7 6 byte

Ç²%UÃâ

Menguji

1 byte disimpan berkat Oliver

Penjelasan

Input bilangan bulat implisit U.

Ç   Ã

Buat array bilangan bulat dari 0hingga U-1, inklusif, dan berikan masing-masing fungsi.

²

Kotak.

%U

Modulo U.

â

Dapatkan semua elemen unik dalam array dan secara implisit menampilkan hasilnya.

Shaggy
sumber

1

Saya tidak berpikir rentang perlu inklusif. Ç²%UÃâtampaknya berfungsi dengan baik.

Oliver

2

Python 3 , 40 39 37 byte

-1 byte terima kasih kepada Tn. Xcoder. -2 byte berkat Business Cat.

lambda m:[*{n*n%m for n in range(m)}]

Cobalah online!

benar-benar manusiawi
sumber

1

Tidak bisakah Anda ganti n**2dengan n*n?

Tn. Xcoder

Yup, selalu lupakan itu. > <Terima kasih!

totallyhuman

2

Selain itu, range(m)sudah cukup

Bisnis Kucing

1

Anda dapat menggunakan set untuk 34 byte

Mr. Xcoder

2

Sebenarnya , 11 byte

;╗r⌠²╜@%⌡M╔

Cobalah online!

Penjelasan:

;╗r⌠²╜@%⌡M╔
;╗           store a copy of m in register 0
  r          range(m)
   ⌠²╜@%⌡M   for n in range:
    ²          n**2
     ╜@%       mod m
          ╔  remove duplicates

Mego
sumber

2

CJam , 12 byte

{_,_.*\f%_&}

Blok anonim menerima nomor dan mengembalikan daftar.

Cobalah online!

Penjelasan

_,          Copy n and get the range [0 .. n-1]
  _.*       Multiply each element by itself (square each)
     \f%    Mod each by n
        _&  Deduplicate

Kucing Bisnis
sumber

Bagus! Saya punya {:X{_*X%}%_&}untuk 13 byte

Luis Mendo

2

Haskell , 45 byte

import Data.List
f m=nub[n^2`mod`m|n<-[0..m]]

-4 byte dari Anders Kaseorg

Cobalah online!

Mego
sumber

Sedihnya, versi point-free f m=nub$map((`mod`m).(^2))[0..m]sama panjangnya, kecuali ada sintaks yang licik untuk menghilangkan tanda kurung tambahan.

shooqie

2

MATL , 6 5 byte

-1 byte terima kasih kepada @LuisMendo

:UG\u

Cobalah online!

Cinaski
sumber

Terima kasih! Saya mencari di dokumen mencari fungsi itu tetapi tidak dapat menemukannya.

Cinaski

BTW juru bahasa yang dibuat oleh Suever ini memiliki pencarian dokumentasi, Anda mungkin merasa berguna

Luis Mendo

1

Oktaf , 27 byte

@(n)unique(mod((1:n).^2,n))

Cobalah online!

Luis Mendo
sumber

1

Mathematica, 30 byte

Union@Table[Mod[i^2,#],{i,#}]&

Cobalah online!

J42161217
sumber

1

JavaScript (ES6), 48 byte

f=
n=>[...new Set([...Array(n)].map((_,i)=>i*i%n))]

<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>

Luaskan cuplikan

43 byte jika mengembalikan Setbukan array dapat diterima.

Neil
sumber

1

Scala , 32 30 byte

Penggunaan sederhana tip mudah dari OP.

(0 to n-1).map(x=>x*x%n).toSet

Cobalah online!

-2 byte terima kasih kepada @MrXcoder, dengan prioritas (tidak perlu ()sekitar* operasi )

Bertanya-tanya: apakah ini mungkin secara implisit memberitahu kompiler untuk memahami hal-hal seperti (0 to n-1)map(x=>x*x%n)toSet(tanpa harus import scala.language.postfixOps)?

V. Courtois
sumber

1

(0 to n-1).map(x=>x*x%n).toSetselama 30 byte. Eksponensial memiliki prioritas lebih tinggi daripada modulo.

Tn. Xcoder

@ Mr.Xcoder ooh ~ terima kasih :)

V. Courtois

1

Haskell , 44 byte

f m=[k|k<-[0..m],or[mod(n^2)m==k|n<-[0..m]]]

Cobalah online!

Anders Kaseorg
sumber

0

Retina , 70 byte

.+
$*

;$`¶$`
1(?=.*;(.*))|;1*
$1
(1+)(?=((.*¶)+\1)?$)

D`1*¶
^|1+
$.&

Cobalah online! Peringatan: Lambat untuk input besar. Versi 72 byte yang sedikit lebih cepat:

.+
$*

$'¶$';
1(?=.*;(.*))|;1*
$1
+s`^((1+)¶.*)\2
$1
^1+

D`1*¶
^|1+
$.&

Cobalah online!

Neil
sumber

0

Clojure, 40 byte

#(set(map(fn[x](mod(* x x)%))(range %)))

MattPutnam
sumber

0

Perl 6 , 19 byte

{set (^$_)»²X%$_}

Menguji

Diperluas:

{ # bare block lambda with implicit param ｢$_｣

  set        # turn the following into a Set (shorter than ｢unique｣)

      (
        ^$_  # a Range upto (and excluding) ｢$_｣
      )»²    # square each of them (possibly in parallel)

    X%       # cross modulus the squared values by

      $_     # the input
}

Brad Gilbert b2gills
sumber

0

Pyth , 13 byte

VQ aY.^N2Q){Y

Coba online.

Usaha yang lemah untuk menjelaskan:

VQ               for N in [0 .. input-1]
                   blank space to supress implicit print inside the loop
     .^N2Q         N ^ 2 % input
   aY              append that to Y, which is initially an empty list
          )      end for
           {Y    deduplicate and implicit print

Untuk mengurutkan output, masukkan sebuah Sdi sisi mana saja dari{

Saya pikir harus ada cara yang lebih pendek ...

alleks
sumber

1

Ya, gaya fungsional Pyth cenderung jauh lebih ringkas . mapadalah temanmu!

Anders Kaseorg

0

Python 2 , 59 byte

t=int(input())
print list(set([(i*i)%t for i in range(t)]))

Cobalah online!

Husnain Raza
sumber

0

PowerShell , 35 byte

0..($n="$args")|%{$_*$_%$n}|sort -u

Cobalah online!

Joey
sumber

0

R , 28 byte

unique((1:(n<-scan()))^2%%n)

Cobalah online!

Biarawati Bocor
sumber

0

Rubi ,31 30 byte

->m{(0..m).map{|n|n*n%m}.uniq}

Cobalah online!

Alexis Andersen
sumber

0

PHP , 53 byte

for(;$i<$t=$argv[1];)$a[$z=$i++**2%$t]++?:print"$z
";

Ulangi dari 0 ke nomor input, menggunakan n^2 mod baserumus untuk menandai nomor yang telah digunakan. Itu pergi ke posisi itu dalam sebuah array, memeriksa apakah sudah bertambah dan mengeluarkannya jika belum. Itu kemudian bertambah setelah itu sehingga nilai duplikat tidak bisa dicetak.

Cobalah online!

Xanderhall
sumber

0

8 , 138 131 byte

Kode

[] swap dup >r ( 2 ^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip

Penjelasan

[] - Buat array output

swap dup >r - Simpan input untuk digunakan nanti

( 2 ^ r@ n:mod a:push ) 1 rot loop - Hitung ujung kuadrat

rdrop - Bersihkan r-stack

' n:cmp a:sort - Urutkan susunan keluaran

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Singkirkan duplikat berturut-turut dari array

SED (Stack Effect Diagram) adalah:a -- a

Penggunaan dan contoh

: f [] swap dup >r ( 2 n:^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip ;

ok> 120 f .
[0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105]

Kekacauan Manor
sumber

0

Perl 5 , 41 + 1 (-n) = 42 byte

$k{$n++**2%$_}++while$n<$_;say for keys%k

Cobalah online!

Xcali
sumber

Bagaimana ujungnya?

Jawaban:

Jelly , 5 byte

Penjelasan

Google Sheets, 52 51 47 byte

05AB1E , 5 byte

Swift , 47 35 32 * byte

Penjelasan

C #, 63 byte

JavaScript (ES6), 52 byte

Uji kasus

Versi non-rekursif, 60 58 byte

Uji kasus

Pyth, 6 byte

Bagaimana itu bekerja

Brachylog , 10 9 byte

Penjelasan

Japt , 7 6 byte

Penjelasan

Python 3 , 40 39 37 byte

Sebenarnya , 11 byte

CJam , 12 byte

Penjelasan

Haskell , 45 byte

MATL , 6 5 byte

Oktaf , 27 byte

Mathematica, 30 byte

JavaScript (ES6), 48 byte

Scala , 32 30 byte

Haskell , 44 byte

Retina , 70 byte

Clojure, 40 byte

Perl 6 , 19 byte

Diperluas:

Pyth , 13 byte

Python 2 , 59 byte

PowerShell , 35 byte

R , 28 byte

Rubi ,31 30 byte

PHP , 53 byte

8 , 138 131 byte

Perl 5 , 41 + 1 (-n) = 42 byte