Rectangles in rectangles

Question

This code-golf challenge will give you two positive integers n and k as inputs and have you count the number of rectangles with integer coordinates that can be drawn with vertices touching all four sides of the \$n \times k\$ rectangle $$ \{(x,y) : 0 \leq x \leq n, 0 \leq y \leq k\}. $$ That is, there should be:

• at least one vertex with an \$x\$-coordinate of \0ドル\$,
• at least one vertex with an \$x\$-coordinate of \$n\$,
• at least one vertex with an \$y\$-coordinate of \0ドル\$, and
• at least one vertex with an \$y\$-coordinate of \$k\$.

Example

There are \$a(5,7) = 5\$ rectangles with integer coordinates touching all four sides of a \5ドル \times 7\$ rectangle:

Five examples of rectangles embedded in the 5 by 7 rectangle.

Table

The lower triangle of the (symmetric) table of \$a(n,k)\$ for \$n,k \leq 12\$ is

n\k| 1 2 3 4 5 6 7 8 9 10 11 12
---+----------------------------------------------
 1 | 1 . . . . . . . . . . .
 2 | 1 2 . . . . . . . . . .
 3 | 1 1 5 . . . . . . . . .
 4 | 1 1 1 6 . . . . . . . .
 5 | 1 1 1 3 9 . . . . . . .
 6 | 1 1 1 1 1 10 . . . . . .
 7 | 1 1 1 1 5 1 13 . . . . .
 8 | 1 1 1 1 1 1 5 14 . . . .
 9 | 1 1 1 1 1 5 1 1 17 . . .
10 | 1 1 1 1 1 3 1 3 1 18 . .
11 | 1 1 1 1 1 1 5 1 5 5 21 .
12 | 1 1 1 1 1 1 1 1 5 1 1 22

---

This is a code-golf challenge, so the shortest code wins.

• ovs: I get 9 distinct rectangles for n=k=5: https://ibb.co/p49WdTc. Am I missing something? I also have larger results on other (bigger) test cases, here is my result for the table.
• Peter Kagey: @ovs—thanks for catching this! The table is updated now.
• xnor: I took a shot at finding a combinatorial expression, but the best I got is: for \$k<n\,ドル the output is \2ドルC-3\,ドル where \$C\$ is the number of positive divisor pairs \$pq=n^2-k^2\$ with \$p\$ and \$q\$ having the same parity and both lying in the interval \$[n-k,n+k]\$. Unfortunately, the last interval condition seems to prevent a characterization in just terms of the factorization of \$n^2-k^2\$ without enumerating divisors. The condition corresponds to the inner rectangle fitting inside the outer one, rather than lying on its edges extended infinitely, a generalization that's easier to count.

Answer 1

Python 2, (削除) 66 (削除ここまで) 59 bytes

lambda n,k:sum(a%n*(n-a%n)==a/n*(k-a/n)for a in range(n*k))

Try it online!

Each possible rectangle inside the \$n \times k\$-rectangle can be specified by two integers, \0ドル \le a \lt n\$ and \0ドル \le b \lt k\$:

enter image description here enter image description here

To verify a rectangle given \$a\$ and \$b\$, it suffices to check if one angle is a right angle. To do this I take the dot product of \$\binom{b}{0}-\binom{0}{a}=\binom{-b}{a}\$ and \$\binom{k-b}{n}-\binom{0}{a}=\binom{k-b}{n-a}\$ to check whether the angle at \$\binom{0}{a}\$ is a right angle:

$$ \langle \left( \begin{matrix} -b \\ a \\ \end{matrix}\right), \left(\begin{matrix} k-b \\ n-a \\ \end{matrix} \right) \rangle = 0 \\\Leftrightarrow a\cdot(n-a)-b\cdot(k-b)=0 \\\Leftrightarrow a\cdot(n-a)=b\cdot(k-b) $$

Answer 2

05AB1E, (削除) 10 (削除ここまで) 8 bytes

LDI-*`¢O

Try it online!

Commented:

 # implicit input: [n, k]
L # for both values take the [1..x] range
 # [[1,...,n], [1,...,k]]
 D # duplicate this list
 I # push the input [n,k]
 - # subtract this from the ranges
 # [[1-n,...,n-n], [1-k,...,k-k]]
 # =[[-n+1,...,0], [-k+1,...,0]]
 * # multiply with the ranges
 # [[1*(-n+1),...,n*0], [1*(-k+1),...,k*0]]
 ` # push all lists of this list on the stack
 ¢ # count the occurences of each value of one list in the other
 O # sum those counts

Answer 3

C (gcc), (削除) 63 (削除ここまで) 61 bytes

Saved 2 thanks to ceilingcat!!!

s;a;f(n,k){for(s=a=n*k;a--;)s-=a%n*(n-a%n)!=a/n*(k-a/n);a=s;}

Try it online!

Port of ovs's Python answer.

Answer 4

Scala, (削除) 65 (削除ここまで) (削除) 64 (削除ここまで) (削除) 60 (削除ここまで) 51 bytes

n=>k=>0 to n*k-1 count(a=>a%n*(n-a%n)==a/n*(k-a/n))

Try it online!

• -1 thanks to user!
• -4 thanks to ovs!
• -9 thanks to Kjetil!

• user: You can save a byte by currying (n=>k=>)
• ovs: You can use 1.to(n) and 1.to(k) for -2 bytes each.
• Kjetil S: Save 9 bytes with Try it online! I just translated the python answer from @ovs.

Answer 5

Charcoal, 21 bytes

×ばつι−θι

Try it online! Link is to verbose version of code. Explanation: Calculates \$ x(n-x) \$ for \$ 0 \le x < n \$ and \$ y(n-y) \$ for \$ 0 \le y < k \$ and counts the number of times an integer appears in both lists, which corresponds to the parallelogram with coordinates \$ (x, 0), (0, y), (n - x, 0), (0, k - y) \$ having 90 degree angles:

NθNη

Input \$ n \$ and \$ k \$.

IΣ

Output the total sum of all matches found.

×ばつλ−ηλ

Calculate \$ y(n-y) \$ for \$ 0 \le y < k \$.

×ばつι−θι

Calculate \$ x(n-x) \$ for \$ 0 \le x < n \$ and count how many times each integer appears in the other list.

Answer 6

JavaScript (ES6), (削除) 63 58 (削除ここまで) 56 bytes

Saved 2 bytes thanks to @ovs

(n,y=x=0)=>g=k=>(x=x||++y*k--&&n)&&(y*k==--x*(n-x))+g(k)

Try it online!

• Neil: Since y<k and x<n the formula is slightly more readable if you write k*y-y*y and n*x-x*x.
• ovs: I think (n,y=x=0)=>g=k=> ... +g(k) works for 56 bytes: tio.run/…
• Arnauld: @ovs It sure does. Thank you!

Answer 7

Jelly, 8 bytes

×ばつḶċⱮ/S

A monadic Link accepting a pair of integers which yields the count.

Try it online! Or see the test-suite.

How?

×ばつḶċⱮ/S - Link [n,k]
r1 - ([n,k]) inclusive range to 1 = [[n,n-1,...,1],[k,k-1,...,1]]
 Ḷ - lowered range ([n,k]) = [[0,1,...,n-1],[0,1,...,k-1]]
 ×ばつ - multiply = [[n×ばつ0,(n-1)×ばつ(n-1)],[k×ばつ0,(k-1)×ばつ(k-1)]]
 / - reduce by - i.e.: f(A=[n×ばつ0,(n-1)×ばつ(n-1)], B=[k×ばつ0,(k-1)×ばつ(k-1)])
 Ɱ - map with - i.e.: [f(A,v) for v in B]
 ċ - count occurrences (of v in A)
 S - sum

Answer 8

Retina, 45 bytes

\d+
*
L$w`(_+) (_+)
$.`*1ドル=$.2*$'
m`^(.*)=1円$

Try it online! Link includes test suite. Takes space-separated inputs. Explanation:

\d+
*

Convert the inputs to unary.

L$w`(_+) (_+)

Match all substrings that contain _ _. This corresponds to all pairs of \$ 0 \le x < n \$ and \$ 0 \le y < k \$ which are represented by the unmatched parts at the beginning and end of the string $` and $' respectively while \$ n - x \$ and \$ k - y \$ are represented by 1ドル and 2ドル respectively.

$.`*1ドル=$.2*$'

For each pair, list the (unary) products \$ x (n - x) \$ and \$ y (k - y) \$.

m`^(.*)=1円$

Count the number of times that they are equal.

Answer 9

Haskell,(削除) 53 (削除ここまで) 47 bytes

a#b=sum[1|x<-[1..a],y<-[1..b],x*(a-x)==y*(b-y)]

Try it online!

• Saved 6 thanks to @ovs

We use the expression x/(b-y)==y/(a-x) which is converted to x*(a-x)==y*(b-y) to avoid modulo checks.

The expression computes the ratio between sides(the second inverted) which has to be the same to be a valid rectangle.

• ovs: You can use sum instead of foldr1(+): tio.run/##y0gszk7Nyfn/…

Answer 10

Perl 5, (-p -Minteger) 54 bytes

/ /;$_=grep$_%$'*($'-$_%$')==$_/$'*($`-$_/$'),1..$`*$'

Try it online! Using the same formula, and range product as ovs except the range starts from 1

Answer 11

Forth (gforth), 72 bytes

: f 0e over 0 do dup 0 do
2dup i - i * swap j - j * = s>f f- loop loop ;

Try it online!

Yet another port of ovs's Python 2 answer, except that it uses nested loops. Direct loop counters are much cheaper when multiple copies are needed.

Takes n k from the main stack and returns the count via the FP stack.

: f ( n k -- f:cnt )
 0e \ setup the initial count
 over 0 do \ outer loop (j): 0 to n-1
 dup 0 do \ inner loop (i): 0 to k-1
 2dup \ ( n k n k )
 i - i * swap \ ( n k i*[k-i] n )
 j - j * = \ ( n k i*[k-i]==j*[n-j] ) Forth boolean is 0/-1
 s>f f- \ increment count if equal
 loop
 loop
;

Answer 12

Java 8, 75 bytes

n->k->{int r=0,a=n*k;for(;a-->0;)if(a%n*(n-a%n)==a/n*(k-a/n))r++;return r;}

Port of @ovs' Python 2 answer, so make sure to upvote him!

Try it online.