44
\$\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
\$\endgroup\$
10
  • \$\begingroup\$ Related (as noted by @PeterTaylor) \$\endgroup\$
    – Luis Mendo
    Aug 4 '16 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
    Aug 4 '16 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
    Jan 6 '17 at 13:13
  • 1
    \$\begingroup\$ @uhoh Your actual question seems much more complicated though. Sorry that I cannot contribute to it \$\endgroup\$
    – Luis Mendo
    Jun 5 '20 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
    Oct 11 '20 at 12:43

34 Answers 34

1
2
1
\$\begingroup\$

Husk, 11 bytes

€¹m§+Πṁ□π2ṡ

Try it online!

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

Pyth, 17 bytes

.Am+%hd3%h/PQd2{P

Try it online! Test cases

Translation of Dennis's Jelly answer.

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

Perl 5 -pal, 50 bytes

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

Try it online!

\$\endgroup\$
1
2

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.