# Prime factorizations that yield hyperrectangles with integer diagonals

I have been looking into $n$-dimensional rectangles (aka hyperrectangles) with measures given by any orderless prime-factorization of a natural number, where the diagonal is of an integer length.

Let's denote these as perfect rectangles.

Obviously, every prime number yields a perfect ($1$-dimensional) rectangle.

As a more generalized definition - any number whose prime-factorization is given by $\overbrace{{p}\times\dots\times{p}}^\text{N times}$ with $N$ being a square yields a perfect $N$-dimensional rectangle. For example:

$81$ yields a perfect $4$-dimensional rectangle with diagonal length $\sqrt{3^2+3^2+3^2+3^2}=6$.

However, there are other types of numbers that yield perfect rectangles. For example:

$48$ yields a perfect $5$-dimensional rectangle with diagonal length $\sqrt{2^2+2^2+2^2+2^2+3^2}=5$.

I have been searching for sequences of consecutive numbers that yield perfect rectangles.

For example, $16$ and $17$ yield perfect rectangles with diagonal lengths $4$ and $17$ respectively.

$2729-2730-2731$ yield perfect rectangles with diagonal lengths $2729-16-2731$ respectively.

Searching up to $16$ million, I have not been able to find any sequence longer than $3$ numbers.

In addition, I have noticed that in every sequence of $3$ numbers, one or two of them are prime.

So my question is - has either one of these two statements been conjectured, proved or refuted?

C-code is given below (should anyone wishes to extend the tested range):

#include <math.h>
#include <stdio.h>

#define RANGE 16000000
#define SEQUENCE_LEN 4

typedef unsigned char      uint08;
typedef unsigned int       uint32;
typedef unsigned long long uint64;

uint08 sieve[RANGE] = {0};
uint32 prime[RANGE] = {0};
uint32 numOfPrimes  =  0 ;

void CalcAuxiliaryData()
{
uint32 i,j;

uint32 root = (uint32)sqrt((double)RANGE);

for (i=2; i<=root; i++)
{
if (sieve[i] == 0)
for (j=i+i; j<RANGE; j+=i)
sieve[j] = 1;
}

for (i=2; i<RANGE; i++)
{
if (sieve[i] == 0)
prime[numOfPrimes++] = i;
}
}

uint32 CalcDiagonalLen(uint32 n)
{
uint32 i;

uint64 square;
uint32 length;

if (sieve[n] == 0)
return n;

square = 0;
for (i=0; i<numOfPrimes && n>1; i++)
{
uint32 p = prime[i];
uint64 pp = (uint64)p*p;
while (n%p == 0)
{
n /= p;
square += pp;
}
}

length = (uint32)sqrt((double)square);
if ((uint64)length*length == square)
return length;

return 0;
}

int main()
{
uint32 i;

uint32 sequence_len;
uint32 diagonal_len;

CalcAuxiliaryData();

sequence_len = 0;
for (i=2; i<RANGE; i++)
{
diagonal_len = CalcDiagonalLen(i);
if (diagonal_len == 0)
{
sequence_len = 0;
}
else
{
printf("%u %u\n",i,diagonal_len);
if (++sequence_len == SEQUENCE_LEN)
break;
}
}

return 0;
}


UPDATE:

Using this implementation advice, I have verified both statements up to $1.2$ billion.

UPDATE #$2$:

Checking up to $2$ billion, I have counted $1585$ triplets:

• The trivial triplet $1-2-3$
• $2$ triplets of the form $C-C-P$
• $4$ triplets of the form $P-C-C$
• $7$ triplets of the form $C-P-C$
• $1571$ triplets of the form $P-C-P$

I have also encountered the following quadruplet, which refutes the first conjecture:

• $A_{1776463301}=\sqrt{1776463301^2}=1776463301$
• $A_{1776463302}=\sqrt{2^2+3^2+173^2+857^2+1997^2}=2180$
• $A_{1776463303}=\sqrt{1776463303^2}=1776463303$
• $A_{1776463304}=\sqrt{2^2+2^2+2^2+7^2+11^2+179^2+16111^2}=16112$

UPDATE #$3$:

Up to $4$ billion, I have counted $28$ pairs of consecutive non-primes which yield perfect rectangles, but I have not encountered a single triplet of consecutive non-primes which yield perfect rectangles.

