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 at 5:22

44 Answers 44

22
\$\begingroup\$

Google Sheets, 52 51 47 bytes

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

Saved 4 bytes thanks to Taylor Scott

Sheets will automatically add 4 closing parentheses to the end of the formula.

It doesn't return the results in ascending order but it does return the correct results.

Results

\$\endgroup\$
5
  • \$\begingroup\$ Holy cow, man that is fricken killer! Who would’ve thought? +1 \$\endgroup\$ Jul 27, 2017 at 22:14
  • 1
    \$\begingroup\$ This is definitely my favorite answer so far. \$\endgroup\$ Jul 28, 2017 at 13:24
  • \$\begingroup\$ @LordFarquaad I am surprised and pleased this was so well received. I've been trying to golf more in Sheets and Excel even though - and partially because - they have such limited ranges. It's led to a lot of array formulas. \$\endgroup\$ Jul 30, 2017 at 1:40
  • \$\begingroup\$ You should be able to drop the terminating )s for -4 bytes \$\endgroup\$ Sep 5, 2017 at 16:10
  • \$\begingroup\$ @TaylorScott Thanks! I saw that trick somewhere recently - probably on one of your answers - and need to remember to start using it. \$\endgroup\$ Sep 5, 2017 at 17:04
9
\$\begingroup\$

Jelly, 5 bytes

R²%³Q

Try it online!

Explanation

R²%³Q   Main link, argument: n

R       Range from 1 to n
 ²      Square each
  %³    Mod each by n
    Q   Deduplicate
\$\endgroup\$
8
\$\begingroup\$

Swift, 47 35 32* bytes

* -3 thanks to @Alexander.

Possibly the first time in history Swift ties beats Python?

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

Try it online!


Explanation

  • (0..<m).map{} - Iterates through the range [0...m) and map the following results:

  • $0*$0%m - The square of each integer modulo the base m.

  • Set(...) - Removes the duplicates.

  • m in - Assigns the base to a variable m

\$\endgroup\$
3
  • \$\begingroup\$ Username checks out... wait a second. \$\endgroup\$ Jul 28, 2017 at 2:50
  • 1
    \$\begingroup\$ More like it beats Python. That is impressive! I thought I would never see the day that would happen. \$\endgroup\$ Jul 28, 2017 at 17:56
  • \$\begingroup\$ @CalebKleveter Thanks! I'm glad you found it impressive :) \$\endgroup\$
    – Mr. Xcoder
    Jul 28, 2017 at 21:29
7
\$\begingroup\$

05AB1E, 5 bytes

Lns%ê

Try it online! or as a Test Suite

L     # Range 1 .. input
 n    # Square each
  s%  # Mod by input
    ê # Uniquify (also sorts as a bonus)
\$\endgroup\$
5
  • \$\begingroup\$ How does s work here? Is the input repeated? \$\endgroup\$
    – Luis Mendo
    Jul 27, 2017 at 14:05
  • \$\begingroup\$ @LuisMendo s is pop a,b; push b,a. When a command tries to pop something from the stack and there isn't anything left the next input is used. If there isn't any more input the last input is used (here is an example). In this case I could have used ¹ which pushes the first input, but s works better for the test suite. \$\endgroup\$
    – Riley
    Jul 27, 2017 at 14:09
  • \$\begingroup\$ Thanks. Do you have more info regarding the criterion for which input gets reused? (if there have been say three inputs and you try to pop two values from an empty stack)? \$\endgroup\$
    – Luis Mendo
    Jul 27, 2017 at 14:13
  • 1
    \$\begingroup\$ @LuisMendo Input is used in order until it runs out, then it continues to use the last element. You could imagine it like the stack was padded with each input in order and an infinite number of the last element. \$\endgroup\$
    – Riley
    Jul 27, 2017 at 14:16
  • \$\begingroup\$ @LuisMendo Ln¹%ê is equivalent here. s. \$\endgroup\$ Jul 27, 2017 at 16:28
5
+100
\$\begingroup\$

APL (Dyalog Unicode), 6 bytes

∪⊢|⍳×⍳

Try it online!

Explanation:

∪⊢|⍳×⍳
   ⍳×⍳    ⍝ square every number in range from 1 to ⍵
 ⊢|       ⍝ modulo ⍵
∪         ⍝ unique elements
\$\endgroup\$
1
  • \$\begingroup\$ 2*⍨⍳ → ⍳×⍳ for -1 byte. \$\endgroup\$
    – Bubbler
    Dec 23, 2020 at 7:45
4
\$\begingroup\$

Pyth, 6 bytes

{%RQ*R

Try it online

How it works

{%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
\$\endgroup\$
4
\$\begingroup\$

Japt, 7 6 bytes

Dz%UÃâ

Test it

1 byte saved thanks to Oliver


Explanation

Implicit input of integer U.

Ç   Ã

Create an array of integers from 0 to U-1, inclusive and pass each though a function.

²

Square.

%U

Modulo U.

â

Get all unique elements in the array and implicitly output the result.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I don't think the range needs to be inclusive. Dz%UÃâ seems to work just fine. \$\endgroup\$
    – Oliver
    Jul 27, 2017 at 20:28
3
\$\begingroup\$

Python 3, 40 39 37 bytes

-1 byte thanks to Mr. Xcoder. -2 bytes thanks to Business Cat.

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

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Can't you replace n**2 with n*n? \$\endgroup\$
    – Mr. Xcoder
    Jul 27, 2017 at 13:44
  • \$\begingroup\$ Yup, always forget that. >< Thanks! \$\endgroup\$ Jul 27, 2017 at 13:44
  • 2
    \$\begingroup\$ Also, just range(m) is sufficient \$\endgroup\$ Jul 27, 2017 at 13:45
  • 1
    \$\begingroup\$ You can use sets for 34 bytes \$\endgroup\$
    – Mr. Xcoder
    Jul 27, 2017 at 13:46
3
\$\begingroup\$

C#, 63 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 52 bytes

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

Test cases

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


Non-recursive version, 60 58 bytes

Saved 2 bytes thanks to @ThePirateBay

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

Test cases

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

\$\endgroup\$
2
  • \$\begingroup\$ Non-recursive 58 bytes: m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v)) \$\endgroup\$
    – user72349
    Jul 27, 2017 at 15:06
  • \$\begingroup\$ @ThePirateBay Good catch. Thanks. \$\endgroup\$
    – Arnauld
    Jul 27, 2017 at 15:10
3
\$\begingroup\$

Brachylog, 10 9 bytes

>ℕ^₂;?%≜ᶠ

Try it online!

Explanation

       ≜ᶠ       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]
\$\endgroup\$
7
  • \$\begingroup\$ I was about to suggest {>≜^₂;?%}ᵘ as an alternative...then I realized there are negative numbers too. >_< \$\endgroup\$ Jul 27, 2017 at 14:23
  • 1
    \$\begingroup\$ @EriktheOutgolfer Once a commit gets pulled to TIO, I can actually reduce this answer to 9 bytes indeed using . \$\endgroup\$
    – Fatalize
    Jul 27, 2017 at 14:43
  • \$\begingroup\$ OK...how would it work when there are negative numbers too? Would it simply ignore them or something? \$\endgroup\$ Jul 27, 2017 at 14:47
  • \$\begingroup\$ @EriktheOutgolfer mod can be defined as remainder of division, which would be positive (the quotient takes the sign). EDIT: also, squares are positive. \$\endgroup\$
    – jaxad0127
    Jul 27, 2017 at 17:05
  • \$\begingroup\$ @jaxad0127 I don't think that's the case here, since > would still account for negative numbers afaik. \$\endgroup\$ Jul 27, 2017 at 17:56
2
\$\begingroup\$

Actually, 11 bytes

;╗r⌠²╜@%⌡M╔

Try it online!

Explanation:

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

CJam, 12 bytes

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

Anonymous block accepting a number and returning a list.

Try it online!

Explanation

_,          Copy n and get the range [0 .. n-1]
  _.*       Multiply each element by itself (square each)
     \f%    Mod each by n
        _&  Deduplicate
\$\endgroup\$
1
  • \$\begingroup\$ Nice! I had {:X{_*X%}%_&} for 13 bytes \$\endgroup\$
    – Luis Mendo
    Jul 27, 2017 at 13:59
2
\$\begingroup\$

Haskell, 45 bytes

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

-4 bytes from Anders Kaseorg

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Sadly point-free version f m=nub$map((`mod`m).(^2))[0..m] is just as long, unless there is a sneaky syntax to get rid of extra parentheses. \$\endgroup\$
    – shooqie
    Jul 27, 2017 at 14:00
