Author |
Topic: Zeroes in binary expansion of sqrt(2) (Read 1319 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Zeroes in binary expansion of sqrt(2)
« on: Sep 1st, 2009, 9:19am » |
 Quote  Modify
|
Consider the binary expansion of sqrt(2)
1.01101010000010011110011001100111111...
Suppose a sequence of k zeroes or more first appears at such a position such that there are ak digits after the decimal (binary?) point upto that position.
For instance a1 = 0
a4 = 7
a5 = 7
etc.
If a sequence of k zeroes or more does not appear at all (which is probably not true) define ak = k.
Show that for all k,
ak >= k-1
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Zeroes in binary expansion of sqrt(2)
« Reply #1 on: Sep 3rd, 2009, 3:47pm » |
Quote Modify
|
| hidden: | Say  2 = r +  , with > 0. Letting f(x) = x2 - 2, we have
0 = f(2) = f(r) + f'(t),
for some t in [r, 2]. But then
= |f(r)| / f'(t) = |f(r)|/(2t)  |f(r)|/23/2.
But if r = m/2a, with m an integer, then
|f(r)| = | r2 - 2 | = | (m2 - 22a+1 ) / 22a | 1/22a,
so 1/22a+3/2 > 1/22a+2.
Therefore a string of (a+2) 0s cannot appear beginning a digits after the decimal point: if k a+2, then ak > a; that is, ak k-1. |
|
| « Last Edit: Sep 3rd, 2009, 3:47pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print