Message Boards Message Boards

GROUPS:

Formula for computing sqrt(2) of binary numbers.

Posted 3 years ago
8110 Views
|
9 Replies
|
15 Total Likes
|

In binary representation of $\sqrt{2}$ are there more ones or zeros?

$\sqrt{2}$ is an irrational number. Regardless what base numbering system youre using. There is no way to tell how many of each there are... because they go on forever.

The first so many 1.01101010000010... no predictability, there shouldn't be any "pattern" to the binary representation of it, and therefore, statistically, the ratio of the numbers of 1s and 0s will approach 1.

Is there a pattern?,So there is, and we will try to discover it.

How to find? well:

Using this identity:

$$\lfloor x\rfloor =x-\frac{1}{2}+\frac{\sum _{k=1}^{\infty } \frac{\sin (2 k \pi x)}{k}}{\pi }$$

Solving sum :

 Floor[x] == x - 1/2 + 1/Pi*Sum[Sin[2*k*Pi*x]/k, {k, 1, Infinity}]

$$\lfloor x\rfloor =-\frac{1}{2}+x-\frac{i \log \left(1-e^{-2 i \pi x}\right)}{2 \pi }+\frac{i \log \left(1-e^{2 i \pi x}\right)}{2 \pi }$$

At the first I'm find closed expression integer sequences of OEIS A084188 and substitute $x=2^{n+\frac{1}{2}}$ to first equation.

 Floor[x] == -(1/2) + x + ( I (Log[1 - E^(2 I \[Pi] x)] - Log[E^(-2 I \[Pi] x) (-1 + E^(2 I \[Pi] x))]))/(2 \[Pi]) /. x -> (Sqrt[2]*2^n)

$$\left\lfloor \sqrt{2} 2^n\right\rfloor =-\frac{1}{2}+2^{\frac{1}{2}+n}+\frac{i \left(-\log \left(1-e^{-i 2^{\frac{3}{2}+n} \pi }\right)+\log \left(1-e^{i 2^{\frac{3}{2}+n} \pi }\right)\right)}{2 \pi }$$

a checks if works:

 Table[-(1/2) + 2^(1/2 + n) + (I (Log[1 - E^(I 2^(3/2 + n) \[Pi])] - Log[E^(-I 2^(3/2 + n) \[Pi]) (-1 + E^(I 2^(3/2 + n) \[Pi]))]))/(2 \[Pi]) /. n -> m, {m, 0,
 19}] // N // Chop // Rationalize
(*{1, 2, 5, 11, 22, 45, 90, 181, 362, 724, 1448, 2896, 5792, 11585, 23170, 46340, 92681, 185363, 370727, 741455, 1482910}*)

then I'm need solve for $b(n)$ from equation $\{a(0)=1,a(n+1)=2 a(n)+b(n+2)\}$

 sol = RSolve[{b[n + 2] == a[n + 1] - 2*a[n], a[n] == -(1/2) + 2^(1/2 + n) + ( I (-Log[1 - E^(-I 2^(3/2 + n) \[Pi])] + 
 Log[1 - E^(I 2^(3/2 + n) \[Pi])]))/(2 \[Pi]), b[0] == 1, b[1] == 0}, {b[n], a[n]}, n]
 sol2 = FullSimplify[b[n] /. sol[[1]], Assumptions -> {n > 0, n \[Element] Integers}]

$$B_n=\frac{i \left(-i \pi +2 \log \left(1-e^{-i 2^{-\frac{1}{2}+n} \pi }\right)-2 \log \left(1-e^{i 2^{-\frac{1}{2}+n} \pi }\right)-\log \left(1-e^{-i 2^{\frac{1}{2}+n} \pi }\right)+\log \left(1-e^{i 2^{\frac{1}{2}+n} \pi }\right)\right)}{2 \pi } $$

We simplify $B_n$ expression to very simple form:

sol22=1/2 - (2 ArcTan[Cot[2^(-(3/2) + n) \[Pi]]])/\[Pi] + ArcTan[Cot[2^(-(1/2) + n) \[Pi]]]/\[Pi]

$$B_n=\frac{1}{2}-\frac{2 \tan ^{-1}\left(\cot \left(2^{-\frac{3}{2}+n} \pi \right)\right)}{\pi }+\frac{\tan ^{-1}\left(\cot \left(2^{-\frac{1}{2}+n} \pi \right)\right)}{\pi }$$

This is closed formula for the n-th digit in the binary representation of $\sqrt{2}$ for $n > 0$ and $n\in \mathbb{Z}$

Table[sol22 /. n -> m, {m, 1, 50}] // Expand

$1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1$

checks if works:

mm = N[Sqrt[2], 16]; RealDigits[mm, 2][[1]]

$1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1$

this last integer sequences can be found here OEIS A004539.

Another test checking closed expression to numerical value for the square root of two of base-10 :

