Find a sequence in the binary digits of π

Question

Given a binary sequence of finite length, find the starting position where this sequence first appears in the binary digits of π (after the decimal). You can assume that an answer exists for any input sequence.

The binary digits of π start with

11.001001000011111101101010100010001000010110100011...

and digits will be counted such that the first one after the decimal (the first 0 digit) has index 1.

Examples

The requested function is related to OEIS A178707 but differs in that input sequences may have leading zeros. OEIS A178708 and OEIS A178709 provide good test cases for large sequences of 0's and 1's.

Some test cases below 10^9:

• 00100 → 1
• 11 → 11
• 00000000 → 189
• 11111111 → 645
• 0101000001101001 → 45038
• 00000000000000000000 → 726844
• 11111111111111111111 → 1962901
• 01000111010011110100110001000110 → 105394114
• 111111111111111111111111111111 → 207861698
• 100000000110000001100111100001 → 987654321

Input/output formats

You can use any input and output formats: strings, lists, encoding the binary digits in integers, etc. Just use what is convenient for you.

Limitations

Your program must be able to accept sequences of arbitrary (finite) length if run on an infinite-size computer, and terminate in finite time (assuming that a match always exists, which is what most people seem to believe in 2021 based on the pseudo-randomness of the digits of π).

Scoring

This is code golf, so the shortest program (in bytes or bits/8) wins.

Answer 1

JavaScript (Node.js),  167  165 bytes

This is long and slow ... but it should work for any input in theory.

s=>{for(k=t=1n,l=q=2n,n=0n,r=6n,o='#';!~(i=o.search(s));)n=4n*q+t*~n<r?(o+=n,q+(q+=q)-r)/t-n<<(r+=r+t*n*2n)/r:(q*7n*k+2n-r*++l)/(r=(r-q-q)*l,q*=k++,t*=l++);return i}

Try it online!

This is derived from the C# entry on this Rosetta Code page.

The C# code is derived from Java, which is derived from Icon, which is derived from PicoLisp, which is derived from Haskell, which is based on this paper. :-p

Answer 2

MATL, 28 bytes

`YPX$3-@X$W*kc4Y22@&ZaGXftn~

Try it online!

The code is very inefficient. Test cases beyond the second time out in the online compiler, but work offline. Here's an example with the fourth case (it takes about 25 seconds):

Explanation

The code keeps trying increasingly long truncated binary expansions of the fractional part of 𝜋, until the input is contained in the expansion.

`        % Do...while
  YP     %   Push pi as a double
  X$     %   Convert to symbolic. This recognizes pi's double representation
  3-     %   Subtract 3
  @      %   Push iteration index, n, starting at 1
  X$     %   Convert to symbolic. This avoids overflow in the next operation
  W      %   Exponential with base 2
  *      %   Multiply
  k      %   Floor(round down). This gives floor((pi-3)*2^n) as a symbolic variable 
  c      %   Convert to char. This gives a sequence of decimal digits
  4Y2    %   Push '0123456789' (input alphabet for base conversion)
  2      %   Push 2 (output base for conversion)
  @      %   Push n (number of digits in the output)
  &Za    %   Base conversion. This gives the binary expansion with n digits
  G      %   Push input
  Xf     %   Index of ocurrences of the input. May be empty
  t      %   Duplicate
  n~     %   Number of elements, negate. This gives 1 if the input was not found
         % End (implicit). A new iteration is run if the top of the stack is 1
         % Display (implicit). The stack contains several empty arrays, and a 
         % non-empty array with the solution. Empty arrays are not displayed

Answer 3

Wolfram Language (Mathematica), 49 bytes

0//.n_/;RealDigits[Pi,2,Tr[1^#],-n][[1]]!=#:>n+1&

Try it online!

thanks @Roman for -2bytes and @att for -3 bytes

Answer 4

Charcoal, 114 bytes

≔²η≔±⁶ρ≔¹τ≔¹κ≔⁰ν≔³λＷ¬№ψθ¿‹⁺×⁴ηρ×⊕ντ«≔⁺ψνψ≔⊗⁻ρ×τνσ≔⁻÷⊗⁺׳ηρτ⊗νν≦⊗η≔σρ»«≔×⁺⊗ηρλσ≧×κη≧×λτ≔÷⁺⁺×⁷η²×ρλτν≧⁺²λ≦⊕κ≔σρ»Ｉ⌕ψθ

Try it online! Link is to verbose version of code. Uses the same source as @Arnauld's answer, so you can read up on the spigot algorithm there. Builds up the entire binary expansion as it goes and searches from the beginning on each loop but that turns out to be faster than just keeping the necessary number of bits.

Answer 5

R, 261 259 bytes

function(x,p=''){while((a=regexpr(x,p<-paste0(c(p,(16*(4*s(F,1)-2*s(F,4)-s(F,5)-s(F,6))%%1)%/%2^(3:0)%%2),collapse='')))<0)F=F+1;a}
s=function(n,d){for(k in 0:n){p=1;for(i in seq(l=n-k))p=(16*p)%%d;F=(F+p/d)%%1;d=d+8};while((f=(T=T/16)/(d=d+8))>2e-16)F=F+f;F}

Try it online!

This is pretty long and can almost certainly be golfed better...

The function s calculates the value of one of the four summations of the Bailey–Borwein–Plouffe forumla.

We then use four calls to s to implement a spigot algorithm to sequentially calculate each hexadecimal digit of pi, and convert these into groups of 4 bits.

Finally, each iteration of the while loop adds these next 4 bits to the string a, and checks whether it now contains the search string x, halting and ouputting the index if this is true.