In der Basis 10 enden alle perfekten Quadrate auf 0 , 1 , 4 , 5 , 6 oder 9 .

In Basis 16 enden alle perfekten Quadrate mit 0 , 1 , 4 oder 9 .

Nilknarf beschreibt in dieser Antwort, warum dies so ist und wie dies sehr gut funktioniert , aber ich werde hier auch eine kurze Beschreibung geben:

Beim Quadrieren einer Basis-10-Zahl, N , wird die Einerstelle nicht durch die Zehner- oder Hunderter-Stelle usw. beeinflusst. Nur die Einerstelle in N wirkt sich auf die Einerstelle in N ^{2 aus} . Ein einfacher (aber möglicherweise nicht der erfolgreichste) Weg, alle möglichen letzten Stellen für N ² zu finden, besteht darin, n ² mod 10 für alle 0 <= n zu finden < 10 . Jedes Ergebnis ist eine mögliche letzte Ziffer. Für Base-m könnte man n ² mod m für alle 0 <= n < m finden .

Schreiben Sie ein Programm, das bei Eingabe von N alle möglichen letzten Ziffern für ein perfektes Quadrat in Base-N ausgibt (ohne Duplikate). Sie können davon ausgehen , N größer ist 0 , und das N ist klein genug , dass N ² nicht Überlauf (Wenn Sie den ganzen Weg bis testen N ² , gebe ich Ihnen eine endliche Menge Pluspunkte, aber wissen , dass Der Wechselkurs von Brownie-Punkten zu echten Punkten ist unendlich zu eins.

Tests:

 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

Das ist Code-Golf , also gelten die Standardregeln!

(Wenn Ihnen dies zu leicht fällt oder Sie eine ausführlichere Frage zum Thema wünschen, sollten Sie sich diese Frage überlegen: Minimale Abdeckung der Basen für die quadratische Prüfung der Rechtwinkligkeit nach Restwerten ).

Gelee , 5 Bytes

R²%³Q

Probieren Sie es online!

Erläuterung

R²%³Q   Main link, argument: n

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

Google Sheets, 52 51 47 Bytes

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

_{^{4 Bytes gespart dank Taylor Scott}}

Sheets fügt am Ende der Formel automatisch 4 schließende Klammern hinzu.

Es gibt die Ergebnisse nicht in aufsteigender Reihenfolge zurück, aber es gibt die richtigen Ergebnisse zurück.

05AB1E , 5 Bytes

Lns%ê

Probieren Sie es online! oder als Test Suite

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

Swift , 47 35 32 * Bytes

* -3 danke an @Alexander.

Möglicherweise das erste Mal in der Geschichte. Schnelle Verbindungen schlagen Python?

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

Probieren Sie es online!

Erläuterung

• (0..<m).map{}- Durchläuft den Bereich [0...m)und ordnet die folgenden Ergebnisse zu:

• $0*$0%m- Das Quadrat jeder Ganzzahl modulo der Basis m.

• Set(...) - Entfernt die Duplikate.

• m in - Weist die Basis einer Variablen zu m

C #, 63 Bytes

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

Probieren Sie es online!

JavaScript (ES6), 52 Byte

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

Testfälle

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

Nicht-rekursive Version, 60 58 Bytes

2 Bytes dank @ThePirateBay gespart

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

Testfälle

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

Pyth, 6 Bytes

{%RQ*R

Probieren Sie es online aus

Wie es funktioniert

{%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

Brachylog , 10 9 Bytes

>ℕ^₂;?%≜ᶠ

Probieren Sie es online!

Erläuterung

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

Japt , 7 6 Bytes

Dz%UÃâ

Probier es aus

Dank Oliver 1 Byte gespart

Erläuterung

Implizite Eingabe einer Ganzzahl U.

Ç   Ã

Erstellen Sie ein Array von ganzen Zahlen von 0bis U-1einschließlich und übergeben Sie jede durch eine Funktion.

²

Platz.

%U

Modulo U.

â

Holen Sie sich alle eindeutigen Elemente im Array und geben Sie das Ergebnis implizit aus.

Python 3 , 40 39 37 Bytes

-1 Byte danke an Herrn Xcoder. -2 Bytes dank Business Cat.

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

Probieren Sie es online!

Eigentlich 11 Bytes

;╗r⌠²╜@%⌡M╔

Probieren Sie es online!

Erläuterung:

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

CJam , 12 Bytes

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

Anonymer Block, der eine Nummer akzeptiert und eine Liste zurückgibt.

Probieren Sie es online!

Erläuterung

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

Haskell , 45 Bytes

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

-4 Bytes von Anders Kaseorg

Probieren Sie es online!

MATL , 6 5 Bytes

-1 Byte dank @LuisMendo

:UG\u

Probieren Sie es online!

Oktave , 27 Bytes

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

Probieren Sie es online!

Mathematica, 30 Bytes

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

Probieren Sie es online!

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>

43 Bytes, wenn die Rückgabe von a Setanstelle eines Arrays zulässig ist.

Scala , 32 Bytes

Einfache Bedienung mit dem Easy Tip von OP.

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

Probieren Sie es online!

-2 Bytes dank @MrXcoder mit Prioritäten (keine Notwendigkeit für ()um* Operation)

Fragen Sie sich: Ist es möglich , den Compiler implizit anzuweisen, Dinge wie (0 to n-1)map(x=>x*x%n)toSet(ohne dies tun zu müssen import scala.language.postfixOps) zu verstehen ?

Haskell , 44 Bytes

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

Probieren Sie es online!

Netzhaut , 70 Bytes

.+
$*

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

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

Probieren Sie es online! Warnung: Langsam für große Eingaben. Etwas schnellere 72-Byte-Version:

.+
$*

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

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

Probieren Sie es online!

Clojure, 40 Bytes

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

Perl 6 , 19 Bytes

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

Probier es aus

Erweitert:

{ # 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
}

Pyth , 13 Bytes

VQ aY.^N2Q){Y

Versuchen Sie es online.

Lahmer Erklärungsversuch:

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

Um die Ausgabe zu sortieren, fügen Sie an einer Sbeliebigen Seite des ein{

Ich denke, es sollte einen kürzeren Weg geben ...

Python 2 , 59 Bytes

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

Probieren Sie es online!

PowerShell , 35 Byte

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

Probieren Sie es online!

R , 28 Bytes

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

Probieren Sie es online!

Rubin ,31 30 Bytes

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

Probieren Sie es online!

PHP , 53 Bytes

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

Gehen Sie mit der Taste von 0 zur Eingangsnummer n^2 mod base markieren Sie die verwendeten Nummern Formel. Es geht zu dieser Position in einem Array, überprüft, ob es erhöht wurde, und gibt es aus, wenn dies nicht der Fall ist. Anschließend wird es inkrementiert, damit keine doppelten Werte gedruckt werden.

Probieren Sie es online!

8. , 138 131 Bytes

Code

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

Erläuterung

[] - Ausgabe-Array erstellen

swap dup >r - Eingaben zur späteren Verwendung speichern

( 2 ^ r@ n:mod a:push ) 1 rot loop - Quadratisches Ende berechnen

rdrop - R-Stack reinigen

' n:cmp a:sort - Ausgabearray sortieren

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Entfernen Sie aufeinanderfolgende Duplikate aus dem Array

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

Verwendung und Beispiel

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

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

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

Probieren Sie es online!