En Base-10, tous les carrés parfaits se terminent par 0 , 1 , 4 , 5 , 6 ou 9 .

En Base-16, tous les carrés parfaits se terminent par 0 , 1 , 4 ou 9 .

Nilknarf décrit pourquoi c'est et comment cela fonctionne très bien dans cette réponse, mais je vais également donner une brève description ici:

Lors de la mise au carré d'un nombre Base-10, N , le chiffre "un" n'est pas affecté par ce qui est dans le chiffre "dizaines" ou le chiffre "centaines", et ainsi de suite. Seul le chiffre "uns" dans N affecte le chiffre "uns" dans N ² , donc un moyen facile (mais peut-être pas le plus golfique) de trouver tous les derniers chiffres possibles pour N ² est de trouver n ² mod 10 pour tous 0 <= n < 10 . Chaque résultat est un dernier chiffre possible. Pour Base-m, vous pouvez trouver n ² mod m pour tous les 0 <= n < m .

Écrivez un programme qui, quand on lui donne l'entrée N , sort tous les derniers chiffres possibles pour un carré parfait en Base-N (sans doublons). Vous pouvez supposer que N est supérieur à 0 et que N est suffisamment petit pour que N ² ne déborde pas (si vous pouvez tester jusqu'à N ² , je vous donnerai une quantité finie de points brownie, mais sachez que le taux de change des points brownie en points réels est de l'infini à un).

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

c'est du code-golf , donc des règles standards s'appliquent!

(Si vous trouvez cela trop facile, ou si vous voulez une question plus approfondie sur le sujet, considérez cette question: Couverture minimale des bases pour les tests de résidus quadratiques de l'équerrage ).

Gelée , 5 octets

R²%³Q

Essayez-le en ligne!

Explication

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 octets

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

_{^{Enregistré 4 octets grâce à Taylor Scott}}

Les feuilles ajouteront automatiquement 4 parenthèses fermantes à la fin de la formule.

Il ne renvoie pas les résultats dans l'ordre croissant, mais il renvoie les résultats corrects.

05AB1E , 5 octets

Lns%ê

Essayez-le en ligne! ou comme suite de tests

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

Swift , 47 35 32 * octets

* -3 grâce à @Alexander.

Peut - être la première fois dans l' histoire Swift liens bat Python?

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

Essayez-le en ligne!

Explication

• (0..<m).map{}- Itère à travers la plage [0...m)et mappe les résultats suivants:

• $0*$0%m- Le carré de chaque entier modulo la base m.

• Set(...) - Supprime les doublons.

• m in - Attribue la base à une variable m

C #, 63 octets

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

Essayez-le en ligne!

JavaScript (ES6), 52 octets

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

Cas de test

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

Version non récursive, 60 58 octets

Enregistré 2 octets grâce à @ThePirateBay

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

Cas de test

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 octets

{%RQ*R

Essayez-le en ligne

Comment ça fonctionne

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

>ℕ^₂;?%≜ᶠ

Essayez-le en ligne!

Explication

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

Dz%UÃâ

Essaye-le

1 octet sauvé grâce à Oliver

Explication

Saisie implicite d'entier U.

Ç   Ã

Créez un tableau d'entiers de 0à U-1, inclus et passez chacun par une fonction.

²

Carré.

%U

Modulo U.

â

Récupère tous les éléments uniques du tableau et affiche implicitement le résultat.

Python 3 , 40 39 37 octets

-1 octet merci à M. Xcoder. -2 octets grâce à Business Cat.

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

Essayez-le en ligne!

En fait , 11 octets

;╗r⌠²╜@%⌡M╔

Essayez-le en ligne!

Explication:

;╗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 octets

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

Bloc anonyme acceptant un numéro et renvoyant une liste.

Essayez-le en ligne!

Explication

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

Haskell , 45 octets

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

-4 octets d'Anders Kaseorg

Essayez-le en ligne!

MATL , 6 5 octets

-1 octet grâce à @LuisMendo

:UG\u

Essayez-le en ligne!

Octave , 27 octets

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

Essayez-le en ligne!

Mathematica, 30 octets

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

Essayez-le en ligne!

JavaScript (ES6), 48 octets

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 octets si le renvoi d'un Setau lieu d'un tableau est acceptable.

Scala , 32 30 octets

Utilisation simple de la pointe facile d'OP.

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

Essayez-le en ligne!

-2 octets grâce à @MrXcoder, avec des priorités (pas besoin d' ()environ* fonctionnement )

Vous vous demandez: est-ce possible de dire implicitement au compilateur de comprendre des choses comme (0 to n-1)map(x=>x*x%n)toSet(sans avoir à le faire import scala.language.postfixOps)?

Haskell , 44 octets

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

Essayez-le en ligne!

Rétine , 70 octets

.+
$*

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

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

Essayez-le en ligne! Avertissement: lent pour les grandes entrées. Version 72 octets légèrement plus rapide:

.+
$*

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

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

Essayez-le en ligne!

Clojure, 40 octets

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

Perl 6 , 19 octets

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

Essaye-le

Étendu:

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

VQ aY.^N2Q){Y

Essayez en ligne.

Lame tentative d'expliquer:

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

Pour trier la sortie, insérez un Ssur n'importe quel côté du{

Je pense qu'il devrait y avoir un chemin plus court ...

Python 2 , 59 octets

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

Essayez-le en ligne!

PowerShell , 35 octets

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

Essayez-le en ligne!

R , 28 octets

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

Essayez-le en ligne!

Rubis ,31 30 octets

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

Essayez-le en ligne!

PHP , 53 octets

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

Boucle de 0 au numéro d'entrée, en utilisant la n^2 mod baseformule pour marquer les numéros qui ont été utilisés. Il va à cette position dans un tableau, vérifiant s'il a été incrémenté et le sortant s'il ne l'a pas été. Il l'incrémente ensuite pour que les valeurs en double ne soient pas imprimées.

Essayez-le en ligne!

8ème , 138 131 octets

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

Explication

[] - Créer un tableau de sortie

swap dup >r - Enregistrer l'entrée pour une utilisation ultérieure

( 2 ^ r@ n:mod a:push ) 1 rot loop - Calculer l'extrémité carrée

rdrop - R-stack propre

' n:cmp a:sort - Trier le tableau de sortie

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Débarrassez-vous des doublons consécutifs du tableau

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

Utilisation et exemple

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

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

Essayez-le en ligne!