18
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ @Xcali The is no encoding involved, if I understand correctly. It is the binary expansion of pi, which is unique \$\endgroup\$ – Luis Mendo Jan 4 at 15:38
  • 1
    \$\begingroup\$ Is it known that the expansion of pi contains all finite sequences? Otherwise the challenge should state that as an assumption \$\endgroup\$ – Luis Mendo Jan 4 at 15:51
  • 2
    \$\begingroup\$ Note that "the digits of Pi are pseudo-random" is not per se equivalent to "any sequence of 1 and 0 can be found in the digits of Pi in binary form", because every decimal digit >1 has to use more than one digit in binary. It could be true, haven't thought it in details, but it seems to be an assumption on an assumption \$\endgroup\$ – Kaddath Jan 4 at 17:24
  • 5
    \$\begingroup\$ @Kaddath Let's put it this way: I'm pretty sure that if you find a binary sequence that is absent in π, then you win a prize that's substantially bigger than code-golfing points. \$\endgroup\$ – Roman Jan 4 at 17:27
  • 1
    \$\begingroup\$ In my opinion it should be stated more prominently, and earlier in the text. You cannot "find the starting position where..." if such position is not guaranteed/assumed to exist. Anyway, it's your challenge, so you choose the wording, however confusing I may find it ;-) \$\endgroup\$ – Luis Mendo Jan 4 at 17:31
12
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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):

enter image description here

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
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 114 bytes

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

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.