# Rectangles in rectangles

This 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: ### 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 challenge, so the shortest code wins.

• 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.
– ovs
Oct 17, 2020 at 21:43
• @ovs—thanks for catching this! The table is updated now. Oct 17, 2020 at 22:04
• I took a shot at finding a combinatorial expression, but the best I got is: for $k<n$, the output is $2C-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.
– xnor
Oct 18, 2020 at 5:12

# 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\$$:

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)$$

# 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


# 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!

# Scala, 656460 51 bytes

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


Try it online!

• You can save a byte by currying (n=>k=>)
– user
Oct 18, 2020 at 19:04
• You can use 1.to(n) and 1.to(k) for -2 bytes each.
– ovs
Oct 18, 2020 at 21:22
• Save 9 bytes with Try it online! I just translated the python answer from @ovs. Oct 20, 2020 at 0:42

# 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:

ＮθＮη


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

ＩΣ


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.

# 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!

• Since y<k and x<n the formula is slightly more readable if you write k*y-y*y and n*x-x*x.
– Neil
Oct 17, 2020 at 22:20
• I think (n,y=x=0)=>g=k=> ... +g(k) works for 56 bytes: tio.run/…
– ovs
Oct 18, 2020 at 13:31
• @ovs It sure does. Thank you! Oct 18, 2020 at 13:35

# Jelly, 8 bytes

r1×ḶċⱮ/S


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

Try it online! Or see the test-suite.

### How?

r1×ḶċⱮ/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)×1,...,1×(n-1)],[k×0,(k-1)×1,...,1×(k-1)]]
/  - reduce by - i.e.: f(A=[n×0,(n-1)×1,...,1×(n-1)], B=[k×0,(k-1)×1,...,1×(k-1)])
Ɱ   -   map with - i.e.: [f(A,v) for v in B]
ċ    -     count occurrences (of v in A)
S - sum


# 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.

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.

• You can use sum instead of foldr1(+): tio.run/##y0gszk7Nyfn/…
– ovs
Oct 18, 2020 at 13:29

# 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

# 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
;


# 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.