Is this number Loeschian?

Jelly, 11 9 bytes

ÆF‘%3,2ḄȦ

Try it online! or verify all test cases.

Background

In Elementary results on the binary quadratic form a² + ab + b², the author proves the following theorem about Löschian numbers.

Theorem 16. The necessary and sufficient condition of any non-negative integer to be in the form a² + ab + b² is that, in its prime factorization, all primes other than 3 that are not in the form (6k + 1) have even exponents.

As noted on the relevant OEIS page, since all integers are are congruent to 0, 1 or 2 modulo 3, the number 3 is the only prime that is congruent to 0, and all numbers of the form (6k + 1) are congruent to 1, the theorem can be stated alternatively as follows.

A non-negative integer n is a Löschian number if and only if all prime factors of n that are congruent to 2 modulo 3 have even exponents.

How it works

ÆF‘%3,2ḄȦ  Main link. Argument: n (integer)

ÆF         Yield the prime factorization of n, as prime-exponent pairs.
  ‘        Increment all primes and exponents, turning primes of the form 3k - 2
           into multiples of 3 and odd exponents into multiples of 2.
   %3,2    Reduce all incremented primes/exponents modulo 3/2.
           n is Löschian if and only if this does not result in a [0, 0] pair.
           Due to Jelly's form of vectorization, this yields [3, 2] if n = 1.
       Ḅ   Unbinary; convert each pair from base 2 to integer.
           Note that [x, y] = [0, 0] if and only if 2x + y = 0.
        Ȧ  All; return 1 if the result contains no zeroes, 0 otherwise.

Retina, 66 63 45 43 36 bytes

^()(\1(?<1>.\1))+(\1(.(?(4).\4)))*$

Despite the title saying Retina, this is just a plain .NET regex which accepts unary representations of Loeschian numbers.

Inputs 999 and 1000 take well under a second.

Try it online! (The first line enables a linefeed-separated test suite, and the next two take care of the conversion to unary for convenience.)

Explanation

The solution is based on the classification that the input can be written as i*i + j*(i + j) for positive i and non-negative j (since we don't have to handle input 0), and that n*n is just the sum of the first n odd integers. Golfing this was an interesting exercise in forward references.

A "forward reference" is when you put a backreference inside the group it refers to. Of course that doesn't work when the group is used the first time, since there is nothing to be backreferenced yet, but if you put this in a loop, then the backreference gets the previous iteration's capture each time. This in turn, let's you build up a larger capture with each iteration. This can be used to craft very compact patterns for things like triangular numbers, squares and Fibonacci numbers.

As an example, using the fact that squares are just sums of the first n odd integers, we can match a square input like this:

(^.|..\1)+$

On the first iteration, ..\1 can't work, because \1 doesn't have a value yet. So we start with ^., capturing a single character into group 1. On subsequent iterations, ^. no longer matches due to the anchor, but now ..\1 is valid. It matches two more characters than the previous iteration and updates the capture. This way we match increasing odd numbers, getting a square after each iteration.

Now unfortunately, we can't use this technique as is. After matching i*i, we need to get i as well, so that we can multiply it by j. A simple (but long) way to do this is to make use of the fact that matching i*i takes i iterations, so that we've captured i things in group 1. We could now use balancing groups to extract this i, but like I said that's expensive.

Instead, I figured out a different way to write this "sum of consecutive odd integers" that also yields i in a capturing group at the end. Of course the ith odd number is just 2i-1. This gives us a way to increment the forward reference only by 1 on each iteration. That's this part:

^()(\1(?<1>.\1))+

This () just pushes an empty capture onto group 1 (initialising i to 0). This is pretty much equivalent to the ^.| in the simple solution above, but using | in this case would be a bit trickier.

Then we have the main loop (\1(?<1>.\1)). \1 matches the previous i, (?<1>.\1) then updates group 1 with i+1. In terms of the new i, we've just matched 2i-1 characters. Exactly what we need.

When we're done, we've matched some square i*i and group 1 still holds i characters.

The second part is closer to the simple square matching I showed above. Let's ignore the backreference to 1 for now:

(.(?(4).\1))*

This is basically the same as (^.|..\4)*, except that we can't make use of ^ because we're not at the start of the string. Instead we make use of a conditional, to match the additional .\1 only when we've already used group 4. But in effect this is exactly the same. This gives us j*j.

The only thing that's missing is the j*i term. We combine this with the j*j by making use of the fact that the j*j computation still takes j iterations. So for each iteration we also advance the cursor by i with \1. We just need to make sure not to write that into group 4, because that would mess with matching consecutive odd numbers. That's how we arrive at the:

(\1(.(?(4).\1)))*

CJam (16 15 bytes)

{mF{~\3%2=&},!}

Online demo

This is a block (an "anonymous function") which takes input on the stack and leaves 0 or 1 on the stack. It uses the characterisation that a number is Loeschian iff it has no prime factor equal to 2 mod 3 with odd multiplicity.

Thanks to Dennis for a one-byte saving.