Problems & Puzzles: Puzzles

Puzzle 1093 Sum[Round[Sqrt[k]],{k,1,n}] Sebastián Martín Ruiz sent the following nice puzzle: Let S(n) to be Sum[Round[Sqrt[k]],{k,1,n}] I have checked that S(n) is prime just for n=2, 7 & 9 for n<100000. S(2)=2, S(7)=13 and S(9)=19. Q. Are there more n values such that S(n)  is prime?

---

During the week from 2 to 10 of July, contributions came from Giorgio Kalogeropoulos, Adam Stinchcombe Gennady Gusev, Simon Cavegn, Oscar Volpattu and Emmanuel Vantieghem

***

Giorgio wrote:

We are searching for primality of the partial sums of A000194

1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5...

 where n appears 2n times.
 

So, S(n) is A165453 

OEIS gives us a formula for S(n) as a product: 

S(n) = (1/3) * t(n) * (3*n + 1 - t(n)^2), where t(n) = floor( sqrt(n) + 1/2 )

t(n) is A000194 that was mentioned above and t(n) > 3 for n > 12

Also, (3*n + 1 - t(n)^2) is

3, 6, 6, 9, 12, 15, 13, 16, 19, 22, 25, 28, 24, 27, 30, 33, 36, 39, 42, 45, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 58, 61, 64, 67, 70, 73...

So, (3*n + 1 - t(n)^2) is always >3 for n>2.

This is because t(n)^2 is bounded: n - sqrt(n)< t(n)^2 < n + sqrt(n) and 

2n + 1 - sqrt(n) <  3*n + 1 - t(n)^2 < 2n +1 + sqrt(n)

In conclusion, S(n) = (1/3) * t(n) * (3*n + 1 - t(n)^2) cannot be prime for any n>12 because both  t(n) and  (3*n + 1 - t(n)^2) are greater than 3 and at least one of them is divisible by 3.

So, S(n) has at least 2 prime factors for n>12.

 

***

Adam wrote:

S(n) is never prime again.
 

For    n-1/2 =<sqrt(x)<n+1/2    round(sqrt(x)) = n and is constant on that interval.  Squaring both sides and rounding,  n^2-n+1=<x<=n^2+n   has round(sqrt(x))=n and there are 2n such numbers.  So sum[x=n^2-n+1..x=n^2+n] { round(sqrt(x)) } = 2n*n.  Let g be a integer bigger then 2.  Then sum[x=1..x=g^2+g] { round(sqrt(x)) }  =  sum(n=1..n=g) { 2n^2 } = g(2g+1)(g+1)/3.  What happens to sum after x=g^2+g?  For x from g^2+g+1 through (g+1)^2+(g+1), round(sqrt(x)) = g+1 and you are adding the constant (g+1) to g(2g+1)(g+1)/3.  These two summands share a factor of either g+1 or (g+1)/3  (which is >1 for g>2) if the factor of 3 in g(2g+1)(g+1)/3 cancels into the factor of g+1.

 

How can it be prime ever (which it is)?   For g=1, g(2g+1)/3=1 and you get the prime 2.  For g=2, you get the sum up to x=6 which is 10 and then you are adding g+1=3 to 10 from x=7 to x=12 yielding the sequence 10,13,16,19,22,25,28 and the primes 13 and 19.  Thereafter, the new round(sqrt(x)) term shares a factor with the previous sum, yielding a composite number.

***

Gennady wrote:

Let's solve the inverse problem: find an interval for k in which round(sqrt(k)) = m.

This is true when m-0.5 <= sqrt(k)<m+0.5 ,

m^2-m+0.25<=k<m^2+m+0.25

m^2-m < k <= m^2+m.

That is, for k there are exactly 2m values giving the result m. Their sum is equal to 2m^2. The maximum k giving round(sqrt(k))=m is equal to m^2+m=m*(m+1).

