A372917 a(n) is the number of distinct rectangles with area n whose vertices lie on points of a unit square grid.

1, 2, 1, 3, 2, 3, 1, 4, 2, 5, 1, 5, 2, 3, 3, 5, 2, 5, 1, 8, 2, 3, 1, 7, 3, 5, 2, 5, 2, 9, 1, 6, 2, 5, 3, 8, 2, 3, 3, 11, 2, 6, 1, 5, 5, 3, 1, 9, 2, 8, 3, 8, 2, 6, 3, 7, 2, 5, 1, 15, 2, 3, 3, 7, 5, 6, 1, 8, 2, 9, 1, 11, 2, 5, 5, 5, 2, 9, 1, 14, 3, 5, 1, 10, 5, 3

Offset

1,2

Comments

A rectangle in the square unit grid has the sides W = w*sqrt(r) and H = h*sqrt(r). The area is therefore n = w*h*r. Let r be a squarefree divisor of n that can be written as the sum of two squares x^2 + y^2. The number of distinct rectangles is then the sum of the number of ways for each value of r to decompose n/r into two factors w and h (with w >= h).

Links

Felix Huber, Table of n, a(n) for n = 1..10000

Felix Huber, Illustrations of terms a(4), a(8), a(15)

Formula

a(n) = ceiling(Product_{i=1..omega(n)}(k[i]*e[i] + 1)/2), with k[i] = 2 if p[i] mod 4 = 3 and k[i] = 1 else, where p[i]^e[i] is the prime factorization of n.

Example

See also the linked illustrations of the terms a(4) = 3, a(8) = 4, a(15) = 3.
n = 4 has the three divisors 1, 2, 4. Since 4 is not squarefree, r can have the values 1 or 2. For r = 1 = 1^2 + 0^2 there are two rectangles (2,2), (4,1). For r = 2 = 1^2 + 1^2 and n/r = 4/2 = 2 = w*h there is the rectangle (2*sqrt(2), 1*sqrt(2)). That's a total of a(4) = 3 distinct rectangles.
n = 8 has the four divisors 1, 2, 4, 8. Since 4 and 8 are not squarefree, r can have the values 1 or 2. For r = 1 = 1^2 + 0^2 there are two rectangles (4,2), (8,1). For r = 2 = 1^2 + 1^2 and n/r = 8/2 = 4 = w*h there are the rectangles (4*sqrt(2), 1*sqrt(2)) and (2*sqrt(2), 2*sqrt(2)). That's a total of a(8) = 4 distinct rectangles.
n = 15 has the four divisors 1, 3, 5, 15. They are all squarefree, but 3 and 15 cannot be written as a sum of two squares, r can only have the values 1 or 5. For r = 1 = 1^2 + 0^2 there are two rectangles (5,3), (15,1). For r = 5 = 2^2 + 1^2 and n/r = 15/5 = 3 = w*h there is the rectangles (3*sqrt(5), 1*sqrt(5)). That's a total of a(15) = 3 distinct rectangles.

Maple

A372917:= proc(n)
    local f, i, prod;
    f:=ifactors(n)[2];
    prod:=1;
    for i from 1 to numelems(f) do
        if f[i][1] mod 4 = 3 then
            prod:=prod*(1*f[i][2]+1);
        else
            prod:=prod*(2*f[i][2]+1);
        end if;
    end do;
    return round(prod/2);
end proc;
seq(A372917(n), n=1..86);

Prog

(PARI) a(n) = my(f=factor(n)); prod(i=1, #f[, 1], if(f[i, 1]%4==3, 1, 2)*f[i, 2] + 1) \/ 2; \\ Kevin Ryde, Jun 09 2024

Crossrefs

Cf. A001481, A005117, A038548, A085582, A113751, A122225, A285956, A330805, A354704, A372915.

Sequence in context: A307314 A057940 A097285 * A057432 A374741 A361942

Adjacent sequences: A372914 A372915 A372916 * A372918 A372919 A372920

Keyword

nonn

Author

Felix Huber, Jun 08 2024

Status

approved