sol3 = Table[Block[{$MaxExtraPrecision = 10000}, N[Limit[sol22, n -> m], 10]], {m, 1, 600}] // Rationalize // Quiet
N[FromDigits[{Drop[sol3, 0], 1}, 2], 166]

$1.41421356237309504880168872420969807856967187537694807317667973799073\ 2478462107038850387534327641572735013846230912297024924836055850737212\ 644121497099935831413222666$

N[Sqrt[2], 166]

$1.41421356237309504880168872420969807856967187537694807317667973799073\ 2478462107038850387534327641572735013846230912297024924836055850737212\ 644121497099935831413222666$

At the end of post a interesting sum: $$2 \sum _{n=1}^{\infty } \left(\frac{1}{2}-\frac{2 \tan ^{-1}\left(\cot \left(2^{-\frac{3}{2}+n} \pi \right)\right)}{\pi }+\frac{\tan ^{-1}\left(\cot \left(2^{-\frac{1}{2}+n} \pi \right)\right)}{\pi }\right) 2^{-n}=\sqrt{2}$$

  N[2*Sum[(1/2 - (2 ArcTan[Cot[2^(-(3/2) + n) \[Pi]]])/\[Pi] + ArcTan[Cot[2^(-(1/2) + n) \[Pi]]]/\[Pi])*2^(-n), {n, 1, 164}], 50]

$1.4142135623730950488016887242096980785696718753769$

PS:See attached Notebook.

Attachments:
9 Replies

Neat! Is it your result and is it new? Do you think expression can be simplified? This does not work

$$\arctan{u}+\arctan{v}=\arctan\left(\frac{u+v}{1-uv}\right)$$

but maybe similar trigonometry.

Yes, I found this formula.Is it new? Probably so.I searched in the web, but did not find a similar formula.

I tried to simplify, but I have not yet succeeded.

Appendix: To simplify $B_n$ formula.

We have: $$B_n=\frac{i \left(-i \pi +2 \log \left(1-e^{-i 2^{-\frac{1}{2}+n} \pi }\right)-2 \log \left(1-e^{i 2^{-\frac{1}{2}+n} \pi }\right)-\log \left(1-e^{-i 2^{\frac{1}{2}+n} \pi }\right)+\log \left(1-e^{i 2^{\frac{1}{2}+n} \pi }\right)\right)}{2 \pi }$$

 sol2 = (I (-I \[Pi] + 2 Log[1 - E^(-I 2^(-(1/2) + n) \[Pi])] - 2 Log[1 - E^(I 2^(-(1/2) + n) \[Pi])] - Log[1 - E^(-I 2^(1/2 + n) \[Pi])] +  Log[1 - E^(I 2^(1/2 + n) \[Pi])]))/(2 \[Pi])
 sol5 = FullSimplify[Re[sol2] // ComplexExpand, Assumptions -> n \[Element] Integers]
 Table[sol5, {n, 1, 5}]

$\left\{\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(\sqrt{2} \pi \right)}{1-\cos \left(\sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)}{2 \pi },\frac{\pi -4 \tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)+2 \tan ^{-1}\left(\frac{\sin \left(32 \sqrt{2} \pi \right)}{1-\cos \left(32 \sqrt{2} \pi \right)}\right)}{2 \pi }\right\}$

