Author |
Topic: Sum(floor[sqrt(kn)], k=1..n) (Read 4588 times) |
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 1948
|
 |
Sum(floor[sqrt(kn)], k=1..n)
« on: Aug 29th, 2006, 7:31pm » |
 Quote  Modify
|
Suppose n=a2+b2 is square-free (a,b integers). Evaluate
Sum( floor[ sqrt(kn) ], k=1..n ).
|
|
 IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #1 on: Aug 29th, 2006, 9:35pm » |
Quote Modify
|
What does square-free mean?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #2 on: Aug 30th, 2006, 12:41am » |
Quote Modify
|
on Aug 29th, 2006, 9:35pm, 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.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #3 on: Aug 30th, 2006, 10:40am » |
Quote Modify
|
on Aug 30th, 2006, 12:41am, 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.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #4 on: Aug 30th, 2006, 12:46pm » |
Quote Modify
|
on Aug 30th, 2006, 10:40am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #5 on: Aug 30th, 2006, 6:29pm » |
Quote Modify
|
Is it 2*(a^2 + b^2) or 2n?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #6 on: Aug 30th, 2006, 7:13pm » |
Quote Modify
|
No. Since n >= k, kn >= k2, 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]
|
| « Last Edit: Aug 30th, 2006, 7:18pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #7 on: Aug 31st, 2006, 9:57am » |
Quote Modify
|
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...
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #8 on: Oct 26th, 2006, 11:55pm » |
Quote Modify
|
*bump* any hints?
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #9 on: Oct 27th, 2006, 11:58am » |
Quote Modify
|
Think on the other side of the box.
|
|
IP Logged |
|
|
|
Sjoerd Job Postmus
Full Member
Posts: 228
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #10 on: Oct 27th, 2006, 4:21pm » |
Quote Modify
|
May I assume it's similar to 2/3*n^2? At least it kind-of looks like it...
|
|
IP Logged |
|
|
|
Michael Dagg
Senior Riddler
Gender:
Posts: 500
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #11 on: Oct 31st, 2006, 4:04pm » |
Quote Modify
|
Nice problem!
Experiment with the sum sqrt(kn).
|
|
IP Logged |
Regards,
Michael Dagg
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #12 on: Nov 2nd, 2006, 9:09am » |
Quote Modify
|
The solution to this lovely problem escapes me...
I guess I need another hint... 
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #13 on: Nov 3rd, 2006, 9:54pm » |
Quote Modify
|
What is the sum counting?
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #14 on: Dec 16th, 2006, 12:59pm » |
Quote Modify
|
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
Sumk=1p floor[sqrt(kp)] = (2p2+1)/3 - h,
where h is the class number of the field Q(sqrt(-p)). This is result is much more advanced.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #15 on: Dec 18th, 2006, 11:25pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #16 on: Dec 19th, 2006, 9:39am » |
Quote Modify
|
Maybe I should have been more direct: evaluate
Sumk=1n floor[ k2/n ]
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #17 on: Dec 21st, 2006, 10:24am » |
Quote Modify
|
Step by step...
on Dec 19th, 2006, 9:39am, Eigenray wrote:
I was able to show that under given conditions this sum equals (n2+2)/3.
|
| « Last Edit: Dec 21st, 2006, 10:27am by Barukh » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #18 on: Dec 24th, 2006, 3:41pm » |
Quote Modify
|
Correct! So what's the answer to the original problem?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Sum(floor[sqrt(kn)], k=1..n)
« Reply #19 on: Dec 25th, 2006, 9:52am » |
Quote Modify
|
My stupidity really has no limits!
Denote: sn(k) = floor(k2/n), Sn =  k = 1 .. n sn(k) = (n2 + 2)/3 (Eigenray’s auxiliary sum).
Then: k = 1 .. n floor(sqrt((kn)) = (!) = k = 1 .. n-1 k [sn(k+1)- sn(k)] + 1 = n2 - Sn + 1 = (2n2 + 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 Sn (the former being one less than twice the other).
To be continued...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print