4
$\begingroup$

I am interested in a quick test to see if a number is a perfect square. One good test is to look at how the number ends. In Base-10, a perfect square ends in 0,1,4,5,6, or 9. This is helpful because I can trivially filter out numbers that end differently before I need to do more expensive operations.

It's also true that in Base-16, a perfect square ends in 0, 1, 4, or 9.

However, if we look at the non-perfect-square numbers 11 and 17, we can see 11 passes the Base-10 test, since 11 mod 10 = 1, but fails the Base-16 test (11 mod 16 = 11). Likewise, 17 fails the Base-10 test, but passes the Base-16 test. I think this is because 10 has a factor that 16 doesn't have, but I'm not sure.

It's easy to see that performing both tests will filter out more numbers than either one on its own, and it stands to reason that there exist more bases which filter out additional numbers.

My question is: Why do these two bases test a different set of numbers, and how could I choose a minimal set of bases which filtered out the most numbers?

(I realize any method of choosing bases can be extended infinitely, but infinity and quick don't exactly get along. I'm more curious into the theory behind this, and I can discuss a test coverage vs. speed tradeoff in Stack Overflow).

$\endgroup$
  • $\begingroup$ the base 16 test is a more restricted version of the base 8 version, which is a more restricted version of the base 4 version. etc. so in short tend the bases to infinity. A possibly easier way is to test divisibility by prime squares. $\endgroup$ – user451844 Jul 26 '17 at 14:08
  • 1
    $\begingroup$ Assuming you are programming in a language that allows you to store a given number using chunks in a given base (e.g., binary, with byte or word chunks), one good way is to store all the squares up to some pre-defined limit. So in bytes, you might choose to find all the squares up to $8$ bytes or $64$ bits in number length, then you would be storing $4$ bytes or about $4$ four billion values. This isn't that much memory for today's computers, and a hash test is $O(1)$. $\endgroup$ – abiessu Jul 26 '17 at 14:16
  • $\begingroup$ @abiessu thanks, that's what I was planning. I think mod 10 is a pretty trivial operation for computers too (I'm pretty sure ALUs optimize that particular calculation), so I might also store a similarly sized list in base 10 and check against both. Once I realized I could do both, though, I just had to come here and check if it was worth stopping at just 2. $\endgroup$ – Lord Farquaad Jul 26 '17 at 14:23
  • $\begingroup$ Have you noticed that base $80$ filters out exactly the same numbers as base $10$ and base $16$ combined? Because of this overlap, you might prefer to consider just prime (or prime-power) bases. $\endgroup$ – Erick Wong Jul 26 '17 at 14:25
  • 3
    $\begingroup$ Related OEIS sequence: oeis.org/A002189 enumerates the smallest non-square value of $n$ which successfully eludes all bases below $k$ for several values of $k$. This should give you a general feel for how large a set of bases you need to capture all numbers of a given size. $\endgroup$ – Erick Wong Jul 26 '17 at 14:27
4
$\begingroup$

NOT an answer, but too long to be a comment.

I would like to include a small proof of the statement that you opened with, for some context. If we have some integer in base $10$, it can be represented as $$n=C_0 10^0+C_1 10^1 +...+ C_k 10^k$$ where each $C_i \lt 10$ and $k+1$ is the number of digits that the integer has. When we square this integer, by expansion, it becomes clear that the only term containing $10^0$ will end up being $$C_0^2 10^0$$ and, since we want to represent its square in base $10$, the first coefficient of its square must be less than $10$, and so the first digit of its square is $$C_0^2 \bmod 10$$ and, since $C_0 \lt 10$, the only possible first digits of $n^2$ are $$1\bmod 10=1$$ $$4\bmod 10=4$$ $$9\bmod 10=9$$ $$16\bmod 10=6$$ $$25\bmod 10=5$$ $$36\bmod 10=6$$ $$49\bmod 10=9$$ $$64\bmod 10=4$$ $$81\bmod 10=1$$ Which proves your statement.

Now we may generalize this to all bases. A number $n$ in base $b$ can be represented by $$n=C_0b^0+C_1b^1+...+C_kb^k$$ Where each $C_i \lt b$ and $k+1$ is the number of digits of $n$ in base $b$. By following the same path as we did in the last proof, the set of all possible smallest digits is the set $$\bigcup \limits_{a=1}^{b-1} \{a^2 \bmod b\}$$ let this set contain $l$ elements. Then you are seeking some base $b_m$ for which the ratio of $l$ to $b_m-1$ is minimized.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Actually, the number has $k+1$ digits. $\endgroup$ – steven gregory Jul 26 '17 at 14:32
  • $\begingroup$ @stevengregory Oh, thanks. :) $\endgroup$ – Franklin Pezzuti Dyer Jul 26 '17 at 14:44
  • $\begingroup$ @Nilknarf thanks, this is a great insight on the problem. Also, I've been testing various power of 2 bases and I've noticed that as bm get bigger (by powers of 2), l:bm - 1 converges to 1/6. For 2^27, this is true for up to 7 decimals. Do you have any reason why this might be? $\endgroup$ – Lord Farquaad Jul 26 '17 at 16:01
  • 1
    $\begingroup$ @LordFarquaad Ooh, interesting. I'll work on it... $\endgroup$ – Franklin Pezzuti Dyer Jul 26 '17 at 16:08
3
$\begingroup$

Checking your candidate number $x\bmod 24$ is quite a good option, especially if you first cast out factors of $4$ and $9$ (to get $x'$). Then you need $x'\equiv 1 \bmod 24$ for a candidate square.

The reason lurking behind this is that the Carmichael function $\lambda(24)=2$, so every co-prime squares to $1 \bmod 24$. Dividing out $4$s and $9$s can only leave zero or one factor of $2$ or $3$ respectively in the modified number (one of either would make it non-square). And $24$ is the largest number with $\lambda=2$.

For checking against any other primes, first reduce the candidate by casting out factors of the square of that prime, then half of the possible values will indicate candidate squares - all the even powers of a primitive root.

| cite | improve this answer | |
$\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.