Message Boards Message Boards

Formula for computing sqrt(2) of binary numbers.

GROUPS:

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:
POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

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.

POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

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 }$$

POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

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}$

POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

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

POSTED BY: Sander Huisman
Answer
6 months ago

You're right.So let it be.

Have a nice day. :)

Mariusz.

POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

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.

POSTED BY: Sam Carrettie
Answer
6 months ago

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

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

POSTED BY: Sander Huisman
Answer
6 months ago

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} $

POSTED BY: Mariusz Iwaniuk
Answer
6 months ago

Group Abstract Group Abstract