Now we need find a pattern.The first ingredient in the formula: We have: $$\left\{4 \tan ^{-1}\left(\frac{\sin \left(\sqrt{2} \pi \right)}{1-\cos \left(\sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(2 \sqrt{2} \pi \right)}{1-\cos \left(2 \sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(4 \sqrt{2} \pi \right)}{1-\cos \left(4 \sqrt{2} \pi \right)}\right),4 \tan ^{-1}\left(\frac{\sin \left(8 \sqrt{2} \pi \right)}{1-\cos \left(8 \sqrt{2} \pi \right)}\right),\tan ^{-1}\left(\frac{\sin \left(16 \sqrt{2} \pi \right)}{1-\cos \left(16 \sqrt{2} \pi \right)}\right)\right\}$$

 FindSequenceFunction[{1, 2, 4, 8, 16}, n]
 (*2^(-1 + n)*)

Finding the second ingredient in the formula is the same how I found at first:

 FindSequenceFunction[{2, 4, 8, 16, 32}, n]
 (*2^n*)

Substitution:

$$\frac{\pi -\left(4 \tan ^{-1}\left(\frac{\sin \left(n \sqrt{2} \pi \right)}{1-\cos \left(n \sqrt{2} \pi \right)}\right)\text{/.}\, n\to 2^{n-1}\right)+\left(2 \tan ^{-1}\left(\frac{\sin \left(n \sqrt{2} \pi \right)}{1-\cos \left(n \sqrt{2} \pi \right)}\right)\text{/.}\, n\to 2^n\right)}{2 \pi }$$

  FullSimplify[(\[Pi] - (4 ArcTan[Sin[n Sqrt[2] \[Pi]]/(1 - Cos[n Sqrt[2] \[Pi]])] /. n -> 2^(n - 1)) + (2 ArcTan[Sin[n Sqrt[2] \[Pi]]/(
  1 - Cos[n Sqrt[2] \[Pi]])] /. n -> 2^n))/(2 \[Pi])] // Expand

$$B_n = \frac{1}{2}-\frac{2 \tan ^{-1}\left(\cot \left(2^{-\frac{3}{2}+n} \pi \right)\right)}{\pi }+\frac{\tan ^{-1}\left(\cot \left(2^{-\frac{1}{2}+n} \pi \right)\right)}{\pi }$$

Just checking: is this, then, some kind of spigot algorithm for sqrt(2)?

https://en.wikipedia.org/wiki/Spigot_algorithm

No is not algorithm ,its better than that.It simple, its a formula,or function.

An example:

To start calculating binary digits from, say, the 8th place only need substitute for n=8,9,10,11,12,13,14,15....That it's all.

formula =1/2 - (2 ArcTan[Cot[2^(-(3/2) + n) \[Pi]]])/\[Pi] + ArcTan[Cot[2^(-(1/2) + n) \[Pi]]]/\[Pi]

sol = Table[formula, {n, 8, 15}] // N // Round

${1, 0, 0, 0, 0, 0, 1, 0}$

and say from n=1....15:

 sol2 = Table[formula, {n, 1, 15}] // N // Round

${1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0}$

I think it is then a spigot algorithm, because you have extensions, like the famous one for Pi in base 16 which calculates the nth digit directly... Algorithm here can be read as function:

> A further refinement is an algorithm which can compute a single arbitrary digit, without first computing the preceding digits: an example is the Bailey-Borwein-Plouffe formula, a digit extraction algorithm for ? which produces hexadecimal digits.

https://en.wikipedia.org/wiki/Spigot_algorithm

You're right.So let it be.

Have a nice day. :)

Mariusz.

Finding formula for the n-th digit in the binary representation of Sqrt[2] using Floor function.

 sol = RSolve[{b[n + 2] == a[n + 1] - 2*a[n], a[n] == Floor[Sqrt[2]*2^n], b[0] == 1, b[1] == 0}, {b[n], a[n]}, n]
 sol2 = FullSimplify[b[n] /. sol[[1]], Assumptions -> {n > 0, n \[Element] Integers}]

$$B_n=-2 \left\lfloor 2^{-\frac{3}{2}+n}\right\rfloor +\left\lfloor 2^{-\frac{1}{2}+n}\right\rfloor$$

This is formula for the n-th digit in the binary representation of $\sqrt{2}$ for $n > 0$ and $n\in \mathbb{Z}$ using Floor function.

 Table[sol22 /. n -> m, {m, 1, 50}] 

$ {1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, \ 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, \ 1, 0, 0, 1} $

I am interested in proving that the proportion of binary digits of $\sqrt{2}$ is exactly $\frac{1}{2}$, and I have worked on this for a long time. You wrote a great article using the Fourier series expansion for the fractional part function. I am looking at a simpler formula (I have yet to find one!) but have asked my question on StackExchange, here. For your convenience, my question is posted below:

Is it possible to find an expression of the form $$\lfloor 2^n \sqrt{2}\rfloor = \sum_{k=1}^r (\alpha_k + \beta_ki)\cdot\Big(a_k+b_k i\Big)^n, $$ where $i^2 = -1$ and $\alpha_k, \beta_k, a_k, b_k$ real numbers? Maybe with $r< 5$ if possible. I am trying to compute the mean value (average) of $\{ 2^n \sqrt{2}\}= 2^n \sqrt{2} - \lfloor 2^n \sqrt{2}\rfloor$ over $n=0, 1,2, \cdots$. Let us denote as $p$ this mean value: $p$ is the proportion of binary digits of $\sqrt{2}$ equal to one, and $p$ is widely believed to be equal to $\frac{1}{2}$.

Note that $$p=\lim_{n\rightarrow\infty} p_n, \mbox{ with } p_n = \frac{1}{n}\sum_{k=1}^n \Big( 2^k \sqrt{2} - \lfloor 2^k \sqrt{2}\rfloor\Big).$$ Assuming we have a simple closed form for $\lfloor 2^k \sqrt{2}\rfloor$ as suggested in the first formula, then we can have a closed form for $p_n$, involving a finite number of terms. I don't expect this to be true if you replace $\sqrt{2}$ by (say) $\pi$ or $\log 2$, but I would expect this to work with any quadratic irrational.

Of course you can always use the Fourrier series to represent the fractional part function, but I don't think it would be easy to handle: it involves an infinite number of terms ( $r=\infty$.)

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract