20

W Base-10 wszystkie idealne kwadraty kończą się cyframi 0 , 1 , 4 , 5 , 6 lub 9 .

W Base-16 wszystkie idealne kwadraty kończą się cyframi 0 , 1 , 4 lub 9 .

Nilknarf opisuje, dlaczego tak jest i jak to bardzo dobrze rozwiązać w tej odpowiedzi, ale dam również krótki opis tutaj:

Kwadratowa liczba Base-10, N , cyfra „jedynki” nie ma wpływu na to, co jest w cyfrze „dziesiątki” lub cyfra „setki” i tak dalej. Tylko cyfra „jedynki” w N wpływa na cyfrę „jedynki” w N ² , więc łatwym (ale może nie najbardziej golfowym) sposobem znalezienia wszystkich możliwych ostatnich cyfr dla N ² jest znalezienie n ² mod 10 dla wszystkich 0 <= n < 10 . Każdy wynik jest możliwą ostatnią cyfrą. Dla Base-m można znaleźć n ² mod m dla wszystkich 0 <= n < m .

Napisz program, który otrzyma wejście N , wypisuje wszystkie możliwe ostatnie cyfry idealnego kwadratu w Base-N (bez duplikatów). Możesz założyć, że N jest większe od 0 i że N jest wystarczająco małe, aby N ² się nie przelał (jeśli możesz przetestować aż do N ² , dam ci skończoną liczbę punktów brownie, ale wiedz, że kurs wymiany punktów brownie na punkty rzeczywiste wynosi nieskończoność do jednego).

Testy:

 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

to jest golf golfowy , więc obowiązują standardowe zasady!

(Jeśli uznasz to za zbyt łatwe lub chcesz uzyskać bardziej dogłębne pytanie na ten temat, rozważ to pytanie: Minimalne pokrycie zasad dla kwadratowego badania pozostałości kwadratowości ).

code-golf number-theory abstract-algebra

— Lord Farquaad
źródło

1

Czy tablica wyjściowa musi zostać posortowana?

— Kudłaty

@Shaggy Nope! Mego, powielanie jest niedozwolone. Teoretycznie N może być ogromny, więc duplikaty spowodują, że wynik będzie bardzo nieczytelny. Odpowiem na pytanie

— Lord Farquaad,

Czy wyjście zestawu jest dopuszczalne?

— całkowicieludzki 27.07.17

2

@totallyhuman Dlaczego to nie byłoby ważne? Zestawy są nieuporządkowanymi kolekcjami i nie można ich sortować , więc ...

— Mr. Xcoder

8

Galaretka , 5 bajtów

R²%³Q

Wypróbuj online!

Wyjaśnienie

R²%³Q   Main link, argument: n

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

— Business Cat
źródło

19

Arkusze Google, 52 51 47 bajtów

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

_{^{Zaoszczędź 4 bajty dzięki Taylor Scott}}

Arkusze automatycznie dodają 4 nawiasy zamykające na końcu formuły.

Nie zwraca wyników w kolejności rosnącej, ale zwraca prawidłowe wyniki.

— Inżynier Toast
źródło

Święta krowa, człowiek, który jest zabójcą! Kto by pomyślał? +1

— bearacuda13

1

To zdecydowanie moja ulubiona odpowiedź.

— Lord Farquaad

@ LordFarquaad Jestem zaskoczony i zadowolony, że został tak dobrze przyjęty. Próbowałem więcej grać w golfa w Arkuszach i Excelu, chociaż - i częściowo dlatego - że mają tak ograniczone zasięgi. Doprowadziło to do wielu formuł tablicowych.

— Engineer Toast

Powinieneś być w stanie usunąć kończące )s dla -4 bajtów

— Taylor Scott

@TaylorScott Thanks! Ostatnio widziałem tę sztuczkę - prawdopodobnie na jednej z twoich odpowiedzi - i muszę pamiętać, aby zacząć z niej korzystać.

— Engineer Toast,

6

05AB1E , 5 bajtów

Lns%ê

Wypróbuj online! lub jako pakiet testowy

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

— Riley
źródło

Jak stu działa? Czy dane są powtarzane?

— Luis Mendo

@LuisMendo sjest pop a,b; push b,a. Gdy polecenie próbuje wyskoczyć coś ze stosu i nic nie pozostało, używane jest następne wejście. Jeśli nie ma już żadnych danych wejściowych, używane jest ostatnie wejście ( oto przykład ). W tym przypadku mogłem użyć, ¹który wypycha pierwsze wejście, ale sdziała lepiej dla zestawu testowego.

— Riley

Dzięki. Czy masz więcej informacji na temat kryterium, dla którego dane wejściowe są ponownie wykorzystywane? (jeśli powiedziano trzy dane wejściowe i próbujesz usunąć dwie wartości z pustego stosu)?

— Luis Mendo

1

@LuisMendo Input jest używane w kolejności, aż skończy się, a następnie nadal używa ostatniego elementu. Można to sobie wyobrazić, jakby stos był uzupełniany kolejnymi wejściami i nieskończoną liczbą ostatniego elementu.

— Riley

@LuisMendo Ln¹%êjest tutaj równoważne. s.

— Magic Octopus Urn

6

Swift , 47 35 32 * bajtów

* -3 dzięki @Alexander.

Być może pierwszy raz w historii Szybkie ~~więzi~~ pokonały Pythona?

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

Wypróbuj online!

Wyjaśnienie

(0..<m).map{}- Iteruje przez zakres [0...m)i mapuje następujące wyniki:
$0*$0%m- Kwadrat każdej liczby całkowitej modulo podstawy m.
Set(...) - Usuwa duplikaty.
m in - Przypisuje bazę do zmiennej m

— Pan Xcoder
źródło

Nazwa użytkownika jest sprawdzana ... poczekaj sekundę.

— Rohan Jhunjhunwala

1

Bardziej, niż bije Python. To imponujące ! Myślałem, że nigdy nie zobaczę dnia, który się wydarzy.

— Caleb Kleveter

@CalebKleveter Dzięki! Cieszę się, że zrobiłeś wrażenie :)

— Mr. Xcoder

3

C #, 63 bajty

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

Wypróbuj online!

— TheLethalCoder
źródło

3

JavaScript (ES6), 52 bajty

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

Przypadki testowe

Pokaż fragment kodu

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

Rozwiń fragment kodu

Wersja nierekurencyjna, 60 58 bajtów

Zaoszczędź 2 bajty dzięki @ThePirateBay

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

Przypadki testowe

Pokaż fragment kodu

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

Rozwiń fragment kodu

— Arnauld
źródło

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

@ThePirateBay Dobry połów. Dzięki.

— Arnauld

3

Pyth, 6 bajtów

{%RQ*R

Wypróbuj online

Jak to działa

{%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
źródło

3

Brachylog , 10 9 bajtów

>ℕ^₂;?%≜ᶠ

Wypróbuj online!

Wyjaśnienie

       ≜ᶠ       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]

— Fatalizować
źródło

Chciałem zasugerować {>≜^₂;?%}ᵘjako alternatywę ... wtedy zdałem sobie sprawę, że są też liczby ujemne. > _ <

— Erik the Outgolfer

1

@EriktheOutgolfer Po zatwierdzeniu do TIO mogę faktycznie zmniejszyć tę odpowiedź do 9 bajtów, używając ≜.

— Fatalize

OK ... jak by to działało, gdy są też liczby ujemne? Czy po prostu je zignoruje?

— Erik the Outgolfer

@EriktheOutgolfer mod można zdefiniować jako pozostałą część podziału, która byłaby dodatnia (iloraz przyjmuje znak). EDYCJA: również kwadraty są dodatnie.

— jaxad0127

@ jaxad0127 Nie sądzę, że tak jest w tym przypadku, ponieważ >nadal uwzględniają liczby ujemne afaik.

— Erik the Outgolfer

3

Japt , 7 6 bajtów

Ç²%UÃâ

Sprawdź to

1 bajt zapisany dzięki Oliverowi

Wyjaśnienie

Domniemane wprowadzenie liczby całkowitej U.

Ç   Ã

Utwórz tablicę liczb całkowitych od 0do U-1, włącznie i przekaż każdą funkcję.

²

Plac.

%U

Modulo U.

â

Pobierz wszystkie unikalne elementy z tablicy i niejawnie wyślij wynik.

— Kudłaty
źródło

1

Nie sądzę, że zakres musi obejmować. Ç²%UÃâwydaje się działać dobrze.

— Oliver

2

Python 3 , 40 39 37 bajtów

-1 bajt dzięki Mr. Xcoder. -2 bajty dzięki Business Cat.

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

Wypróbuj online!

— całkowicie ludzki
źródło

1

Nie można zastąpić n**2z n*n?

— Pan Xcoder

Tak, zawsze o tym zapominaj. > <Dzięki!

— całkowicie ludzki

2

Również range(m)wystarczy

— Business Cat

1

Możesz użyć zestawów dla 34 bajtów

— Mr. Xcoder

2

Właściwie 11 bajtów

;╗r⌠²╜@%⌡M╔

Wypróbuj online!

Wyjaśnienie:

;╗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
źródło

2

CJam , 12 bajtów

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

Anonimowy blok akceptujący numer i zwracający listę.

Wypróbuj online!

Wyjaśnienie

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

— Business Cat
źródło

Ładny! Miałem {:X{_*X%}%_&}dla 13 bajtów

— Luis Mendo

2

Haskell , 45 bajtów

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

-4 bajty od Andersa Kaseorga

Wypróbuj online!

— Mego
źródło

Niestety wersja bez punktów f m=nub$map((`mod`m).(^2))[0..m]jest tak samo długa, chyba że istnieje podstępna składnia pozwalająca pozbyć się dodatkowych nawiasów.

— shooqie

2

MATL , 6 5 bajtów

-1 bajt dzięki @LuisMendo

:UG\u

Wypróbuj online!

— Cinaski
źródło

Dzięki! Przejrzałem dokument w poszukiwaniu tej funkcji, ale nie byłem w stanie jej znaleźć.

— Cinaski

BTW, ten interpreter stworzony przez Suever ma wyszukiwanie dokumentacji, może ci się przydać

— Luis Mendo

1

Oktawa , 27 bajtów

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

Wypróbuj online!

— Luis Mendo
źródło

1

Mathematica, 30 bajtów

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

Wypróbuj online!

— J42161217
źródło

1

JavaScript (ES6), 48 bajtów

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>

Rozwiń fragment kodu

43 bajty, jeśli zwracanie Setzamiast tablicy jest dopuszczalne.

— Neil
źródło

1

Scala , 32 lata 30 bajtów

Proste użycie łatwej końcówki z OP.

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

Wypróbuj online!

-2 bajty dzięki @MrXcoder, z priorytetów (nie ma potrzeby ()około *operacji)

Zastanawiasz się: czy jest to możliwe, aby pośrednio powiedzieć kompilatorowi, aby rozumiał takie rzeczy (0 to n-1)map(x=>x*x%n)toSet(bez konieczności import scala.language.postfixOps)?

— V. Courtois
źródło

1

(0 to n-1).map(x=>x*x%n).toSetprzez 30 bajtów. Potęgowanie ma wyższy priorytet niż modulo.

— Pan Xcoder

@ Mr.Xcoder ooh ~ dzięki :)

— V. Courtois

1

Haskell , 44 bajty

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

Wypróbuj online!

— Anders Kaseorg
źródło

0

Siatkówka oka , 70 bajtów

.+
$*

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

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

Wypróbuj online!Ostrzeżenie: Wolno przy dużych wejściach. Nieco szybsza 72-bajtowa wersja:

.+
$*

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

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

Wypróbuj online!

— Neil
źródło

0

Clojure, 40 bajtów

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

— MattPutnam
źródło

0

Perl 6 , 19 bajtów

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

Sprawdź to

Rozszerzony:

{ # 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
źródło

0

Pyth , 13 bajtów

VQ aY.^N2Q){Y

Wypróbuj online.

Kiepska próba wyjaśnienia:

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

Aby posortować dane wyjściowe, wstaw Spo dowolnej stronie pliku{

Myślę, że powinna istnieć krótsza droga ...

— alleks
źródło

1

Tak, funkcjonalny styl Pyth jest zwykle bardziej zwięzły . mapjest twoim przyjacielem!

— Anders Kaseorg,

0

Python 2 , 59 bajtów

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

Wypróbuj online!

— Husnain Raza
źródło

0

PowerShell , 35 bajtów

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

Wypróbuj online!

— Joey
źródło

0

R , 28 bajtów

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

Wypróbuj online!

— Leaky Nun
źródło

0

Rubin ,31 30 bajtów

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

Wypróbuj online!

— Alexis Andersen
źródło

0

PHP , 53 bajty

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

Zapętlaj od 0 do liczby wejściowej, korzystając ze n^2 mod basewzoru, aby zaznaczyć używane liczby. Przechodzi do tej pozycji w tablicy, sprawdzając, czy została zwiększona i wyprowadzając ją, jeśli nie. Następnie zwiększa ją, aby zduplikowane wartości nie zostały wydrukowane.

Wypróbuj online!

— Xanderhall
źródło

0

8th , 138 131 bajtów

Kod

[] 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

Wyjaśnienie

[] - Utwórz tablicę wyjściową

swap dup >r - Zapisz dane wejściowe do późniejszego wykorzystania

( 2 ^ r@ n:mod a:push ) 1 rot loop - Oblicz kwadratowy koniec

rdrop - Czysty stos r

' n:cmp a:sort - Sortuj tablicę wyjściową

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Pozbądź się kolejnych duplikatów z tablicy

SED (diagram efektu stosu) to:a -- a

Zastosowanie i przykład

: 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]

— Dwór Chaosu
źródło

0

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

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

Wypróbuj online!

— Xcali
źródło

Jak kończy się kwadrat?

Galaretka , 5 bajtów

Wyjaśnienie

Arkusze Google, 52 51 47 bajtów

05AB1E , 5 bajtów

Swift , 47 35 32 * bajtów

Wyjaśnienie

C #, 63 bajty

JavaScript (ES6), 52 bajty

Przypadki testowe

Wersja nierekurencyjna, 60 58 bajtów

Przypadki testowe

Pyth, 6 bajtów

Jak to działa

Brachylog , 10 9 bajtów

Wyjaśnienie

Japt , 7 6 bajtów

Wyjaśnienie

Python 3 , 40 39 37 bajtów

Właściwie 11 bajtów

CJam , 12 bajtów

Wyjaśnienie

Haskell , 45 bajtów

MATL , 6 5 bajtów

Oktawa , 27 bajtów

Mathematica, 30 bajtów

JavaScript (ES6), 48 bajtów

Scala , 32 lata 30 bajtów

Haskell , 44 bajty

Siatkówka oka , 70 bajtów

Clojure, 40 bajtów

Perl 6 , 19 bajtów

Rozszerzony:

Pyth , 13 bajtów

Python 2 , 59 bajtów

PowerShell , 35 bajtów

R , 28 bajtów

Rubin ,31 30 bajtów

PHP , 53 bajty

8th , 138 131 bajtów

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