30
\$\begingroup\$

In base-10, all perfect squares end in \$0\$, \$1\$, \$4\$, \$5\$, \$6\$, or \$9\$.

In base-16, all perfect squares end in \$0\$, \$1\$, \$4\$, or \$9\$.

Nilknarf describes why this is and how to work this out very well in this answer, but I'll also give a brief description here:

When squaring a base-10 number, \$N\$, the "ones" digit is not affected by what's in the "tens" digit, or the "hundreds" digit, and so on. Only the "ones" digit in \$N\$ affects the "ones" digit in \$N^2\$, so an easy (but maybe not golfiest) way to find all possible last digits for \$N^2\$ is to find \$n^2 \mod 10\$ for all \$0 \le n < 10\$. Each result is a possible last digit. For base-\$m\$, you could find \$n^2 \mod m\$ for all \$0 \le n < m\$.

Write a program which, when given the input \$N\$, outputs all possible last digits for a perfect square in base-\$N\$ (without duplicates). You may assume \$N\$ is greater than \$0\$, and that \$N\$ is small enough that \$N^2\$ won't overflow (If you can test all the way up to \$N^2\$, I'll give you a finite amount of brownie points, but know that the exchange rate of brownie points to real points is infinity to one).

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

this is , so standard rules apply!

(If you find this too easy, or you want a more in-depth question on the topic, consider this question: Minimal cover of bases for quadratic residue testing of squareness).

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Does the output array need to be sorted? \$\endgroup\$
    – Shaggy
    Jul 27, 2017 at 13:41
  • \$\begingroup\$ @Shaggy Nope! Mego, Duplication is not allowed. Theoretically, N could be enormous, so duplicates would make the output pretty unreadable. I'll adit the question \$\endgroup\$ Jul 27, 2017 at 13:41
  • \$\begingroup\$ Is outputting a set acceptable? \$\endgroup\$ Jul 27, 2017 at 13:47
  • 5
    \$\begingroup\$ @totallyhuman Why wouldn't it be valid? Sets are unordered collections and it must not be sorted, so... \$\endgroup\$
    – Mr. Xcoder
    Jul 27, 2017 at 13:47
  • \$\begingroup\$ en.wikipedia.org/wiki/… for a table of testcases from 0 to 75. \$\endgroup\$
    – bigyihsuan
    Feb 1, 2023 at 5:22

44 Answers 44

1
2
0
\$\begingroup\$

Pyth, 13 bytes

VQ aY.^N2Q){Y

Try online.

Lame attempt at explaining:

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

To sort the output, insert an S on any side of the {

I think there should be a shorter way...

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Yeah, the functional style of Pyth tends to be much more concise. map is your friend! \$\endgroup\$ Jul 28, 2017 at 3:47
0
\$\begingroup\$

Python 2, 59 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PowerShell, 35 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

R, 28 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

PHP, 53 bytes

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

Loop from 0 to the input number, using the n^2 mod base formula to mark numbers that have been used. It goes to that position in an array, checking if it's been incremented and outputting it if it hasn't. It then increments it afterwards so duplicate values don't get printed.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

8th, 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

Explanation

[] - Create output array

swap dup >r - Save input for later use

( 2 ^ r@ n:mod a:push ) 1 rot loop - Compute square end

rdrop - Clean r-stack

' n:cmp a:sort - Sort output array

' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip - Get rid of consecutive duplicates from array

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

Usage and example

: 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]
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 86 77 bytes

n->java.util.stream.IntStream.range(1,n+1).map(a->a*a%n).distinct().toArray()

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Check your byte count, and you can save by using java.util.stream.IntStream instead of the import. \$\endgroup\$
    – Jakob
    Sep 5, 2017 at 17:13
0
\$\begingroup\$

Pari/GP, 25 bytes

n->Set([x^2%n|x<-[1..n]])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -MList::Util=uniq -na, 32 bytes

say for uniq map$_**2%"@F",0..$_

Try it online!

\$\endgroup\$
0
+100
\$\begingroup\$

Prolog (SWI), 49 bytes

N+X:-setof(K,A^(between(0,N,A),K is A^2mod N),X).

Try it online!

Creates a set of values from K=(A^2)%N, where 0<=A<=N.

\$\endgroup\$
0
\$\begingroup\$

Pyt, 7 bytes

Đř²⇹%Ụş

Try it online!

Đ            implicit input (n); Đuplicate on stack
 ř           řangify (push [1,2,...,n])
  ²          square
   ⇹%        modulo n
     Ụş      get Ụnique elements and şort in ascending order; implicit print
\$\endgroup\$
0
\$\begingroup\$

Thunno D, \$ 6 \log_{256}(96) \approx \$ 4.94 bytes

R2^$ZU

Attempt This Online!

Thunno, \$ 7 \log_{256}(96) \approx \$ 5.76 bytes

DR2^$ZU

Attempt This Online!

Explanation

DR2^$ZU  # Implicit input
DR       # Duplicate and get range(input)
  2^     # Square each number
    $    # Mod by the input
     ZU  # Uniquify
         # Implicit output
\$\endgroup\$
0
\$\begingroup\$

JavaScript, 45 bytes

n=>(g=x=>x?g(g[x*x%n]=x-1):Object.keys(g))(n)

Try it online!

40 bytes

With output as an array that could contain multiple empty items.

n=>(g=x=>x?g(x-1,a[y=x*x%n]=y):a)(a=[n])

Try it online!

\$\endgroup\$
0
\$\begingroup\$

J, 10 bytes

~.@:|2^~i.

Attempt This Online!

~.@:|2^~i.
        i.  NB. range [0..n)
     2^~    NB. square
  @:        NB. then
~.          NB. uniquify
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.