2
\$\begingroup\$

MATL, 6 5 bytes

-1 byte thanks to @LuisMendo

:UG\u

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Thanks! I looked through the doc searching for that function but wasn't able to find it. \$\endgroup\$
    – Cinaski
    Jul 28, 2017 at 13:31
  • \$\begingroup\$ BTW this interpreter created by Suever has documentation search, you may find it useful \$\endgroup\$
    – Luis Mendo
    Jul 28, 2017 at 14:11
2
\$\begingroup\$

AWK, 44 43 40 bytes

{for(;i++<$0;)if(!a[j=i*i%$0]++)print j}

I managed to cut off 3 bytes after revisiting this old answer.

Step by step:

{
for(;i++<$0;)        For all numbers less of equal to the input...
            
if(!a[j=i*i%$0]++)   Increments the element j of the array a.
                     j is the last digit of each i*i.
                     If the element a[j] is being incremented
                     for the first time (a[j]++ returns 0,
                     so negating it (!a[j]++) returns 1)...

print j              Prints j.
}

Try it online!

Former answer (43 bytes)

{for(;i++<$0;)a[i*i%$0];for(j in a)print j}

Edit: Incrementing the i variable during the for condition saved one more byte.

Step by step:

{                        
for(;               # starts the loop with no previous statement.
    i++<$0;)        # loops while _i_ is less than the input ($0).
                    # also increments 1 to the _i_ variable after
                    # it is evaluated.

    a[i*i%$0];      # fiat the _i*i%$0_ element of the _a_ array!
                    # by only stating _array[element]_, the element exists.
                    # i*i%$0 means: i squared (mod $0), i.e., the last digit.

for(j in a)         # for every element _j_ existing in the _a_ array,
    print j         # prints the element _j_
}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Octave, 27 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 30 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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 if returning a Set instead of an array is acceptable.

\$\endgroup\$
1
\$\begingroup\$

Scala, 32 30 bytes

Simple use of the easy tip from OP.

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

Try it online!

-2 bytes thanks to @MrXcoder, with priorities (no need for () around * operation)

Wondering: is this possible to implicitly tell the compiler to understand things like (0 to n-1)map(x=>x*x%n)toSet (without having to import scala.language.postfixOps)?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ (0 to n-1).map(x=>x*x%n).toSet for 30 bytes. Exponentiation has higher precedence than modulo. \$\endgroup\$
    – Mr. Xcoder
    Jul 27, 2017 at 14:23
  • \$\begingroup\$ @Mr.Xcoder ooh~ thanks :) \$\endgroup\$ Jul 27, 2017 at 14:26
1
\$\begingroup\$

Haskell, 44 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 19 bytes

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

Test it

Expanded:

{ # 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
}
\$\endgroup\$
1
\$\begingroup\$

Ruby, 31 30 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Whispers v2, 71 bytes

> Input
>> [1)
>> L²
>> L%1
>> Each 3 2
>> Each 4 5
>> {6}
>> Output 7

Try it online!

The TIO Footer simply sorts the output, remove it to see the unsorted set.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 5 bytes

ɾ²$%U

Try it Online!

ɾ     # 1...n
 ²    # Each squared
   %  # Modulo...
  $   # input
    U # Uniquify the result
\$\endgroup\$
1
\$\begingroup\$

Nibbles, 5 bytes

`$.,$%^$~@

Attempt This Online!

`$ Deduplicate
.   map
,    range
$     input
%    mod
^     power
$      it
~      2
@     input
\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 4 bytes

L²ŒU

Try it online!

Explanation

L²ŒU  # Implicit input
L     # Push [0..input)
 ²    # Square each value
  Π  # Mod by input
   U  # Uniquify
      # Implicit output
\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 11 10 bytes

{?x!*/&=x}

Try it online!

  • &=x generate a list containing (0..x; 0..x)
  • */ multiply the two items of the list together
  • x! mod the result by x
  • ? (implicitly) return the distinct last digits
\$\endgroup\$
0
\$\begingroup\$

Retina, 70 bytes

.+
$*

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

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

Try it online! Warning: Slow for large inputs. Slightly faster 72-byte version:

.+
$*

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

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

Try it online!

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

Clojure, 40 bytes

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

Your Answer

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

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