48
\$\begingroup\$

Challenge

So, um, it seems that, while we have plenty of challenges that work with square numbers or numbers of other shapes, we don't have one that simply asks:

Given an integer n (where n>=0) as input return a truthy value if n is a perfect square or a falsey value if not.


Rules

  • You may take input by any reasonable, convenient means as long as it's permitted by standard I/O rules.
  • You need not handle inputs greater than what your chosen language can natively handle nor which would lead to floating point inaccuracies.
  • Output should be one of two consistent truthy/falsey values (e.g., true or false, 1 or 0) - truthy if the input is a perfect square, falsey if it's not.
  • This is so lowest byte count wins.

Test Cases

Input:  0
Output: true

Input:  1
Output: true

Input:  64
Output: true

Input:  88
Output: false

Input:  2147483647
Output: false
\$\endgroup\$
10
  • \$\begingroup\$ @Neil I realized my mistake. I retract that suggestion, and instead offer 18014398509481982 (2**54-2), which is representable with a double, and causes answers that use sqrt to fail. \$\endgroup\$ – user45941 Jun 8 '17 at 12:24
  • \$\begingroup\$ @Mego I'm probably wrong or just misunderstanding what you're saying, but I'm sure 2**54-2 is still larger than a double can safely handle, at least in JavaScript 18014398509481982 > 9007199254740991 \$\endgroup\$ – Tom Jun 8 '17 at 12:32
  • \$\begingroup\$ @Mego I think the limiting value is 9007199515875288. It's not the square of 94906267, because that's not representable in a double, but if you take its square root, then you get that integer as the result. \$\endgroup\$ – Neil Jun 8 '17 at 12:33
  • \$\begingroup\$ @Tom Type 2**54-2 into a JS console, and compare what you get with 18014398509481982 (the exact value). JS outputs the exact value, therefore 2**54-2 is representable with a double. If that still doesn't convince you, take the binary data 0100001101001111111111111111111111111111111111111111111111111111, interpret it as a IEEE-754 double-precision float, and see what value you get. \$\endgroup\$ – user45941 Jun 8 '17 at 12:41
  • 4
    \$\begingroup\$ Sorry, guys, stepped away for lunch and ... well, that escalated! And there I thought this would be a nice, simple challenge! Would adding a rule that you need not handle inputs that lead to floating point inaccuracies in your chosen language cover it? \$\endgroup\$ – Shaggy Jun 8 '17 at 13:17

72 Answers 72

28
\$\begingroup\$

Neim, 2 bytes

qπ•š

Explanation:

q      Push an infinite list of squares
 π•š     Is the input in that list?

When I say 'infinite' I mean up until we hit the maximum value of longs (2^63-1). However, Neim is (slowly) transitioning to theoretically infinitely large BigIntegers.

Try it!

\$\endgroup\$
5
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Dennis Jun 10 '17 at 15:24
  • \$\begingroup\$ Interesting. So, does this pre-buffer the list or is it a generator / iterator that continues checking for the existence of input until it terminates? \$\endgroup\$ – Patrick Roberts Jun 10 '17 at 16:46
  • \$\begingroup\$ @PatrickRoberts Can we talk in chat? \$\endgroup\$ – Okx Jun 10 '17 at 16:51
  • \$\begingroup\$ Sure, just ping me on The Nineteenth Byte. I'm in there occasionally. \$\endgroup\$ – Patrick Roberts Jun 11 '17 at 4:59
  • \$\begingroup\$ Well, this is ... REALLY FUNCTIONAL \$\endgroup\$ – Chromium Jun 15 '18 at 9:03
10
\$\begingroup\$

Jelly, 2 bytes

Ʋ

Try it online!

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Also works with Ohm. \$\endgroup\$ – Nick Clifford Jun 8 '17 at 12:42
8
\$\begingroup\$

TI-Basic, 4 bytes

