Author |
Topic: Interesting Number (Read 1673 times) |
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
 |
Interesting Number
« on: Apr 15th, 2004, 4:39pm » |
 Quote  Modify
|
Ok This one has been bothering me for a while:
Consider a number x=n*frac(n*sqrt(2)) where sqrt() stands for square root and frac() for fractional part. n is any positive integer. What is the largest real number smaller than any x ? For what values of n?
|
|
 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
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
 
Gender:
Posts: 767
|
|
Re: Interesting Number
« Reply #1 on: Apr 15th, 2004, 9:10pm » |
Quote Modify
|
irrational fractions... I ate a bee and now my mouth tastes like burning!
Is x [smiley=bbr.gif] or [smiley=bbz.gif]?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
evergreena3
Full Member
Gender:
Posts: 192
|
|
Re: Interesting Number
« Reply #2 on: Apr 15th, 2004, 9:18pm » |
Quote Modify
|
John,
I thought it was the poisonous berrys that tasted like burning. Darn, that is the last time I trust a monkey-butler to do anything!
EverGreenA3
|
|
IP Logged |
You're welcome! (get it?)
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Number
« Reply #3 on: Apr 16th, 2004, 12:52am » |
Quote Modify
|
hmmm.. Maybe we could do something with the continued fraction?
Of course since every x is a real number, there can't really be said to be a largest real number smaller than any x. (just like there isn't a largest number smaller than 1, which would be 0.999...  )
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Interesting Number
« Reply #4 on: Apr 16th, 2004, 4:12am » |
Quote Modify
|
on Apr 16th, 2004, 12:52am, towr wrote:| Of course since every x is a real number, there can't really be said to be a largest real number smaller than any x. |
|
I think in this case this may be said. I would say the answer is [smiley=square.gif]0[smiley=square.gif], although I didn't prove it yet. The approach is to use the fact that the sequence {frac(n*sqrt(2)} is uniformly distributed in (0,1).
|
|
IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Interesting Number
« Reply #5 on: Apr 16th, 2004, 5:55am » |
Quote Modify
|
When I first read it, the problem bugged me because you can get arbitrarily close to a real number x. As Barukh hinted at, you can make just about any number because the stuff in parens is uniformly distributed on (0,1), which effectively scales the result to (0,n). So we have a number x on the interval (0,n), and we are trying to find the next smaller [smiley=bbr.gif] than x. Like towr said, this is not possible.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Interesting Number
« Reply #6 on: Apr 16th, 2004, 6:00am » |
Quote Modify
|
I wonder if this problem reduces to maximizing frac(n*sqrt(2)) so it is arbitrarily close to 1... I think zero might be a good choice too, but that is too obvious 
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
asterix
Guest
|
I tried running a simple program to check it out. For some reason, the only times x<1, it always hits close to either .35 or .70. As n gets larger, I believe those two numbers are converging on some limits, but I'm not sure what they are or why. Here are the answers that hit .35
n; x
5; .355339
29; .3536059
169; .3535549
985; .3535534
5741; .35355339
33461; .353553390566
195025; .353553388
1136689; .35355332
6625109; .3535523280188499
Each time n increases by a multiple of 5.828427. Figure out what that number has to do with the square root of 2, and you'll find the answer.
|
|
IP Logged |
|
|
|
asterix
Guest
|
I'm sorry, I was reading the problem wrong. I was looking for the maximum number smaller than the smallest x. I'll try again.
|
|
IP Logged |
|
|
|
asterix
Guest
|
No, I think I was right after all. The next n comes at 38613965 and x is .3534395944.
Then n= 225058681; x=.3537. So for the first time x increases. Then n goes beyond the capabilities of my program.
|
|
IP Logged |
|
|
|
asterix
Guest
|
And of course I know where the 5.828 comes from. It's the inverse of the fractional portion of the square root of two, squared.
|
|
IP Logged |
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Interesting Number
« Reply #11 on: Apr 16th, 2004, 9:42am » |
Quote Modify
|
Hmm I actually agree that you cannot find a number greater or smaller than a real number. So let's re word it to say a bound for x (on the lower side, and probably in terms of sqrt(2))
asterix is on the right track... Barukh you are right about that frac thing, I think it is Weyl's distribution or something.
|
|
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: Interesting Number
« Reply #12 on: Apr 16th, 2004, 3:46pm » |
Quote Modify
|
The wording "Largest real number smaller than every x" would be alright. The only problem in the original is the need to interpret "any" to mean "every". To be more exact, we are looking for the greatest lower bound of the set
{ n(n[surd]2 - [lfloor]n[surd]2[rfloor]) | n [in] [bbn] }
|
|
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
|
|
|
asterix
Guest
|
I think I can tell you where the .353553 comes from.
It's 1/(2*sqrt(2)). But if that's supposed to be the lower bound, than a couple of the answers come in just a hair lower than they're supposed to. And I still don't know why that bound exists.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Number
« Reply #14 on: Apr 17th, 2004, 6:33am » |
Quote Modify
|
I assume you calculate those numbers by computer or calculator, so beware of rounding error..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Interesting Number
« Reply #15 on: Apr 17th, 2004, 8:38am » |
Quote Modify
|
That's what happens when one is too fast and tries to guess without a proof - my conjecture is wrong 
Asterix, you are right - the lower bouhd is 1/sqrt( 8 ), and it's exact (really nice job, indeed!)
towr, you are right - the solution has something to do with continued fractions.
I believe I've got a proof for this problem and some generalizations - will try to summarize in a separate post. Also, I will write about computational aspect of the problem.
A wonderful puzzle, Sameer! 
|
| « Last Edit: Apr 18th, 2004, 9:39am by Barukh » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Interesting Number
« Reply #16 on: Apr 17th, 2004, 9:20am » |
Quote Modify
|
Is 8-.5 the actual greatest lower bound, or is it the lowest accumulation point?
|
|
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
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Interesting Number
« Reply #17 on: Apr 17th, 2004, 10:48am » |
Quote Modify
|
I've not found a connection yet, but the continued fraction for 1/sqrt(8)=[0;2,1,(4)].
So the sequence of convergents would be:
1/2, 1/3, 5/14, 21/59, 89/250, 377/1059, ...
After the 2nd convergent all further terms are given by, pn/qn = (4pn-1+pn-2)/(4qn-1+qn-2).
Trying to link this with the sequence that Asterix found I noticed that his list of optimal values of n: 5, 29, 169, 985, 5741, ..., is given by the second order recurrence relation, un=6un-1–un-2.
For example, the next term, u6=6*5741–985=33461.
Not sure how to connect these yet?!
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Interesting Number
« Reply #18 on: Apr 18th, 2004, 9:29am » |
Quote Modify
|
Here's the solution I came with.
[smiley=blacksquare.gif]
Instead of the function f(n) given in the problem, let's look at another one: F(n) = f(n)[sqrt]2 = n[sqrt]2*{n[sqrt]2} ({x} means fractional part).
For every n, find a smallest positive integer r, such that
2n2 – r = m2, a perfect square (*).
Then, we have F(n) = [sqrt]( m2 + r){ [sqrt](m2 + r) } = m2 + r – m[sqrt](m2 + r) (why?).
I then needed the following two statements to proceed (I left them invisible if somebody wants to try them as exercises):
1. For any n and corresponding r, F(n) > r/2.
[smiley=square.gif]
It is clear that m2 + r < (m + r/2m)2, so F(n) > m2 + r – m(m + r/2m) = r/2.
[smiley=square.gif]
2. If for a fixed r, there are infinitely many n's, than F(n) maybe made as close to r/2 as we please.
[smiley=square.gif]
Because of the way r is chosen, we have r <= 2m. Also, if there are infinitely many n's, there must be infinitely many m's, as large as we please, and the claim follows from: F(n) < (m+r/2m){ m + r/2m } = (m+r/2m)r/2m = r/2 + (r/2m)2.
[smiley=square.gif]
Now, it becomes clear that to find the greatest lower bound for F(n), we need to find the smallest possible r, and hope it will give infinitely many values of n. If we look closer at equation (*), we recognize in it the general Pell equation for d=2, which was discussed in x^2 - 61y^2 = 1 thread. It is known, that infinite sequences for certain r are to be found among the convergents of continued fraction (CF) of [sqrt]2 – as towr conjectured. In this case, the smallest r=1 is possible, because the CF for [sqrt]2 has an odd period. The numbers 5, 29, 169, 985, 5741 etc. found by asterix, are just the denominators of the 3rd, 5th, 7th, 9th etc. convergents for [sqrt]2 – the first ones corresponding to r=1, and there are infinitely many of them.
So we get, that F(n) has greatest lower bound (glb) 1/2, therefore f(n) has glb 1/(2[sqrt]2). This glb – according to statement 2 above – is exact, answering Icarus's question.
[smiley=blacksquare.gif]
It took me too long to write this one, I'll consider the computational aspect in a separate post…
|
| « Last Edit: Apr 18th, 2004, 9:29am by Barukh » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Interesting Number
« Reply #19 on: Apr 19th, 2004, 5:54am » |
Quote Modify
|
OK, the computational aspect... 
This problem shows the limitations of floating point operations executed on modern processors. In fact, the erroneous result I’ve got in one of my simulations, was one of reasons for my false first conjecture.
Consider the following C code compiled for X86 processor:
Code:double f(unsigned n)
{
double r = (double)n * sqrt(2.0);
return (double)n * (r - floor(r));
}
|
|
Run it with n = 93222358. You will get a surprising 0.000.. If, instead, you estimate it using Microsoft Calculator (MC), you will get 93222357.646446609… The reason is that double precision code provides only 15 correct digits after the decimal point, while MC keeps with at least 32 (according to the help topic).
The same thing, IMHO, happened with Asterix’s estimations. For large n, the error is too big to show the right convergence. The following are the relevant values for F(n) computed with MC (they differ from Asterix’s value by a [sqrt]2 factor, but are in a way more spectacular):
1136689 0.500000000000048..
6625109 0.5000000000000014..
38613965 0.500000000000000045..
By the way, this raises the following interesing question: how does MC handle its level of accuracy (32 digits)? 
|
| « Last Edit: Apr 19th, 2004, 5:55am by Barukh » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Number
« Reply #20 on: Apr 19th, 2004, 6:10am » |
Quote Modify
|
You can use long doubles in C/C++
And in many math programs you can set the precision at any arbitrary number.. (though if you set it too high you may lack the necessary memory)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Interesting Number
« Reply #21 on: Apr 22nd, 2004, 5:24am » |
Quote Modify
|
on Apr 19th, 2004, 6:10am, towr wrote:| You can use long doubles in C/C++ |
|
Unfortunately, that won't help much - at most 3 additional digits (and some compilers won't do even that).
Quote:| And in many math programs you can set the precision at any arbitrary number.. (though if you set it too high you may lack the necessary memory) |
|
Have you got any particular package to recommend?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Interesting Number
« Reply #22 on: Apr 22nd, 2004, 5:54am » |
Quote Modify
|
on Apr 22nd, 2004, 5:24am, Barukh wrote:| Unfortunately, that won't help much - at most 3 additional digits (and some compilers won't do even that). |
|
Are you sure? It should double the precision afaik..
[edit]I've tried it out on all server/computers I have available, and for floats, doubles, long doubles they all give 31, 62, and 72 digits precision repectively. However, they won't all print all of the bits. (To find out how many bits precision they actually used, I took a fraction (1/271) and repeatedly multiplied by two till there was no fractional part left)[/edit]
Quote:Have you got any particular package to recommend?
|
|
I use Derive at home, but mathematica, maple and matlab are probably all better.. None of them is free though (unless you're into pirating software).
I also have Maxima, which is an open source program, but I haven't used it much, so I can't really say how good it is.
|
| « Last Edit: Apr 22nd, 2004, 6:35am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Interesting Number
« Reply #23 on: Apr 22nd, 2004, 7:13am » |
Quote Modify
|
Ok so If you are really good at programming you can make your own data structure. As for e.g. a linked list ofr however many precision digits you want. Making a simple header file for this datastructure will enable you to exploit however many precision you want.
|
|
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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove