45
\$\begingroup\$

A positive integer \$k\$ is a Loeschian number if

  • \$k\$ can be expressed as \$i^2 + j^2 + i\times j\$ for \$i\$, \$j\$ integers.

For example, the first positive Loeschian numbers are: \$1\$ (\$i=1, j=0\$); \$3\$ (\$i=j=1\$); \$4\$ (\$i=2, j=0\$); \$7\$ (\$i=2, j=1\$); \$9\$ (\$i=-3, j=3\$); ... Note that \$i, j\$ for a given \$k\$ are not unique. For example, \$9\$ can also be generated with \$i=3, j=0\$.

Other equivalent characterizations of these numbers are:

  • \$k\$ can be expressed as \$i^2 + j^2 + i\times j\$ for \$i, j\$ non-negative integers. (For each pair of integers \$i, j\$ there's a pair of non-negative integers that gives the same \$k\$)

  • There is a set of \$k\$ contiguous hexagons that forms a tesselation on a hexagonal grid so that corresponding cells are the same distance apart (see illustrations for \$k = 4\$ and for \$k = 7\$). (Because of this property, these numbers find application in mobile cellular communication networks.)

  • See more characterizations in the OEIS page of the sequence.

The challenge

Given a positive integer, output a truthy result if it is a Loeschian number, or a falsy result otherwise.

The program or function should handle (say in less than a minute) inputs up to \$1000\$, or up to data type limitations.

Code golf. Shortest wins.

Test cases

The following numbers should output a truthy result:

1, 4, 7, 12, 13, 108, 109, 192, 516, 999

The following numbers should output a falsy result:

2, 5, 10, 42, 101, 102, 128, 150, 501, 1000
Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ Related (as noted by @PeterTaylor) \$\endgroup\$
    – Luis Mendo
    Commented Aug 4, 2016 at 15:35
  • \$\begingroup\$ note for the brute force algorithm: if you iterate to √k you reduce algorithm complexity from O(n²) to O(n), at expense of some bytes c; \$\endgroup\$
    – Rod
    Commented Aug 4, 2016 at 17:19
  • 1
    \$\begingroup\$ @Titus Oh now I see. For each pair of integers i, j there's a non-negative pair that gives the same k \$\endgroup\$
    – Luis Mendo
    Commented Jan 6, 2017 at 13:13
  • 1
    \$\begingroup\$ @uhoh Your actual question seems much more complicated though. Sorry that I cannot contribute to it \$\endgroup\$
    – Luis Mendo
    Commented Jun 5, 2020 at 12:59
  • 1
    \$\begingroup\$ Find all integer pairs that produce a given Loeschian number My first question here, I've borrowed from your question quite a bit, but I think the continuity is helpful, and you did such a nice job writing this up. \$\endgroup\$
    – uhoh
    Commented Oct 11, 2020 at 12:43

36 Answers 36

Reset to default
1
2
1
\$\begingroup\$

Husk, 11 bytes

€¹m§+Πṁ□π2ṡ

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 9 8 bytes

Żp`ḋÄ$€i

Try it online!

Returns a non-zero integer for Loeschian numbers and \$0\$ for non-Loeschian numbers

-1 byte thanks to Sisyphus

May be a little cheeky to post, as the only reason this is shorter than Leaky's and Dennis’ Jelly answer is due to newer features, but it's different enough from the existing Jelly answers.

How it works

Żp`ḋÄ$€i - Main link. Takes k on the left
Ż        - Yield [0, 1, 2, ..., k]
  `      - Use this as both left and right argument for:
 p       -   Cartesian power
     $€  - Over each pair, [i, j], run the previous two commands:
    Ä    -   Cumulative sum; [i, i+j]
   ḋ     -   Dot product with [i, j]; Yields i×i+j×(i+j) = i×i + i×j + j×j
           This yields all Loeschian numbers below 3k²
       i - Index of k in this list, or 0 if not found
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Pyth, 17 bytes

.Am+%hd3%h/PQd2{P

Try it online! Test cases

Translation of Dennis's Jelly answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -pal, 50 bytes

$_=grep{//;grep$'*$'+$_*$_+$'*$_=="@F",0..$_}0..$_

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jellyfish, 26 bytes

p
c-&*+S
i*  R
 E  E,r&;32

Try it online!

Judge if the input value is in { (x+y)^2-xy | 0<=x,y<32 } with c

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 51 bytes

k=>g=(z=k*k,i=z/k|0)=>z&&(i+z%k)**2-z%k*i==k|g(z-1)

Try it online!

n^2 time

JavaScript (Node.js), 59 bytes

k=>g=(i=k,j=k)=>i<0|j<0?0:i*i+j*j+i*j-k?g(i-1,j)|g(i,j-1):1

Try it online!

C(2k,k) time

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