not(fPart(√(Ans

Simply checks if the square root is an integer by looking for a nonzero fractional/decimal part.

\$\endgroup\$
3
  • \$\begingroup\$ Can you add a TIO (or equivalent)? \$\endgroup\$ – Shaggy Jun 8 '17 at 13:23
  • \$\begingroup\$ @Shaggy I don't think there are any. TI-Basic is proprietary and will only run on TI's calculators and in emulators running the ROM from a calculator, so you cannot legally use TI-Basic if you don't own a calculator. \$\endgroup\$ – Adám Jun 8 '17 at 13:56
  • 1
    \$\begingroup\$ @Shaggy If you have any ROMs you can use an emulator (my preference is jstified) to try this out online. \$\endgroup\$ – Timtech Jun 8 '17 at 15:18
8
\$\begingroup\$

C#, 27 bytes

n=>System.Math.Sqrt(n)%1==0

A more correct/accurate way to do this would be:

n=>System.Math.Sqrt(n)%1<=double.Epsilon*100
\$\endgroup\$
4
  • \$\begingroup\$ double.Epsilon is useless for this type of check. tl;dr: When comparing numbers >2, Double.Epsilon is basically the same as zero. Multiplying by 100 will only delay that a bit. \$\endgroup\$ – Robert Fraser Jun 8 '17 at 14:17
  • \$\begingroup\$ @RobertFraser I only went by the linked SO post and didn't read to much into it. Either way it isn't useless just not to useful at higher numbers. \$\endgroup\$ – TheLethalCoder Jun 8 '17 at 14:21
  • \$\begingroup\$ ...<int>==0 is ...!<int> I think \$\endgroup\$ – Stan Strum Jan 13 '18 at 20:39
  • \$\begingroup\$ @StanStrum Not in C# \$\endgroup\$ – TheLethalCoder Jan 13 '18 at 21:31
7
\$\begingroup\$

JavaScript (ES6), 13 bytes

n=>!(n**.5%1)

Returns true if the square root of n is a whole number.

Snippet:

f=
n=>!(n**.5%1)

console.log(f(0));
console.log(f(1));
console.log(f(2));
console.log(f(4));
console.log(f(8));
console.log(f(16));
console.log(f(88));
console.log(f(2147483647));

\$\endgroup\$
7
\$\begingroup\$

dc, 9

0?dvd*-^p

Outputs 1 for truthy and 0 for falsey.

Try it online.

0            # Push zero.  Stack: [ 0 ]
 ?           # Push input.  Stack: [ n, 0 ]
  dv         # duplicate and take integer square root.  Stack: [ ⌊√nβŒ‹, n, 0 ]
    d        # duplicate.  Stack: [ ⌊√nβŒ‹, ⌊√nβŒ‹, n, 0 ]
     *       # multiply.  Stack: [ ⌊√nβŒ‹Β², n, 0 ]
      -      # take difference. Stack: [ n-⌊√nβŒ‹Β², 0 ]
       ^     # 0 to power of the result.  Stack: [ 0^(n-⌊√nβŒ‹Β²) ]
        p    # print.

Note dc's ^ exponentiation command gives 00=1 and 0n=0, where n>0.

\$\endgroup\$
1
  • \$\begingroup\$ Beautiful! +1 for using dc in such ingenious fashion. \$\endgroup\$ – Wildcard Jun 10 '17 at 0:26
6
\$\begingroup\$

Perl 5, 14 bytes

13 bytes of code + -p flag.

$_=sqrt!~/\./

Try it online!

Computes the square root, and looks if it's an integer (more precisely, if it doesn't contain a dot (/\./).

\$\endgroup\$
6
\$\begingroup\$

Python 3, 19 bytes

lambda n:n**.5%1==0

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Fails for large inputs, e.g. 4111817668062926054213257208. \$\endgroup\$ – L3viathan Jun 8 '17 at 11:41
  • \$\begingroup\$ Fixed in 25 bytes: lambda n:int(n**.5)**2==n \$\endgroup\$ – L3viathan Jun 8 '17 at 11:43
  • 4
    \$\begingroup\$ @L3viathan That (along with any solution that involves sqrt) fails on values which are outside of the range of a double, like 2**4253-1. \$\endgroup\$ – user45941 Jun 8 '17 at 12:30
  • \$\begingroup\$ @totallyhuman a float after %1 is definitely <1, so your proposal would return true for all inputs. Note that n**.5 is a float. \$\endgroup\$ – Leaky Nun Jun 8 '17 at 13:33
6
\$\begingroup\$

Retina, 18 bytes

.+
$*
(^1?|11\1)+$

Try it online! Shamelessly adapted from @MartinEnder's answer to Is this number triangular? but with the base conversion included at a cost of 6 bytes.

Note that Is this number triangular? wasn't for some inexplicable reason required to support zero as a triangular number, so part of the adaption was to add a ? to make the leading 1 optional, allowing the group to match the empty string, and therefore a zero input. However, having now matched the empty string, the + operator stops repeating, to avoid the infinite loop that would happen if it kept greedily matching the empty string (after all, ^1? would certainly keep matching). This means that it doesn't even try to match the other alternative in the group, thus avoiding the match of 2, 6, 12 etc. As @MartinEnder points out, a simpler way to avoid that while still matching the empty string is to anchor the match at the start while making the group optional for the same byte count: ^(^1|11\1)*$.

\$\endgroup\$
5
  • \$\begingroup\$ Looking forward to your explanation why this doesn't match 2, 6 or other numbers of the form n^2-n. ;) (A way to avoid that explanation for the same byte count would be ^(^1|11\1)*$.) \$\endgroup\$ – Martin Ender Jun 8 '17 at 12:54
  • \$\begingroup\$ @MartinEnder Same reason that you couldn't use (^|1\1)+$, I think? \$\endgroup\$ – Neil Jun 8 '17 at 13:12
  • \$\begingroup\$ Yeah that's right. Just thought it would probably be good to mention because most people probably haven't read my comment on the triangular answer (and in this case it's actually relevant to why the solution is correct, as opposed to just why it can't be golfed further). \$\endgroup\$ – Martin Ender Jun 8 '17 at 13:14
  • \$\begingroup\$ For the record, the + would also stop looping if there was no longer an empty alternative, e.g. in the case of ((?(1)11\1|1?))+. Once there was an empty iteration, it won't try any further ones, regardless of whether they may or may not be empty. \$\endgroup\$ – Martin Ender Jun 8 '17 at 13:33
  • \$\begingroup\$ @MartinEnder Indeed, I meant "having now matched" instead of "having immediately matched". Fixed. \$\endgroup\$ – Neil Jun 8 '17 at 14:36
6
\$\begingroup\$

C (gcc), 30 bytes

f(n){n=sqrt(n)==(int)sqrt(n);}

Try it online!

C, 34 bytes

f(n){return(int)sqrt(n)==sqrt(n);}

Try it online!

C, 33 bytes

#define f(n)(int)sqrt(n)==sqrt(n)

Try it online!

\$\endgroup\$
6
\$\begingroup\$

MATL, 5 4 bytes

Thanks to Luis for reducing my one byte longer code by two bytes, making it the shortest one.

t:Um

Try it online

Explanation:

         % Implicit input
t        % Duplicate it
 :       % Range from 1 to input value
  U      % Square the range, to get 1 4 9 ... 
   m     % ismember, Checks if the input is a member of the range of perfect squares

Old answer:

X^1\~

Try it online!

        % Implicit input
X^      % Square root of input
  1\    % Modulus 1. All perfect squares will have 0, the rest will have decimal value
     ~  % Negate, so the 0 becomes 1, and the decimal values become 0
\$\endgroup\$
7
  • \$\begingroup\$ @Mego I disagree. MATL can't even do mod(2**127-, 1000). Unless the four last digits are 0.... \$\endgroup\$ – Stewie Griffin Jun 8 '17 at 12:02
  • \$\begingroup\$ You can also use t:Um. That works for inputs up to 2^53, due to floating point limited precision \$\endgroup\$ – Luis Mendo Jun 8 '17 at 12:30
  • \$\begingroup\$ I see now that this is similar to your edit, only a little shorter :-) \$\endgroup\$ – Luis Mendo Jun 8 '17 at 12:31
  • \$\begingroup\$ Well hidden square command! U: str2num / string to array / square. I knew there had to be a square function, but I couldn't find it... \$\endgroup\$ – Stewie Griffin Jun 8 '17 at 12:32
  • 1
    \$\begingroup\$ @cairdcoinheringaahing that was partially on purpose. I had two solutions, one was 5 bytes, the other one 6 bytes. Luis golfed off two bytes from the one with 6. So I saved two bytes thanks to him, but I only saved a byte on the score... \$\endgroup\$ – Stewie Griffin Jun 8 '17 at 20:49
6
\$\begingroup\$

Python 3, 40 38 bytes

Thanks to squid for saving 2 bytes!

lambda n:n in(i*i for i in range(n+1))

Try it online!

Too slow to return an answer for 2147483647 in a reasonable amount of time. (But written using a generator to save memory, since it doesn't cost any bytes.)

Works in Python 2 also, though an OverflowError is a possibility due to range if you try it with huge inputs. (A MemoryError would also be likely in Python 2, also due to range.)

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

05AB1E, 4 bytes

LnΒΉΓ₯

Try it online!

\$\endgroup\$
7
  • \$\begingroup\$ Doesn't work for large numbers, for example 4111817668062926054213257208 \$\endgroup\$ – Emigna Jun 8 '17 at 11:28
  • \$\begingroup\$ @Emigna Oh because it's considered a long? I thought that 05AB1E uses Python 3. \$\endgroup\$ – Erik the Outgolfer Jun 8 '17 at 11:29
  • \$\begingroup\$ Fails for large inputs (the given input is 2**127-1, a Mersenne prime). \$\endgroup\$ – user45941 Jun 8 '17 at 11:30
  • \$\begingroup\$ It does use python 3. The problem is that square root gives rounding errors for large numbers. \$\endgroup\$ – Emigna Jun 8 '17 at 11:30
  • \$\begingroup\$ @Emigna Oh...I guess I'll have to figure out another way then, shouldn't be hard. \$\endgroup\$ – Erik the Outgolfer Jun 8 '17 at 11:31
5
\$\begingroup\$

SageMath, 9 bytes

is_square

Try it online

The built-in function does exactly what it says on the tin. Since Sage uses symbolic computation, it's free of computational accuracy errors that plague IEEE-754 floats.

\$\endgroup\$
5
\$\begingroup\$

Japt, 3 bytes

Β¬v1

Try it online!

Seems to work fine for 2**54-2 in the Japt Interpreter but fails on TIO for some reason...

\$\endgroup\$
9
  • \$\begingroup\$ Fails for large inputs (input is 2**127-1, a Mersenne prime). \$\endgroup\$ – user45941 Jun 8 '17 at 11:35
  • \$\begingroup\$ @Mego, isn't the norm that solutions need not handle numbers larger than the language is capable of handling? \$\endgroup\$ – Shaggy Jun 8 '17 at 11:36
  • \$\begingroup\$ @Shaggy Japt is based on JavaScript, which uses double-precision floats. 2**127-1 is well within the range of a double. \$\endgroup\$ – user45941 Jun 8 '17 at 11:36
  • 2
    \$\begingroup\$ @Mego Isn't the max safe int for JavaScript 2**53-1? \$\endgroup\$ – Tom Jun 8 '17 at 11:37
  • 3
    \$\begingroup\$ @Mego But JavaScript's numbers only have 53 bits of precision, so JS cannot exactly represent the value 2**127-1 as a number. The closest it can get is 2**127. \$\endgroup\$ – ETHproductions Jun 8 '17 at 17:01
5
\$\begingroup\$

Haskell, 26 24 bytes

f n=elem n$map(^2)[0..n]

Try it online!

Checks if n is in the list of all squares from 0 to n.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ same byte count: f n=or[i*i==n|i<-[0..n]] :) \$\endgroup\$ – vroomfondel Jun 8 '17 at 18:10
5
\$\begingroup\$

Prolog (SWI), 27 bytes

+N:-between(0,N,I),N=:=I*I.

Try it online!

Explanation

Searches through all numbers greater or equal to 0 and less than or equal to N and tests whether that number squared is equal to N.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ @DLosc done! \$\endgroup\$ – 0 ' Jan 15 '18 at 15:36
5
\$\begingroup\$

MathGolf, 1 byte

Β°

Try it online!

I don't think an explanation is needed. I saw the need for an "is perfect square" operator before I saw this challenge, as the language is designed to handle math related golf challenges. Returns 0 or 1, as MathGolf uses integers to represent booleans.

\$\endgroup\$
4
\$\begingroup\$

APL, 5 bytes

βŠ’βˆŠβ³Γ—β³

Explanation:

⊒           N
  ∊         in
    ⍳        numbers up to N
      Γ—     times
        ⍳    numbers up to N

Test:

      ((βŠ’βˆŠβ³Γ—β³) Β¨ X) ,[Γ·2] X←⍳25
1 0 0 1 0 0 0 0 1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
\$\endgroup\$
2
  • \$\begingroup\$ Can you add a TIO (or equivalent)? \$\endgroup\$ – Shaggy Jun 8 '17 at 13:22
  • \$\begingroup\$ doesn't work for 0, but you could do ⊒∊0,⍳×⍳ and it's still the shortest APL answer \$\endgroup\$ – ngn Jun 15 '18 at 11:07
4
\$\begingroup\$

PHP, 21 bytes

<?=(-1)**$argn**.5<2;

If the square root is not an integer number, (-1)**$argn**.5 is NAN.

\$\endgroup\$
3
  • \$\begingroup\$ How do I run this? \$\endgroup\$ – Titus Jun 9 '17 at 8:40
  • \$\begingroup\$ @Titus With the -F flag and pipeline: echo 144 | php -F script.php. \$\endgroup\$ – user63956 Jun 9 '17 at 8:44
  • \$\begingroup\$ Ah I forgot that letter. Thanks. \$\endgroup\$ – Titus Jun 9 '17 at 8:47
4
\$\begingroup\$

R, 15

scan()^.5%%1==0

^.5 is less bytes than sqrt(). %%1, the modulus, will result in 0 if answer is an interger. scan() takes user input.

http://www.tutorialspoint.com/execute_r_online.php?PID=0Bw_CjBb95KQMSm1qVktIOUdSSDg

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

Ruby, 25 bytes

Math.sqrt(gets.to_i)%1==0

There probably is a shorter way but that's all I found.

Try it online!

\$\endgroup\$
4
  • \$\begingroup\$ Welcome to PPCG :) Could you add a TIO (or equivalent) to this, please? \$\endgroup\$ – Shaggy Jun 9 '17 at 8:18
  • \$\begingroup\$ Thanks for adding the TIO however, this doesn't seem to return any output. \$\endgroup\$ – Shaggy Jun 9 '17 at 15:37
  • \$\begingroup\$ My bad, i updated it. \$\endgroup\$ – Gregory Jun 9 '17 at 15:43
  • \$\begingroup\$ Nope, still not working. \$\endgroup\$ – Shaggy Jul 3 '17 at 16:10
4
+100
\$\begingroup\$

Factor + math.unicode, 20 17 bytes

Saved 3 bytes thanks to @chunes!

[ √ dup ⌊ = ]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ You can save 3 bytes with math.unicode. Try it online! \$\endgroup\$ – chunes Mar 25 at 21:57
  • \$\begingroup\$ @chunes Thanks (that'll be a useful vocabulary in the future too)! \$\endgroup\$ – user Mar 25 at 22:03
4
\$\begingroup\$

Regex (ECMAScript / Python or better), 50 bytes

^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+$))\5){2})*x?$

