Pi chains.

Computer Science Level 5

The prime counting function, denoted by $\pi(x)$ counts the number of primes less or equal to $x$ .

Consider the process of continually finding the value of $\pi(x)$ of $x$ until it equals zero.

For example,for $x=1000$ we have $\pi(1000) = 168 \rightarrow 39 \rightarrow 12 \rightarrow 5 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 0$

$\pi(20) = 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \rightarrow 0$

From the above we can say that $1000$ has a pi chain of length 8 and $20$ has a pi chain of length 5 .

How many integers have a pi chain of length 9 ?

The answer is 47330.

2 solutions

Abdelhamid Saadi
Oct 8, 2015

let $f(n)$ denote the prime at position n.

so we have $f(1) = 2 , f(2) = 3. f(3) = 5 ...$

Now we have:

$f(1) = 2$

$f(2)= 3$

$f(3) = 5$

$f(5) = 11$

$f(11) = 31$

$f(31) = 127$

$f(127) = 709$

$f(709) = 5381$

$f(5381) = 52711$

the answer is $52711-5381=47330$

Sindhu G
Aug 20, 2014

5831 is a number which contains chain of 9 continue the process we get 52710 has chain 9 later 52711has chain 10 so answer is 52711-5831=47330

I have to write lot's of code to find the result

Ronak Agarwal - 6 years, 9 months ago

can you pls post your code here........?

Sarthak Tanwani - 5 years, 6 months ago

Pi chains.

The answer is 47330.

2 solutions

0 pending reports