# Formula for computing sqrt(2) of binary numbers.

GROUPS:
 Mariusz Iwaniuk 7 Votes 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: Answer 1 year ago 8 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. Answer 1 year ago  Mariusz Iwaniuk 1 Vote 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 }$$ Answer 1 year ago  Mariusz Iwaniuk 2 Votes 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. Answer 1 year ago  Just checking: is this, then, some kind of spigot algorithm for sqrt(2)?https://en.wikipedia.org/wiki/Spigot_algorithm Answer 1 year ago  Mariusz Iwaniuk 1 Vote 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}$Answer 1 year ago  Sander Huisman 1 Vote 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 Answer 1 year ago  Mariusz Iwaniuk 1 Vote You're right.So let it be.Have a nice day. :)Mariusz. Answer 1 year 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} \$
Answer
1 year ago