Try it online!

This regex is explained in Match strings whose length is a fourth power. teukon and I arrived at it independently, starting on 2014-02-22, though golfing it down to this point took him 2 days and took me 4 days. It works by dividing away squared prime factors one at a time, thus keeping the number's property of being a square at every step iff it started out being a square. This regex represents a local minimum in length; it's the shortest form that this particular algorithm can be golfed into. It can be modified to match Nth powers by changing the 2 in {2} to N.

Regex (ECMAScript), 28 bytes

^(x(x*)|)(?=(\1*)\2+$)\1*$\3

Try it online!

^              # tail = C = input number
(x(x*)|)       # \1 = A = conjectured square root of C; \2 = A-1, or unset if A==0,
               # allowing us to match C==0 using ECMAScript NPCG behavior; tail -= A
(?=
    (\1*)\2+$  # iff A*A==C, the first match here must result in \3==0
)
\1*$\3         # assert A divides tail, and \3==0

This ultimate form of this was arrived upon from 2014-03-02 to 2014-03-04 through several rounds of golfing between teukon and me, after we had already independently come up with the coprime moduli method of generalized multiplication (which took him 3 hours and took me almost 2 days). I came up with the idea to do one of the tests as (\1*)\2+$ followed by testing if \3==0 although it didn't improve my regex's overall length at the time, and he came up with the idea to combine the \3==0 test and \1*$ test into one, as \1*$\3, thus doing the \1*$ test at the end instead of the beginning (which sacrifices speed in the name of golf, assuming the regex engine doesn't optimize it). (That is with the group numbering of the fully golfed form mapped onto the snippets.)

I've explained the generalized multiplication algorithm in this post, but since its application to squares is simpler, I'm including an explanation for that here.

To explain why this works, let's rearrange the order of the assertions:

(?=
    \1*$       # assert that A divides C-A
)
(?=
    (\1*)\2+$  # iff A*A==C, the first match here must result in \3==0
)
.*$\3          # assert that \3==0

We have \$A^2 \stackrel{?}{=} C\$. If this assertion were true, we would have:

\$\begin{aligned}C &= A^2 \\ C-A &= A^2-A \\ &= (A-1)A\end{aligned}\$

This shows that the assertions made by the regex will hold true if \$C=A^2\$:

\$\begin{aligned}C-A &\equiv 0 \pmod A \\ C-A &\equiv 0 \pmod {A-1}\end{aligned}\$

Note that in regex, \$0 \equiv 0 \pmod 0\$, so the algorithm works for \$C=1^2\$ and \$A=1\$ without any need for a special case. It also works for \$C=0\$, matching it using ECMAScript NPCG (unset/non-participating capture group) behavior – every assertion becomes \$0 \equiv 0 \pmod 0\$ and passes.

Assuming \$A>1\$, these can be simplified into:

\$\begin{aligned}C &\equiv 0 \pmod A \\ C &\equiv 1 \pmod {A-1}\end{aligned}\$

We now have two coprime moduli, \$A\$ and \$A-1\$. By the Chinese remainder theorem, there is one and only one integer \$E\$ such that \$0 \le E < A(A-1)\$ and the above moduli are satisfied. That applies to any window of the same length, so we can change it to \$A < E \le A^2\$.

\$A^2-A=(A-1)A\$ shows there is at least one \$E\$ satisfying the moduli: \$E=A^2\$. The Chinese remainder theorem shows that there is exactly one \$E\$ satisfying the moduli within a certain range. Thus, if we restrict our search to the range \$A < E \le A^2\$, the only value matching both moduli will be \$E=A^2\$.

The first thing the regex does is (x(x*)|) which subtracts \$A\$ from \$C\$, so instead of directly searching for a matching \$E\$, it is searching for a matching \$E-A\$.

(\1*)\2+$ will first attempt a match using the largest possible number of repetitions of \1. Since we already asserted \1*$, this will bring us exactly to $. But then there will be no room for \2+, which is required to have a positive repetition count due to the +. So then it starts trying smaller repetition counts for \1, giving \2+ more space in incremental steps of \1, thus resulting in incrementally larger repetition counts for \2. Note that \1\$=A\$ and \2\$=A-1\$. So a successful match of \2+$ represents a value of \$E-A\$ such that \$E-A \equiv 0 \pmod A\$ and \$E-A \equiv 0 \pmod {A-1}\$.

The regex essentially searches for the smallest \$A-1 \le E-A \le C-A\$ satisfying the moduli, or alternatively stated, the smallest \$2A-1 \le E \le C\$ satisfying the moduli. Thus, even if \$C > A^2\$, the first matching \$E\$ it finds will be \$E=A^2\$. Note that the range only had to be restricted to \$A < E\$ via the Chinese remainder theorem, and the regex restricts it to \$2A-1 \le E\$ which is a subset of that range.

If no match is found, then \$C < A^2\$ and we get a non-match. If a match is found, and if \$E-A=C-A\$, then the \1 in (\1*) will have a repetition count of zero, and \3 will capture a value of zero. The regex asserts that \$E=C\$ by asserting that \3 has a value of zero; if this matches, then \$C=A^2\$ and is indeed a perfect square.

Note that in no point in this reasoning did it matter what the value of \$A\$ is. It will only match if \$A^2=C\$. Thus, it doesn't matter whether we search for a matching \$A\$ from smallest to largest or largest to smallest. The regex does the latter, starting at \$A=C\$ and going downward from there in decrements of \$1\$.

Regex (ECMAScript / Python or better), 30 bytes

^(x(x*))(?=(\1*)\2+$)\1*$\3|^$

Try it online! - ECMAScript (SpiderMonkey)
Try it online! - ECMAScript (Node.js - fast)
Try it online! - Perl
Try it online! - Java
Try it online! - Python
Try it online! - Ruby
Try it online! - PCRE (fastest)
Try it online! - .NET

This is a port of the 28 byte version, dropping the dependence on ECMAScript NPCG behavior. Matching \$0^2\$ is done as a special case, the ^$ alternative at the end.

Regex (Perl / Java / PCRE / .NET), 12 bytes

^(\1xx|^x)*$

Try it online! - Perl (fastest)
Try it online! - Java
Try it online! - PCRE (fast)
Try it online! - .NET (slowest)

This works by exploiting the fact that \$(N+1)^2-N^2=2N+1\$, i.e. the differences between consecutive squares are consecutive odd numbers. The loop is initialized by subtracting \$1\$ from tail, which then captures \1=\$1\$. Every subsequent iteration sets \1\$=\$\1\$+2\$ and subtracts \1 from tail. As a result, the cumulative subtraction from tail is at every step a perfect square, and the $ will only match at the end if the subtraction culminates in tail equaling zero, meaning the initial value of tail before the loop started was a perfect square.

As such, this regex relies on being able to read the last captured value of group 1 from inside group 1 – a nested backreference, which is a feature not supported by the ECMAScript, Python, or Ruby regex engines.

In this post by primo, it is explained how to extend this method to higher powers and polynomials.

An alternative 12 byte form is (\1xx|^x?)+$, but this breaks some nice properties of the form shown above. Most notably, it breaks letting the loop iteration count equal the square root of the number being matched. One of the beauties of keeping that property is that we can return the square root, for example using .NET's balanced groups feature (25 bytes):

^(?=(\1xx|^x)*$)(?<-1>x)*

Try it online! - .NET

Or using group-building with a branch reset group (19 bytes):

^(?|\1(\1x)|^(x))*$

Try it online! - Perl
Try it online! - PCRE

Regex (Pythonregex / Ruby or better), 22 bytes

^((?=(\3xx|^x))(\2))*$

Try it online! - Python import regex
Try it online! - Ruby

In regex flavors with no support for nested backreferences, that feature must be emulated via forward-declared backreferences (which aren't supported either by ECMAScript or Python's built-in re module). This is done here by copying back and forth between \2 and \3.

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

PHP, 26 bytes

<?=(0^$q=sqrt($argn))==$q;

Try it online!

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

CJam, 8 bytes

ri_mQ2#=

Try it online!

Explanation

Integer square root, square, compare with original number.

\$\endgroup\$
5
  • \$\begingroup\$ I guess according to this, you don't need the first 2 bytes \$\endgroup\$ – Chromium Jun 15 '18 at 9:05
  • \$\begingroup\$ And, alternatively, using the idea of this answer, you can do mq1%0=, which is also 6 bytes \$\endgroup\$ – Chromium Jun 15 '18 at 9:11
  • \$\begingroup\$ @Chromium Thanks, but in that case I need {...} to make the code a function, so same byte count \$\endgroup\$ – Luis Mendo Jun 15 '18 at 9:21
  • \$\begingroup\$ Actually, I'm a bit confused whether to add curly braces or not. Cuz if you don't add them, it's actually a program, which is permitted. \$\endgroup\$ – Chromium Jun 15 '18 at 9:23
  • \$\begingroup\$ @Chromium A program needs to take its input, so ri is required in that case \$\endgroup\$ – Luis Mendo Jun 15 '18 at 9:27
3
\$\begingroup\$

Mathematica, 13 bytes

AtomQ@Sqrt@#&

Try it online!

\$\endgroup\$
8
  • \$\begingroup\$ No built in? Odd.... \$\endgroup\$ – TheLethalCoder Jun 8 '17 at 12:17
  • 1
    \$\begingroup\$ You can use AtomQ instead of IntegerQ. \$\endgroup\$ – Martin Ender Jun 8 '17 at 13:16
  • 1
    \$\begingroup\$ of course shaggy... \$\endgroup\$ – ZaMoC Jun 8 '17 at 13:44
  • 1
    \$\begingroup\$ You can still use @*. \$\endgroup\$ – Martin Ender Jun 8 '17 at 14:03
  • 4
    \$\begingroup\$ AtomQ@*Sqrt is a synonym for AtomQ@Sqrt@#&. For example, AtomQ@*Sqrt@4 returns True and AtomQ@*Sqrt@5 returns False. (Because of precedence, AtomQ@*Sqrt[4] doesn't work right, returning AtomQ@*2.) \$\endgroup\$ – Greg Martin Jun 8 '17 at 18:39
3
\$\begingroup\$

APL (Dyalog), 8 bytes

0=1|*∘.5

Try it online!

0= [is] zero equal to

1| the modulus-1 (i.e. the fractional part) of

*∘.5 the argument raised to the power of a half

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

AWK, 27+2 bytes

{x=int($0^0.5);$0=x*x==$1}1

Try it online!

Add +2 bytes for using the -M flag for arbitrary precision. I originally used string comparison because large number compared equal, even though they weren't, but the sqrt was also returning imprecise values. 2^127-2 should not be a perfect square.

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

T-SQL, 38 bytes

SELECT IIF(SQRT(a)LIKE'%.%',0,1)FROM t

Looks for a decimal point in the square root. IIF is specific to MS SQL, tested and works in MS SQL Server 2012.

Input is in column a of pre-existing table t, per our input rules.

\$\endgroup\$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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