Semi-Squares

Number Theory Level 4

I define a "semi-square $n$ " as a positive integer—which is not a square number—such that there exists a prime $p$ satisfying $\frac{n}{p}=x^2$ for some integer $x.$

How many semi-squares are there between $1$ and $1000$ inclusive?

The answer is 337.

3 solutions

Jordan Cahn
Jan 21, 2019

We are looking for integers of the form $n=m^2p$ , where $p$ is prime. If $n\leq 1000$ then $m^2\leq\frac{1000}{p}$ and $m\leq \sqrt{\frac{1000}{p}}$ . Thus we compute $\sum_{i=1}^{\pi(1000)}\left\lfloor\sqrt{\frac{1000}{p_i}}\right\rfloor=\sum_{i=1}^{168}\left\lfloor\sqrt{\frac{1000}{p_i}}\right\rfloor$ where $\pi(1000)=168$ is the prime-counting function (i.e. the number of primes less than $1000$ ) and $p_i$ denotes the $i$ th prime number.

Evaluating the function computationally yields $337$ . I welcome any insight into a simple way to evaluate the sum that can be done by hand.

thanks for the solution. This is a nice first idea

A Former Brilliant Member - 2 years, 4 months ago

I did something similar, but I ran through the squares instead of the primes, so my formula would have been $\displaystyle\sum_{n=1}^{\lfloor \sqrt{500} \rfloor} \pi\left(\left\lfloor \frac{1000}{n^2} \right\rfloor\right)$

I like yours better, just because of how many times I had to call pi(n) in wolfram alpha while adding mine.

Jason Carrier - 2 years, 4 months ago

Just an observation...if we define $s(n)$ to be the number of semi-squares less than or equal to $n$ , we have

$s(1000) = 2\pi(1000)+1$

This caught my eye, and as I had used a programme to find the answer, it was easy to check that

$s(10000) = 2\pi(10000)+1$ as well. Remarkably, it turns out this is a coincidence, and not in fact generally true; but it does seem to be true that $s(n)$ is very close to $2\pi(n)$ . I'm sure there's an excellent reason for this, but it eludes me at the moment - does anyone have any ideas why this might be?

Chris Lewis - 2 years, 4 months ago

Interesting! For $p>\frac{n}{2}$ , there is precisely one semi-square less than $n$ with $p$ as a factor... $p$ itself. The bulk of the semi-squares come from small primes.

Jordan Cahn - 2 years, 4 months ago

X X
Feb 7, 2019

OEIS A229125

Peter Macgregor
Jan 28, 2019

In mathematica the one liner

Total[Table[PrimePi[1000/n^2],{n,1,31}]]

does the trick!

The idea is to take each of the squares and multiply them by prime numbers to produce semi-squares. Each entry in the table counts the number of semi-squares less than 1000 coming from each square.

Semi-Squares

The answer is 337.

3 solutions

0 pending reports