Sums of floors of square roots

Number Theory Level 3

Find the largest possible $n$ such that $\big\lfloor \sqrt{1} \big\rfloor + \big\lfloor \sqrt{2} \big\rfloor + \big\lfloor \sqrt{3} \big\rfloor + \cdots + \big\lfloor \sqrt{n} \big\rfloor$ is a prime number.

Clarification: $\lfloor x \rfloor$ returns the largest integer less than or equal to $x$ .

The answer is 47.

3 solutions

Patrick Corn
Oct 17, 2017

Call the sum $S_n.$ Now first note that $S_{m^2-1}$ is easy to compute: for each $d$ between $1$ and $m-1,$ there are $2d+1$ consecutive $d$ terms. So we get $\sum_{d=1}^{m-1} d(2d+1) = \frac{m(m-1)(4m+1)}6.$

Let $a = \lfloor \sqrt{n} \rfloor.$ Then $S_n = S_{a^2-1} + a(n-a^2+1).$ We will use this to show that $S_n$ is composite based on the value of $a.$

If $p|a, p \text{ prime, }p \ge 5$ : Then $S_{a^2-1}$ is divisible by $p,$ from the formula above, and so $S_n$ is as well. So it must be composite, since $S_{a^2-1}$ is clearly larger than $a$ for $a \ge 2,$ but it has a nontrivial prime divisor $\le a.$

If $4|a$ : Same thing; $S_{a^2-1}$ is even, by the above formula, and so $S_n$ is as well.

If $9|a$ : Same thing; $S_{a^2-1}$ is divisible by $3,$ by the above formula, and so $S_n$ is as well.

This restricts us to the cases $a = 1,2,3,6.$ And in fact, when $a=6$ there are several examples where $S_n$ is prime. The largest of these is $n=47, S_n = 197$ (the only possible larger one is $n=48, S_n = 203,$ which is in fact composite). So this is the maximum possible value of $n.$

from math import sqrt, floor, ceil

def isprime(startnumber):
    startnumber*=1.0
    for divisor in range(2,int(startnumber**0.5)+1):
        if startnumber/divisor==int(startnumber/divisor):
            return False
    return True

sum_ = 0
z = []
for i in range(1,10000):
    sum_ += int(floor(sqrt(i)))
    if isprime(sum_):
        z.append(i)

print max(z)

sum_ = 0
z = []
for i in range(1,10000):
    sum_ += int(ceil(sqrt(i)))
    if isprime(sum_):
        z.append(i)

print max(z)

Ans: 47 (floor) Ans: 34 (ceiling)

Michael Fitzgerald - 3 years, 7 months ago

Is the first sum formula widely known?

I might have approached it a slightly different way but it essentially boils down to the same thing. Interestingly it also yields 1+2^2+3^2+....+(p-1)^2 divides p for all primes.

Set q=(p-1)/2, then

1^2+2^2+...+q^2 = q (q+1) (2*q+1)/6

= q*(q+1)/6 * p

Which is a multiple of p for all primes greater than 3.

Yours is a much tidier solution but made a few leaps that weren't obvious, at least to me.

Malcolm Rich - 3 years, 7 months ago

Nah, I just skipped some steps. It's $2\sum_{d=1}^{m-1} d^2 + \sum_{d=1}^{m-1} d = 2 \frac{m(m-1)(2m-1)}6 + \frac{m(m-1)}2,$ which simplifies to what I had above.

Patrick Corn - 3 years, 7 months ago

I think you have a very clean solution really.

Malcolm Rich - 3 years, 7 months ago

"We will use this to show that S_n is composite based on the value of a." ... "So it can't be composite..." Don't you mean "So it must be composite..."?

Richard Desper - 3 years, 7 months ago

Yep, thanks, fixed.

Patrick Corn - 3 years, 7 months ago

Arjen Vreugdenhil
Oct 31, 2017

Let $p$ be the greatest integer whose square is less than or equal to $n$ ; that is, $n = p^2 + k,\ \ \ \ 0 \leq k \leq 2p.$ The corresponding sum is $S(n) = \sum_{i=1}^n \lfloor i \rfloor = \sum_{q=1}^{p-1} q(2q+1) + p(k+1);$ using the facts that $\sum_{i=1}^m i = \tfrac12 m(m+1)$ and $\sum_{i=1}^m i^2 = \tfrac16 m(m+1)(2m+1)$ , $S(n) = \frac26(p-1)p(2p-1) + \frac12(p-1)p + p(k+1) = p\left(k + 1 + (p-1)\cdot \frac{4p+1}6\right).$ If this is to be prime, $p$ must be a factor of the denominator 6; our best hope is $p = 6$ . In that case, $S(n) = S(36 + k) = 6\left(k + 1 + 5\cdot{25}6\right) = 131 + 6k.$ Checking the possible values $k = 12, 11, \dots, 0$ , we first reject $S(36 + 12) = 203 = 7\cdot 29$ ; but we approve $S(36 + 11) = 197$ , which is prime.

Thus the answer, with $p = 6$ and $k = 11$ , is $6^2 + 11 = \boxed{47}$ , corresponding to the sum $S(47) = 197$ .

Nice solution. Your solution makes much clear where I got wrong as I got it correct in second attempt. :)

Naren Bhandari - 3 years, 7 months ago

Alperen Aydin
Nov 1, 2017

I am ashamed of saying this but I did this using a script. I calculated the values of the sequence for the n in 1:1000 and checked for which one's were prime. I noticed that 47 seemed to be biggest one I tried that one and lo and behold.

from math import sqrt, floor

def isprime(startnumber):
    startnumber*=1.0
    for divisor in range(2,int(startnumber**0.5)+1):
        if startnumber/divisor==int(startnumber/divisor):
            return False
    return True

sum_ = 0
z = []
for i in range(1,10000):
    sum_ += int(floor(sqrt(i)))
    if isprime(sum_):
        z.append(i)
print max(z)

Ans: 47

Michael Fitzgerald - 3 years, 7 months ago

It seems similar. I did mine on R since I had that open.

Alperen AYDIN - 3 years, 7 months ago

You mean this script

Michael Fitzgerald - 3 years, 7 months ago

I “cheated” differently - used Excel. I realize that’s not a valid proof.

Ed Rozmiarek - 3 years, 7 months ago

There is no shame in using code... but is it satisfactory? How do you know that there is no six-digit number $n$ for which the sum is suddenly a prime number again?

Arjen Vreugdenhil - 3 years, 7 months ago

It is not satisfactory. My plan was that I would just calculate a certain amount to get a sense of the question, maybe a pattern would reveal itself.

Anyways, I noticed that 47 seemed to be biggest. I was thinking of maybe a demonstration by the absurd. Someone called me so I had to leave so I decided to at least see if 47 was the answer since we have 3 chances.

Alperen AYDIN - 3 years, 7 months ago

Mathematica : Select[Range@1000,PrimeQ@Tr@Floor[Sqrt@Range@#]&]

Χωρις Ονομας - 3 years, 5 months ago

Sums of floors of square roots

The answer is 47.

3 solutions

0 pending reports