15
\$\begingroup\$

Pi is an irrational number, which means that its decimal representation never terminates or repeats itself.

Pi truncated to 41 decimal digits (40 places) is 3.1415926535897932384626433832795028841971.

If we ignore the decimal point and list the digits as a sequence of positive integers, avoiding duplicates, we get 3 1 4 15 9 2 6 5 35 8 97 93 23 84 62 64 33 83 27 950 28 841 971 (OEIS A064809).
(Notice that 15 appears in the sequence instead of 1 5 because 1 had already occurred.
Also note that 0 does not occur because it is not positive; 950 contains the first zero.)

To construct the first pirrational number we use this sequence to index into the digits of Pi (the first digit being 3, the second 1, etc.).

So the first digit of the first pirrational number is the 3rd digit of Pi,
the second digit is the 1st digit of Pi,
the third digit is the 4th digit of Pi,
the fourth is the 15th digit of Pi,
and so on.
A decimal point is added after the first digit to mimic Pi.

Thus the first pirrational number to 41 digits is 4.3195195867462520687356193644029372991880.
(Note that for the 30th digit I had to go all the way to the 974th digit of Pi.)

To construct the second pirrational number the process is repeated using the first pirrational number instead of Pi. (Pi itself may be called the zeroth pirrational number.) So the new sequence is 4 3 1 9 5 19 58 ... and the first piirational number is indexed to produce the second, which starts 9.14858....

Further pirrational numbers are created in the same way, each being generated from the one before.

Challenge

Your task is to write the shortest program possible that takes in two integers, N and D, and outputs the Nth pirrational number truncated to D decimal digits.

D is always positive but N is non-negative, and D digits of Pi should be output when N is 0.
When D is 1 it does not matter if the decimal point is present or not.

The input should come from stdin or the command line and output should go to stdout (or your language's closest alternatives).

Your program should work for all input values of N and D below 216, but it needn't be timely or efficient.

The shortest code in bytes wins.

(Note that pirrational numbers exits in other bases but everything in this challenge is done in base 10.)

\$\endgroup\$
12
  • \$\begingroup\$ Can we use built-in arbitrary-precision representations of Pi to get its digits? \$\endgroup\$ Sep 24, 2014 at 8:15
  • 1
    \$\begingroup\$ @MartinBüttner Sure. You could even get pi's digits online if you want as long as you are only getting pi's digits. \$\endgroup\$ Sep 24, 2014 at 8:23
  • \$\begingroup\$ @Calvin'sHobbies: Ah nice so I can just have the first 64ki digits of pi in a file? Should I add +1 for the filename? \$\endgroup\$
    – Claudiu
    Sep 24, 2014 at 16:06
  • \$\begingroup\$ Is that input range correct? For N=1, D=13393 for example, you'd need the 31 millionth digit of PI \$\endgroup\$
    – Claudiu
    Sep 24, 2014 at 16:52
  • \$\begingroup\$ The first 1 billion digits of pi only gets you 42,598 digits of the 1st pirrational number \$\endgroup\$
    – Claudiu
    Sep 24, 2014 at 17:02

2 Answers 2

4
\$\begingroup\$

Haskell, 431 400 369

import Data.List
g(q,r,t,k,n,l)|4*q+r-t<n*t=n:g(q#0,(r-n*t)#0,t,k,div(r#(30*q))t-n#0,l)|1<2=g(q*k,(2*q+r)*l,t*l,k+1,div(q*(7*k+2)+r*l)(t*l),l+2)
u w@(x:y:xs)=x:v y xs 0 w
v a(r:s)n w|a`elem`take n(u w)||r==0=v(a#r)s n w|1<2=a:v r s(n+1)w
m p=map(genericIndex p.pred)$u p
a#b=a*10+b
(x:s)%n=show x++'.':show(foldl1(#)$n`take`s)
f n d=print$iterate m(g(1,0,1,1,3,3))!!n%d

Gotta love infinite lists! Given enough time and memory, this program will eventually calculate the right answer for any N and D (I assume).

I'm generating the digits of pi with g using a spigot algorithm (shamelessly stolen from a guy called Stanley Rabinowitz), grouping the digits/creating the sequence using v and generating a pirrational number from these using m.

Here it is in action:

λ> f 0 10
"3.1415926535"
λ> f 1 10
"4.3195195867"
λ> f 2 10
"9.Interrupted. --didn't have the time to wait for this to finish
λ> f 2 4
"9.1485"
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I thought "Haskell!" when I saw the question, scrolled down, and smiled. \$\endgroup\$ Sep 25, 2014 at 14:25
3
\$\begingroup\$

Python 292 bytes

Quite inefficient, I've only been able to get a few digits of N=3 and none of N=4.

import sympy
def P(N,D,s=''):
 if N<1:return'3'+`sympy.pi.evalf(D+9)`[2:-9]
 for i in range(D):
    h=[];l='';j=i;x=0
    while-~j:
     x+=1;d=P(N-1,x)[-1];l+=d
     while'1'>P(N-1,x+1)[-1]:x+=1;l+='0'
     if(l in h)<1:h+=[l];l='';j-=1
    s+=P(N-1,int(h[i]))[-1]
 return s
s=P(*input())
print s[0]+'.'+s[1:]

Sample input:

0,20
3.1415926535897932384

1,20
4.3195195867462520687

2,10
9.148583196

3,5
9.9815
\$\endgroup\$
5
  • \$\begingroup\$ Golfs: Change =="0" to <"1". Make the inner while loop one line. Remove spaces around x += 1. if l not in h -> if(l in h)<1: N==0 -> N<1 \$\endgroup\$
    – isaacg
    Sep 24, 2014 at 7:50
  • \$\begingroup\$ @isaacg Thanks for those, I was in a bit of a rush when I posted and missed some obvious things. I probably wouldn't have realized you could do the string comparison though and the if(l in h)<1 is also pretty clever. \$\endgroup\$
    – KSab
    Sep 24, 2014 at 9:00
  • \$\begingroup\$ Some more: Initialize s as a parameter of P (def P(N,D,s=''):). str(...) can probably be written with backticks. while'1'>... saves the space. Make h a set and initialize with h=l,={''}, then write l in h as {l}<h. \$\endgroup\$
    – flornquake
    Sep 24, 2014 at 11:05
  • \$\begingroup\$ @flornquake That's pretty clever, especially the way you initialize it so python doesn't think its a dict. As I was putting this in though, I realized a fairly big optimization which unfortunately required h to be ordered. Still, that's a neat trick I'll try and remember. \$\endgroup\$
    – KSab
    Sep 24, 2014 at 12:19
  • \$\begingroup\$ @KSab That's even better. :) while j+1: can be shortened to while-~j, btw. \$\endgroup\$
    – flornquake
    Sep 24, 2014 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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