Hence s’ = sum(round(sqrt(k))) {k=1..m*(m+1)} = sum(2i^2) (i=1..m) = 2sum(i^2)= 2*m*(m+1)*(2m+1)/6 = m*(m+1)*(2m+1)/3.

Thus, ALL sums s’ for round(sqrt(k))=m are obtained by subtracting from s’ the value m*l, where l=0..2m-1.

So, s = sum(round(sqrt(k)) = m*(m+1)*(2m+1)/3 - m*l, where l=0..2m-1, (k=1..m*(m+1)

If m=1, we have s=2 – prime (l=0).

If m=3j. For j=1, we have s = 13 and 19 primes (for l = 5 and 3).

When j>1, s is divisible by j, since both parts of s are divisible by j.

If m is # 3j, then (m+1)*(2m+1)  is divisible by 3 , and therefore s is divisible by m.

So, the sum s is always a composite number, except for the specified cases (2, 13, 19).

 

***

Simon wrote:

Found no more prime values for S(n). Searched up to n=1948907134863
 

***

Oscar wrote:

Puzzle 1093 has a negative answer: S(n) is composite for all values n > 9.

Function S(n) is piecewise linear.
First interval [0,2], with slope 1:
S(n) = 0 + 1*(n-0)
Second interval [2,6], with slope 2:
S(n) = 2 + 2*(n-2)
Third interval [6,12], with slope 3:
S(n) = 10 + 3*(n-6)
...
k-th interval [a_k,b_k], with slope k:
S(n) = c_k + k*(n-a_k)
with:
a_k = k*(k-1)
b_k = k*(k+1)
c_k = k*(k-1)*(2*k-1)/3 = S(a_k)

For values n belonging to the first three intervals, the only prime solution are S(2)=2, S(7)=13, and S(9)=19.
For values n belonging to k-th interval, with k>3, S(n) has a proper factor d_k = gcd(k,c_k), with:
d_k = k > 3  if k is coprime with 3,
d_k = k/3 > 1  if k is a multiple of 3.
***

Emmanuel wrote:

There are no more primes.
Consider the following set of numbers :
V={m^2 + 1, m^2 + 2, ..., m^2 + m, m^2 + m + 1, m^2 + m + 2, ..., m^2 + 2m, m^2 + 2m + 1}.
Taking the square root and then taking the function round of these numbers gives the following results :
     {m, m, ..., m, m+1, m+1, ..., m+1, m+1}.
Summing these numbers gives :
     m^2 + (m+1)^2 = 2*m^2 + 2*m + 1= G(m).
Thus, to compute  S((m+1)^2), we compute  G(0) + G(1) + ... + G(m).
Classical summation formulas learn us :
S((m+1)^2) = 1 + 2*Sum(k^2, {k,1,m}) +2*Sum(k, {k,1,m}) + Sum(1, {k,1,m})
     = 1 + 2*m(m+1)(2m+1)/6 + 2*m(m+1)/2 + m
     = (2*m^3 + 6*m^2 + 7*m + 3)/3 = (m + 1)(2*m^2 + 4*m +3)/3.
Now, take an arbitrary number  n > 2.
Then there always exists one and only one set like  V  that contains  n.
In other words, n  is always of the form  m^2 + w.
There are two possibilities : 1 <= w <= m  or  m+1 <= w <= 2m+1.
In the first case, S(n) will be equal to  S(m^2) + a*m = (2*m^3 + m)/3 + a*m  with  1 <= a <= m
and this is always divisible by m  (or by  m/3 when m is divisible by 3).
In the second case, S(n)  will be of the form  S(m^2) + m^2 + b*(m+1)  with  1 <= b <= m.
I. e. : S(n) = m(m+1)(2m+1)/3 + b*(m+1), also always divisible by  m + 1 (or by (m+1)/3 when m+1 is divisible by 3).
Thus, primes can only be reached for small values of  n

***