wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Sum(floor[sqrt(kn)], k=1..n)
        
(Message started by: Eigenray on Aug 29^th, 2006, 7:31pm)

Title: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Aug 29^th, 2006, 7:31pm

Suppose n=a²+b² is square-free (a,b integers). Evaluate

Sum( floor[ sqrt(kn) ], k=1..n ).

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sameer on Aug 29^th, 2006, 9:35pm

What does square-free mean?

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Barukh on Aug 30^th, 2006, 12:41am

on 08/29/06 at 21:35:53, Sameer wrote:

What does square-free mean?

Square-free numbers have no divisors that are perfect squares. In other words, they are products of different primes.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sameer on Aug 30^th, 2006, 10:40am

on 08/30/06 at 00:41:35, Barukh wrote:

Square-free numbers have no divisors that are perfect squares. In other words, they are products of different primes.

Ah in short a^2 + b^2 <> c^2 for any c belongs to Z.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by towr on Aug 30^th, 2006, 12:46pm

on 08/30/06 at 10:40:29, Sameer wrote:

Ah in short a^2 + b^2 <> c^2 for any c belongs to Z.

No, a^2 + b^2 <> k*c^2 for any c belongs to Z.
Many non-squares are still squarefree.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sameer on Aug 30^th, 2006, 6:29pm

Is it [hide]2*(a^2 + b^2) or 2n?[/hide]

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Icarus on Aug 30^th, 2006, 7:13pm

No. Since n >= k, kn >= k², so the sum is >= the sum of all natural numbers up to n, which is n(n+1)/2.

By experiment, here are the values for the first few square-free n:

n -> Sum
2 -> 3
3 -> 6
5 -> 17
6 -> 24
7 -> 32
10 -> 67
11 -> 80
13 -> 113
14 -> 130
15 -> 148
17 -> 193
19 -> 240
21 -> 293

[e] just realized that I forgot to limit my list to only those n that can be expressed as a sum of squares. I leave it to you to sort out which ones Eigenray is asking about...[/e]

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sameer on Aug 31^st, 2006, 9:57am

Yes, once again thanks for pointing out my obvious blunders with a big thud... For starters we can always compares the answer for n=13 (4+9), sum=113
or n=5(4+1), sum=17
or n=2(1+1), sum=3... back to drawing board...

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sameer on Oct 26^th, 2006, 11:55pm

*bump* any hints?

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Oct 27^th, 2006, 11:58am

Think on the other side of the box.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Sjoerd Job Postmus on Oct 27^th, 2006, 4:21pm

May I assume it's similar to [hide]2/3*n^2[/hide]? At least it kind-of looks like it...

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Michael_Dagg on Oct 31^st, 2006, 4:04pm

Nice problem!

Experiment with [hide]the sum sqrt(kn)[/hide].

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Barukh on Nov 2^nd, 2006, 9:09am

The solution to this lovely problem escapes me...

I guess I need another hint... ::)

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Nov 3^rd, 2006, 9:54pm

What is the sum counting?

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Dec 16^th, 2006, 12:59pm

The solution to the given problem involves only elementary number theory; you don't need to know, for example, that n is the product of primes each 1 or 2 mod 4. And you certainly don't need to understand the following: if we replace n by a prime p which is 3 mod 4, then

Sum_k=1^p floor[sqrt(kp)] = (2p²+1)/3 - h,

where h is the class number of the field Q(sqrt(-p)). This is result is much more advanced.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Barukh on Dec 18^th, 2006, 11:25pm

Eigenray, after you supplied so many hints and gave the answer, I still cannot make any progress.

Maybe, this problem is too difficult for me. ::)

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Dec 19^th, 2006, 9:39am

Maybe I should have been more direct: evaluate

Sum_k=1ⁿ floor[ [hide]k²/n[/hide] ]

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Barukh on Dec 21^st, 2006, 10:24am

Step by step...

on 12/19/06 at 09:39:35, Eigenray wrote:

Sum_k=1ⁿ floor[ [hide]k²/n[/hide] ]

I was able to show that under given conditions this sum equals (n²+2)/3.

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Eigenray on Dec 24^th, 2006, 3:41pm

Correct! So what's the answer to the original problem?

Title: Re: Sum(floor[sqrt(kn)], k=1..n)
Post by Barukh on Dec 25^th, 2006, 9:52am

My stupidity really has no limits!

Denote: s_n(k) = floor(k²/n), S_n = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{k = 1 .. n} s_n(k) = (n² + 2)/3 (Eigenray’s auxiliary sum).

Then: http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{k = 1 .. n} floor(sqrt((kn)) = (!) = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{k = 1 .. n-1} k [s_n(k+1)- s_n(k)] + 1 = n² - S_n + 1 = (2n² + 1)/3.

Analyzing the blackout, I now understand that it was caused by my willing to derive directly the relation between the two sums: original and S_n (the former being one less than twice the other).

To be continued...