En Base-10, todos los cuadrados perfectos terminan en 0 , 1 , 4 , 5 , 6 o 9 .

En Base-16, todos los cuadrados perfectos terminan en 0 , 1 , 4 o 9 .

Nilknarf describe por qué esto es así y cómo resolverlo muy bien en esta respuesta, pero también daré una breve descripción aquí:

Al cuadrar un número de Base 10, N , el dígito "unos" no se ve afectado por lo que está en el dígito "decenas" o el dígito "cientos", y así sucesivamente. Solo el dígito "unos" en N afecta el dígito "unos" en N ² , por lo que una forma fácil (pero quizás no la más elegante) de encontrar todos los últimos dígitos posibles para N ² es encontrar n ² mod 10 para todos 0 <= n < 10 . Cada resultado es un posible último dígito. Para Base-m, puede encontrar n ² mod m para todos 0 <= n < m .

Escriba un programa que, cuando recibe la entrada N , emite todos los últimos dígitos posibles para un cuadrado perfecto en Base-N (sin duplicados). Puede suponer que N es mayor que 0 , y que N es lo suficientemente pequeño como para que N ² no se desborde (si puede probar hasta N ² , le daré una cantidad finita de puntos de brownie, pero sepa que el tipo de cambio de puntos brownie a puntos reales es infinito a uno).

Pruebas:

 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

Este es el código de golf , por lo que se aplican reglas estándar.

(Si considera que esto es demasiado fácil, o si desea una pregunta más detallada sobre el tema, considere esta pregunta: cobertura mínima de las bases para la prueba cuadrática de residuos de la cuadratura ).

Jalea , 5 bytes

R²%³Q

Pruébalo en línea!

Explicación

R²%³Q   Main link, argument: n

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

Hojas de cálculo de Google, 52 51 47 bytes

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

_{^{Guardado 4 bytes gracias a Taylor Scott}}

Las hojas agregarán automáticamente 4 paréntesis de cierre al final de la fórmula.

No devuelve los resultados en orden ascendente, pero devuelve los resultados correctos.

05AB1E , 5 bytes

Lns%ê

Pruébalo en línea! o como un conjunto de pruebas

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

Swift , 47 35 32 * bytes

* -3 gracias a @Alexander.

Posiblemente la primera vez en la historia ¿Los lazos rápidos vencen a Python?

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

Pruébalo en línea!

Explicación

• (0..<m).map{}- Itera a través del rango [0...m)y mapea los siguientes resultados:

• $0*$0%m- El cuadrado de cada número entero módulo la base m.

• Set(...) - Elimina los duplicados.

• m in - Asigna la base a una variable m

C #, 63 bytes

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

Pruébalo en línea!

JavaScript (ES6), 52 bytes

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

Casos de prueba

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

Versión no recursiva, 60 58 bytes

Guardado 2 bytes gracias a @ThePirateBay

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

Casos de prueba

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

Pruébalo en línea

Cómo funciona

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

>ℕ^₂;?%≜ᶠ

Pruébalo en línea!

Explicación

       ≜ᶠ       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Ãâ

Pruébalo

1 byte guardado gracias a Oliver

Explicación

Entrada implícita de entero U.

Ç   Ã

Cree una matriz de enteros desde 0hasta U-1, inclusive y pase cada uno a través de una función.

²

Cuadrado.

%U

Módulo U.

â

Obtenga todos los elementos únicos en la matriz y genere implícitamente el resultado.

Python 3 , 40 39 37 bytes

-1 byte gracias al Sr. Xcoder. -2 bytes gracias a Business Cat.

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

Pruébalo en línea!

En realidad , 11 bytes

;╗r⌠²╜@%⌡M╔

Pruébalo en línea!

Explicación:

;╗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%_&}

Bloqueo anónimo que acepta un número y devuelve una lista.

Pruébalo en línea!

Explicación

_,          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 de Anders Kaseorg

Pruébalo en línea!

MATL , 6 5 bytes

-1 byte gracias a @LuisMendo

:UG\u

Pruébalo en línea!

Octava , 27 bytes

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

Pruébalo en línea!

Mathematica, 30 bytes

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

Pruébalo en línea!

JavaScript (ES6), 48 bytes

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 si devolver un en Setlugar de una matriz es aceptable.

Scala , 32 30 bytes

Uso simple de la sugerencia fácil de OP.

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

Pruébalo en línea!

-2 bytes gracias a @MrXcoder, con prioridades (sin necesidad de ()alrededor* operación)

Preguntándose: ¿es posible decirle al compilador implícitamente que comprenda cosas como (0 to n-1)map(x=>x*x%n)toSet(sin tener que hacerlo import scala.language.postfixOps)?

Haskell , 44 bytes

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

Pruébalo en línea!

Retina , 70 bytes

.+
$*

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

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

Pruébalo en línea! Advertencia: lento para entradas grandes. Versión de 72 bytes ligeramente más rápida:

.+
$*

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

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

Pruébalo en línea!

Clojure, 40 bytes

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

Perl 6 , 19 bytes

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

Pruébalo

Expandido:

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

Probar en línea

Cojo intento de explicar:

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

Para ordenar la salida, inserte un S en cualquier lado del{

Creo que debería haber un camino más corto ...

Python 2 , 59 bytes

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

Pruébalo en línea!

PowerShell , 35 bytes

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

Pruébalo en línea!

R , 28 bytes

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

Pruébalo en línea!

Rubí ,31 30 bytes

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

Pruébalo en línea!

PHP , 53 bytes

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

Pase de 0 al número de entrada, usando la n^2 mod basefórmula para marcar los números que se han usado. Va a esa posición en una matriz, verificando si se ha incrementado y emitiéndola si no lo ha hecho. Luego lo incrementa para que no se impriman valores duplicados.

Pruébalo en línea!

8 ° , 138 131 bytes

Código

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

Explicación

[] - Crear matriz de salida

swap dup >r - Guardar entrada para uso posterior

( 2 ^ r@ n:mod a:push ) 1 rot loop - Calcular extremo cuadrado

rdrop - Limpiar r-stack

' n:cmp a:sort - Ordenar matriz de salida

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Deshágase de los duplicados consecutivos de la matriz

SED (Diagrama de efecto de pila) es:a -- a

Uso y ejemplo

: 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

Pruébalo en línea!