7
\$\begingroup\$

Introduction

Pi is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089...

Let's treat each digit as an instruction as to how to get to the next digit.

  • The first digit is 3.
  • Counting three digits after the first digit, we arrive at 1.
  • One digit after this 1 is a 5.
  • Five digits after that is 3.
  • Three digits later is 9.

The digits included in this sequence are in bold: 3.1415926535897932384626433...

If a digit is 0, the next digit is 10 later.

Challenge

Given a positive integer n less than 1000, find out how many of the first n digits of pi, including the initial 3, are in the sequence.

Furthermore, your code's characters must have a "pi-based frequency". Choose any character; your program must use exactly three of that character. Choose another character, use exactly one of it. Choose another character, use it four times. You may continue for as long as you wish, but each character chosen must be different.

For example, the following snippet complies with the frequency rules (but produces the wrong output):

print "r\"rriiiittttnttttppppp" 
# Uses 3 quotation marks, 1 space, 4 r's, 1 \, 5 i's, 9 t's, 2 n's, and 6 p's.

For the purposes of "pi-based frequency", treat the digit 0 as 10.

You may write a function or a full program. You may not use any built-in constants, trigonometry functions, or complex number functions to find pi.

Shortest code in characters wins. The tiebreaker is the most votes.

Examples

Input  Output
-------------
 1      1
 2      1
 3      1
 4      2
 5      3
 28     8
 77     17
 123    28
 328    73
 625    122
 999    189
\$\endgroup\$
  • \$\begingroup\$ Hardcore level - over 9000! \$\endgroup\$ – Optimizer Nov 6 '14 at 21:22
  • \$\begingroup\$ The source limitations makes the max length of the program to be 521 characters (counting just he printable ASCII range) \$\endgroup\$ – Optimizer Nov 6 '14 at 21:28
  • \$\begingroup\$ I know. Just saying. \$\endgroup\$ – Optimizer Nov 6 '14 at 21:39
4
\$\begingroup\$

Mathematica, 253 bytes

f=(For[i=0;j=1,j<=#,j+=Mod[RealDigits[9801/Sqrt@8/Sum[(4j)!(1103+26390j)/(j!)^4/396^(4j),{j,0,125}],10,999][[1,j]]-1,10]+1;++i];"99iiiitS===oooo8862^^^^^^\uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{\{{{{{{}}}}}}}}--@@@@@@";i)&

Ungolfed:

f = (
   For[i = 0; j = 1, j <= #, 
    j += Mod[
       RealDigits[
          9801/Sqrt@8/
           Sum[(4 j)! (1103 + 26390 j)/(j!)^4/396^(4 j), {j, 0, 125}],
           10, 999][[1, j]] - 1, 10] + 1; ++i];
   "99iiiitS===oooo8862^^^^^^uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{{{{{{{}}}}}}}}--@@@@@@";
   i
   ) &

Usage is f[999].

A whopping 122 bytes are used to pad the code with a useless string to get the right character frequencies. I'll try to improve that tomorrow.

The character frequencies should match the digits of pi in this order:

3#/&(,![)4+9j0it"S=;]ro862^usRqM1mlgFfeDda5<{}-@

I confirmed that there is some correct order with the following snippet:

Sort[Last /@ 
   Tally[Characters@
     "f=(For[i=0;j=1,j<=#,j+=Mod[RealDigits[9801/Sqrt@8/Sum[(4j)!(\
1103+26390j)/(j!)^4/396^(4j),{j,0,125}],10,999][[1,j]]-1,10]+1;++i];\"\
99iiiitS===oooo8862^^^^^^\
uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{\
{{{{{{}}}}}}}}--@@@@@@\";i)&"]] == 
 Sort[RealDigits[Pi, 10, 48][[1]] /. 0 -> 10]

I'm computing pi with Ramanujan's series. It converges to 1000 digits in 125 terms. Due to golfing reasons, I recompute the 999 necessary digits for every single digit of the subsequence, but it still completes within a second for n = 999 on my machine.

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

C++, 550 428

#include<iostream>
long a[3505],b,c=3505,d,e,f=10000,g,h,i,j,k,l,x,z;int main(){int P[1000];int M[4];for(;(b=c-=14)>0;){for(;--b>0;){d*=b;if(h==0)d+=2000*f;else d+=a[b]*f;g=b+b-1;a[b]=d%g;d/=g;}h=e+d/f;i=h;for(j=0;j<4;j++){M[j]=i%10;i/=10;}for(j=3;j>=0;j--){P[z]=M[j];z++;};d=e=d%f;}std::cin>>k;j=0;while(j<k){x=P[j];(x==0)?x=10:x;j+=x;l++;}std::cout<<l;}//{{{:+-2220000%,ddhhhhiiiiiiijjnorrt, # # # ,MQQQRRRSSSSSSSSTTTTTTTTT:}}}

I'm not 100% confident that my code has a π-based frequence. I will check tomorrow. If it works, there is a direct correspondance between the frequencies of the following characters and the 60 first digits of π.

  zdj(mxakcb)1[*uPes>0M34t;l]g+=n%wo-,hQ{}Rr<f/Si :sT#2
  3.141592653589793238462643383279502884197169399375105820974944

The craziest part is the computation of π. It is done thanks to an implementation of a fascinating spigot algorithm:

enter image description here

Edit: you can generate n digits of π with this 288 characters-long program: :)

#include<iostream>
#include<vector>
using namespace std;long b,c,d,e,f=10000,g,h,l;int main(){cout<<"? ";cin>>l;cout<<": ";l=(l/4+1)*14;c=l;vector<long> a;a.resize(l);for(;(b=c-=14)>0;){for(;--b>0;){d*=b;if(h==0)d+=2000*f;else d+=a[b]*f;g=b+b-1;a[b]=d%g;d/=g;}h=e+d/f;cout<<h;d=e=d%f;}}
\$\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.