• Nice problem! I currently search with PARI/GP – Peter Jan 4 '15 at 21:07
• Maybe, you are the first one looking for such numbers. I have read a lot about prime factorization, but came never across your "diagonal length". – Peter Jan 4 '15 at 21:43
• I extended to $180\ 000\ 000$ and still could not refute your conjectures. – Peter Jan 4 '15 at 22:03
• @Peter: Thank you very much, I appreciate the effort :) – barak manos Jan 4 '15 at 22:03
• This feels like it must be related to the ABC conjecture, since your numbers are likely to be highly powerful (and could probably be proven so) and the ABC conjecture places limits on how close such powerful numbers can be. – Steven Stadnicki Jan 4 '15 at 22:13

I would conjecture quite the opposite: for any $k$ there should be infinitely many integers $n$ such that $n,n+1,n+k-2$ all yield perfect rectangles. Indeed, these examples can avoid primes altogether.

Given a large number $x$, let's consider all primes less than $x^{1/k}$; there are approximately $k x^{1/k}/\log x$ such primes by the prime number theorem. Now let's consider all numbers that are the product of exactly $k$ distinct primes less than $x^{1/k}$; there are approximately $\frac1{k!} ( k x^{1/k}/\log x) ^k \approx C_1(k) x/(\log x)^k$ such numbers, and any such number is less than $x$. (The leading constant, depending on $k$, won't matter much.)

For any number of this form, the sum of the squares of the prime factors is at most $kx^{2/k}$. Assuming the heuristic that these sums of squares are distributed randomly, the "probability" that the sum of the squares of the prime factors is a perfect square is at least $\frac1{\sqrt k} x^{-1/k}$. Therefore, there should be about $C_2(k) x^{1-1/k}/(\log x)^k$ numbers, consisting of $k$ small primes multiplied together, that yield perfect rectangles. In other words, the probability that a randomly chosen number from $[1,x]$ has this property is about $C_2(k) x^{-1/k}/(\log x)^k$.

If we further assume the heuristic that these numbers are randomly distributed in the interval $[1,x]$, then the probability of any given $n,n+1,\dots,n+k-2$ consisting entierly of integers of this form is about $C_3(k) x^{-(k-1)/k}/(\log x)^{k(k-1)}$. Summing this probability over $1\le n\le x$, we discover that the expected number of sets of $2k-1$ consecutive numbers with this property is about $C_4(k) x^{1/k}/(\log x)^{k(k-1)}$, which in particular goes to infinity with $x$.

(Some slight modifications of this argument need to be made: for example, every 2nd number in the sequence must be a multiple of 2, every 3rd must be a multiple of 3, and so on for all primes less than $k$. I believe one can incorporate this modification with no substantive change to the overall heuristic.)

• There's also the annoying fact that $p^2\equiv1\pmod{24}$ for every prime $p>3$. So it's probably best to consider numbers with $k,k+1,\dots,2k$ prime factors or something like that, to make sure there isn't a local obstruction to the integers being consecutive. – Greg Martin Jan 4 '15 at 23:44
• So for example, look for primes $p_1,p_2,p_3,p_4$ and $p_1',p_2',p_3',p_4'$ near $x^{1/4}$, primes $q_1,\dots,q_5$ near $x^{1/5}$, and primes $r_1,\dots,r_6$ near $x^{1/6}$ such that the four integers $p_1p_2p_3p_4$, $2q_1q_2q_3q_4q_5$, $27r_1r_2r_3r_4r_5r_6$, and $4p_1'p_2'p_3'p_4'$ are consecutive and each of $p_1^2+p_2^2+p_3^2+p_4^2$, $4+q_1^2+\cdots+q_5^2$, $27+r_1^2+\cdots+r_6^2$, and $8+p_1'^2+p_2'^2+p_3'^2+p_4'^2$ are perfect squares. – Greg Martin Jan 5 '15 at 0:17
• Thank you. I will try to find a way to extend the range beyond the $180$M already tested by @Peter. – barak manos Jan 5 '15 at 7:04
• I more or less understand the probabilistic argument. Just FYI, I have tested up to 1G and did not encounter any sequence longer than $3$ numbers. – barak manos Jan 5 '15 at 20:37