Sunday, June 23, 2013

Another number theory problem

This is the second post dedicated to the problems set posted on "Math, Math Education, Math Culture" LinkedIn group. Here is the original LinkedId discussion, again ... if you happen to have a LinkedIn account. Here is the problem:

Prove that the sequence a1=1, a2=11, a3=111, a4=1111,... contains an infinite sub-sequence whose terms are pairwise relatively prime.

Few observations first of all, without proving them as it should be fairly trivial, e.g. using induction: $$a_{m+n}=a_{m}\cdot 10^{n}+a_{n}$$

From the above: $$a_{m\cdot n} = a_{(m - 1)\cdot n}\cdot 10^{n} + a_{n} = a_{n}\cdot 10^{n\cdot (m-1)} + a_{n}\cdot 10^{n\cdot (m-2)} + ... + a_{n}\cdot 10^{n} + a_{n}$$

So if $a_{n}$ is divisible by $t\in \mathbb{N}, t>1$ then $a_{m\cdot n}$ is also divisible by $t$ (1).

Now, let's consider the sub-sequence $\left \{ a_{p_{k}} \right \}_{k=1}^{\infty } \subset \left \{ a_{n} \right \}_{n=1}^{\infty }$, where $p_{k}$- k-th prime. I state that this sub-sequence satisfies the condition of the problem. Let's prove it by contradiction.

I.e. let's assume there $\exists k \neq m$ such that $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$. Because $\gcd\left ( p_{m}, p_{k}\right )= 1$ (i.e. both are prime numbers), then, by applying Bezout's theorem (or lemma), there $\exists r,s\in \mathbb{Z}$ such that: $$r\cdot p_{m} + s\cdot p_{k}=1$$

Both $r,s$ can't be negative and positive as the same time, so we can rewrite it this way: $$r\cdot p_{m} = s\cdot p_{k} + 1$$ assuming both $r$ and $s$ are positive this time.

Because we assumed $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= d > 1$, then $d$ should also divide both $a_{r\cdot p_{m}}, a_{s\cdot p_{k}}$ (using (1) proved above). But $$a_{r\cdot p_{m}} = a_{s\cdot p_{k}+1} = a_{s\cdot p_{k}} \cdot 10 + a_{1}$$ which means $d>1$ also divides $a_{1}=1$. Contradiction.

As a result $\forall k \neq m$, $\gcd\left ( a_{p_{m}}, a_{p_{k}}\right )= 1$.

Saturday, June 8, 2013

Another probability problem

An interesting set of problems was posted on "Math, Math Education, Math Culture" LinkedIn group few weeks ago. I engaged myself in addressing few of them, so I will be posting my solutions in the next few posts. Just to clarify this from the beginning, interesting doesn't necessarily mean difficult. This particular post is dedicated to the probability problem and here is the original LinkedId discussion, if you happen to have a LinkedIn account. Otherwise, continue reading this post. Here is the problem ...

We have n urns, each of these urns contains A white balls and B black balls. We assume a ball from the first urn is randomly picked and then placed into the second urn, then another ball from the second urn is randomly picked and then placed into the third urn, and so on, until a ball from the last urn is finally randomly picked. If this last ball is white, what probability has this fact?

One way to attack the problem is to use total probability (Wikipedia is probably more descriptive on this topic).

Let's define the following two events:
- Wi - white ball is picked from i-th urn
- Bi - black ball is picked from i-th urn.
It is worth noting that $P\left ( W_{i} \right )+P\left ( B_{i} \right )=1$.

Now, applying total probability we have: $$P\left ( W_{n} \right ) = P\left ( W_{n} | W_{n-1} \right )\cdot P\left ( W_{n-1} \right )+P\left ( W_{n} | B_{n-1} \right )\cdot P\left ( B_{n-1} \right )$$ Where:
- $P\left ( W_{n} | W_{n-1} \right )=\frac{A+1}{A+B+1}$ - translated as "probability to pick a white ball from n-th urn, knowing that a white ball was picked from n-1-th urn"
- $P\left ( W_{n} | B_{n-1} \right )=\frac{A}{A+B+1}$ - translated as "probability to pick a white ball from n-th urn, knowing that a black ball was picked from n-1-th urn".

Putting all these together, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot \frac{1}{A+B+1}+\frac{A}{A+B+1}$$ Or, if we note $k= \frac{1}{A+B+1}$, then: $$P\left ( W_{n} \right )= P\left ( W_{n-1} \right )\cdot k+A\cdot k$$

Continuing doing this recursively, we obtain: $$P\left ( W_{n} \right )= P\left ( W_{1} \right )\cdot k^{n-1} + A\cdot \left ( k^{n-1}+k^{n-2}+...+k^{2}+k \right )$$ Where (because W1 relates to the very first urn): $$P\left ( W_{1} \right )=\frac{A}{A+B}=A\cdot \frac{k}{1-k}$$

Finally: $$P\left ( W_{n} \right )=A\cdot \frac{k^{n}}{1-k}+A\cdot \frac{k^{n}-k}{k-1}=\frac{A}{A+B}$$

Which means, the trick with picking randomly a ball and moving it to the next urn has no effect on the final probability. Interesting, isn't it?

Sunday, May 26, 2013

Tackling Andrica's conjecture. Part 3

Here is an interesting, but slightly detached from the previous two articles, result ... Let's look at the following two sequences: $$a_{n}=\sqrt{p_{n+1}} - \sqrt{p_{n}}$$ $$b_{n}=ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}}$$

Here is a short Python code to visualise the sequences:


import math
import matplotlib.pyplot as plt

primes = []

def isPrime(n):
l = int(math.sqrt(n)) + 1
for i in xrange(2,l):
if (n % i) == 0:
return False
return True

def calculateLog(sqrt_p1, sqrt_p2):
sqrt_1_p2 = 1.0 + sqrt_p2
r = math.log(sqrt_1_p2/(1.0 + sqrt_p1))
return r * sqrt_1_p2

N = 1500000

print "populate primes ..."
for i in xrange(2, N):
if isPrime(i):
primes.append(i);

sqrt_diff = [] # sqrt diffs
diff = []      # simple diffs
log_calcs = [] # log calcs
x = []
for i in xrange(1, len(primes)):
sqrt_p2 = math.sqrt(primes[i])
sqrt_p1 = math.sqrt(primes[i-1])
sqrt_diff.append(sqrt_p2 - sqrt_p1)
diff.append(primes[i] - primes[i-1])
log_calcs.append(calculateLog(sqrt_p1, sqrt_p2))
x.append(i)

for i in xrange(len(sqrt_diff)):
print sqrt_diff[i]," = s(",primes[i+1],") - s(",primes[i],")"

plt.subplot(311)
plt.plot(x, sqrt_diff)
plt.subplot(312)
plt.plot(x, log_calcs)
plt.subplot(313)
plt.hist(diff, 1000)
plt.show()


And here is how both sequences look like ($a_{n}$ the first and $b_{n}$ the second): Quite asymptotic, aren't they? Indeed they are ...

Lemma 3. $$\sqrt{p_{n+1}} - \sqrt{p_{n}} \leq ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )^{1+\sqrt{p_{n+1}}} \leq \left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\cdot \left ( \sqrt{p_{n+1}} - \sqrt{p_{n}} \right )$$

Let's look at this function $f_{6}(x)=\frac{\sqrt{p_{n+1}}}{1+x\cdot \sqrt{p_{n+1}}}$. Obviously, ${ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )}'=f_{6}(x)$. As a result $$\int_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = ln\left ( 1+x\cdot \sqrt{p_{n+1}} \right )|_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1}=ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )$$

According to Mean Value Theorem, $\exists \mu \in \left (\sqrt{\frac{p_{n}}{p_{n+1}}} ,1 \right )$ such that: $$\int_{\sqrt{\frac{p_{n}}{p_{n+1}}}}^{1} f_{6}\left ( x \right )dx = f_{6}\left ( \mu \right )\cdot \left ( 1- \sqrt{\frac{p_{n}}{p_{n+1}}} \right )$$

Putting all together: $$ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right ) = \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\mu \cdot \sqrt{p_{n+1}}}$$

Because $$\sqrt{\frac{p_{n}}{p_{n+1}}}< \mu < 1 \Rightarrow 1+\sqrt{p_{n}}< 1+\mu \cdot \sqrt{p_{n+1}} < 1+\sqrt{p_{n+1}}$$

And we get $$\frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq ln\left ( \frac{1+\sqrt{p_{n+1}}}{1+\sqrt{p_{n}}} \right )\leq \frac{\sqrt{p_{n+1}}-\sqrt{p_{n}}}{1+\sqrt{p_{n}}}$$ which proves this lemma.

Noting $\Delta_{n}=\sqrt{p_{n+1}}-\sqrt{p_{n}}$, this becomes: $$\frac{\Delta_{n}}{1+\sqrt{p_{n+1}}}\leq ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )\leq \frac{\Delta_{n}}{1+\sqrt{p_{n}}}$$ or $$\frac{1+\sqrt{p_{n}}}{1+\sqrt{p_{n+1}}}\leq ln\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}}\leq 1$$

Is this result of any use? I don't know yet, but it looks like: $$\left ( 1 + \frac{\Delta_{n}}{1+\sqrt{p_{n}}} \right )^{\frac{1+\sqrt{p_{n}}}{\Delta_{n}}} \rightarrow e, n \to \infty$$ using this result.

Tuesday, May 7, 2013

Few cloud based APIs

If you came to the point of being ready to start a new project, here are few links to some cloud based APIs to consider:

1. StormPath - quite good a user management and you get free perks as well.

2. Mandrill - if you need a good notification (email based) system. Again, quite a decent free of charge limit.

3. MongoLab - well, that's MongoDB. And if you don't know what it is by now, then you shouldn't worry about it at all (caught your attention? Google for it then). Free 0.5Gb instance is a good starting point.

4. Google Chart API - Not the best one, but it's free and quite ok(ish) for building dashboards.

5. GeckoBoard - a better dashboard API, with HTML5 support (WebSockets and all that stuff), not for free though ...

And of course, you can test all that with Amazon for free for one year.

This is it for now, I will do my best to keep this list updated.

Sunday, November 11, 2012

Tackling Andrica's conjecture. Part 2

With the previous post, I stopped at the argument that $f_{4}(x)=\pi (x) - \sqrt{x}$ seems to be ascending for prime arguments. Apparently, this is a necessary and sufficient condition, i.e.:
Lemma 1. Andrica's conjecture is true iff function $f_{4}(x)=\pi (x) - \sqrt{x}$ is strictly ascending ($x < y \Rightarrow f(x) < f(y)$) for prime arguments.
The proof is given in the following discussion with the math.stackexchange.com community.
It is worth mentioning that $f_{4}(x)$ is descending in between prime numbers. For example for $\forall x\in \left ( p_{n}, p_{n+1} \right )$, $f_{4}(x)=n - \sqrt{x}$ and ${f_{4}}'(x)=-\frac{1}{2\cdot \sqrt{x}} < 0$.
In fact the purpose of the discussion was to prove that $$\sqrt{p_{n}} < n$$ which turns to be true for $\forall n \geq 2$, using Rosser's theorem.
Interesting result, out of this inequality, is that $$\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ because $\sqrt{p_{1}}=\sqrt{2} > 1$. However, $$\sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right )=\sqrt{p_{n}} - \sqrt{p_{1}} < n-1$$ and as a result $$\frac{1}{n-1}\cdot \sum_{k=2}^{n}\left ( \sqrt{p_{k}} - \sqrt{p_{k-1}} \right ) < 1$$ or, in other words, on average Andrica's conjecture seems to be true.
But, leaving the statistical argument aside, how do we prove that $f_{4}(x)$ is ascending for prime arguments?
I don't have the answer yet, but here is where I stuck ...
Let's have a look at the following function $$f_{5}(x)=1 - \sqrt{p_{n+1} + x} + \sqrt{p_{n} + x}$$ This function is ascending $\forall x \geq -p_{n}$ $${f_{5}(x)}'= -\frac{1}{2\cdot \sqrt{p_{n+1} + x}} + \frac{1}{2\cdot \sqrt{p_{n} + x}} > 0$$ because $\sqrt{p_{n+1} + x} > \sqrt{p_{n} + x}$, for $\forall x \geq -p_{n}$.
This function also has a zero, $1=\sqrt{p_{n+1} + x} - \sqrt{p_{n} + x} \Leftrightarrow$ $$1 = p_{n+1}+p_{n} +2\cdot x -2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)} \Leftrightarrow$$ $$2\cdot \sqrt{(p_{n+1} + x)\cdot (p_{n} + x)}=p_{n+1}+p_{n} +2\cdot x - 1 \Leftrightarrow$$ $$4\cdot (p_{n+1} + x)\cdot (p_{n} + x)=p_{n+1}^{2}+p_{n}^{2}+4\cdot x^{2}+1+2\cdot p_{n+1}\cdot p_{n}+$$ $$+4\cdot p_{n+1}\cdot x-2\cdot p_{n+1}+4\cdot p_{n}\cdot x-2\cdot p_{n}-4\cdot x \Leftrightarrow$$ jumping ahead $$2\cdot p_{n+1}\cdot p_{n}=p_{n+1}^{2}+p_{n}^{2}+1-2\cdot p_{n+1}-2\cdot p_{n}-4\cdot x \Leftrightarrow$$ $$4\cdot x=(p_{n+1}-p_{n})^{2}-2\cdot (p_{n+1}+p_{n})+1=(p_{n+1}-p_{n}-1)^{2}-4\cdot p_{n}$$ as a result $$x_{0}=\left( \frac{p_{n+1}-p_{n}-1}{2} \right)^{2}-p_{n}$$ Obviously, $x_{0} > -p_{n}$.
And now:
Lemma 2. $f_{4}(p_{n+1}) > f_{4}(p_{n})$ iff $x_{0} < 0$, where $x_{0}$ is zero of $f_{5}(x)$.
First of all $$x_{0} < 0 \Leftrightarrow p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$$
As a result, if $f_{4}(p_{n+1}) > f_{4}(p_{n})$ this is equivalent (from Lemma 1) with $\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$ (Andrica's inequality for $p_{n}, p_{n+1}$). But then $$p_{n+1} - p_{n}=(\sqrt{p_{n+1}}-\sqrt{p_{n}})\cdot (\sqrt{p_{n+1}}+\sqrt{p_{n}}) < \sqrt{p_{n+1}}+\sqrt{p_{n}}$$ and applying Andrica's inequality again $$p_{n+1} - p_{n} < \sqrt{p_{n}}+1+\sqrt{p_{n}}=2\cdot \sqrt{p_{n}}+1$$ so $x_{0} < 0$.
Now, if $x_{0} < 0$, where we know that $x_{0} > -p_{n}$, and the fact that $f_{5}(x)$ is ascending then we have $$x_{0} < 0 \Rightarrow 0=f_{5}(x_{0}) < f_{5}(0)=1 - \sqrt{p_{n+1}} + \sqrt{p_{n}}$$ or $$\sqrt{p_{n+1}}-\sqrt{p_{n}} < 1$$ and then (Lemma 1) $f_{4}(p_{n+1}) > f_{4}(p_{n})$.
Do we know if $p_{n+1}-p_{n} < 2\cdot \sqrt{p_{n}}+1$ for $\forall n$?
Not yet, but we are close. One result, proved by Martin Huxley, states that $p_{n+1}-p_{n} < p_{n}^{\theta }$ for $\theta > \frac{7}{12}$ and sufficiently large $n$. In our case, $\theta =0.5$
Another result by Baker, Harman and Pintz states that $\theta$ may be taken to be 0.525.

Sunday, September 23, 2012

Tackling Andrica's conjecture

Andrica's conjecture is one of those mathematical statements which are extremely easy to formulate, but complicated to prove. In fact it hasn't been proved yet, to be more precise. Here we go, for all consecutive prime numbers $p_{n}$ and $p_{n+1}$, it happens that: $$\sqrt{p_{n+1}} - \sqrt{p_{n}}< 1$$

1. The first attempt

Let's start with an analogy, here is an inequality $p_{n+1} < 2\cdot p_{n}$ which is a direct result from Bertrand's postulate, proved by Chebyshev. As a result of this inequality, we have: $$0 < ln(p_{n+1}) - ln(p_{n}) < ln(2) < 1$$ But what is the relationship between natural logarithm and square root functions?

Well, let's have a look at the following function: $f_{1}(x)=\sqrt{x} - ln(x)$. First derivative of this function is ${f_{1}}'(x) = \frac{1}{2\cdot \sqrt{x}} - \frac{1}{x}=\frac{1}{x}\cdot \left ( \frac{\sqrt{x}}{2} -1\right )\geq 0$, for $\forall x\geq 4$. This means that $f_{1}(x)$ is ascending for $\forall x\geq 4$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (because $p_{3}=5$) $\Rightarrow f_{1}(p_{n}) \leq f_{1}(p_{n+1})$ or $$\sqrt{p_{n}} - ln(p_{n}) \leq \sqrt{p_{n+1}} - ln(p_{n+1})$$ Finally: $$0< ln(p_{n+1}) - ln(p_{n}) \leq \sqrt{p_{n+1}} - \sqrt{p_{n}}, \forall n\geq 3$$ As we can see, the analogy isn't of any use really, though we have a nice inequality.

2. The second attempt

Let's have a look at another function: $f_{2}(x)=\frac{x}{ln(x)} - \sqrt{x}$. Its first derivative is ${f_{2}}'(x)=\frac{ln(x)-1}{(ln(x))^{2}}-\frac{1}{2\cdot \sqrt{x}}=\frac{1}{2\cdot \sqrt{x}\cdot (ln(x))^{2}}\cdot \left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )$.

For the first term we have: $\frac{1}{2\cdot \sqrt{x}\cdot (ln(x))^{2}}> 0$, for $\forall x> 0$.

Let's check the second term: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )=$ $\left (-x+2\cdot \sqrt{x}\cdot ln(x)-(ln(x))^{2}-2\cdot \sqrt{x}+x \right )=$ $\left [ -\left ( x-2\cdot \sqrt{x}\cdot ln(x)+(ln(x))^{2} \right ) +\left ( 1- 2\cdot \sqrt{x}+x\right )-1\right ]=$ $\left [ \left ( \sqrt{x}-1\right )^{2}-\left ( \sqrt{x}-ln(x) \right )^{2} -1\right ]$ and we are not done yet. Using $a^{2}-b^{2}=(a-b)\cdot (a+b)$, we have: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )=$ $\left [ \left ( ln(x)-1 \right )\cdot \left ( \sqrt{x}-1+\sqrt{x}-ln(x) \right )-1 \right ]$.

What we have so far:

• $ln(x)-1 \geq 1$, for $\forall x \geq e^{2}$
• $\sqrt{x}-1 \geq 1$, for $\forall x \geq 4$
• $\sqrt{x}-ln(x)>0$, for $\forall x \geq 4$, this is, by the way, $f_{1}(x)$, so $f_{1}(x)\geq f_{1}(4)>0$
Altogether: $\left ( 2\cdot \sqrt{x}\cdot ln(x)-2\cdot \sqrt{x}-(ln(x))^{2} \right )\geq 0$, for $\forall x\geq e^{2}$.

This means ${f_{2}}'(x)\geq 0$ and $f_{2}(x)$ is ascending, for $\forall x\geq e^{2}$. As a result, for $\forall p_{n}\leq p_{n+1}$, $n\geqslant 3$ (the cases for $p_{3}=5$, $p_{4}=7$ and $p_{5}=11$ can be verified with a calculator) $\Rightarrow f_{2}(p_{n}) \leq f_{2}(p_{n+1})$ or $$\frac{p_{n}}{ln(p_{n})} - \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \sqrt{p_{n+1}}$$ Final result is (let's note it as (2)): $$\sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}, \forall n\geq 3$$

2.1 A negative result of the second attempt

It is worth mentioning that function $\frac{x}{ln(x)}$ has a special role in the number theory. According to the Prime Number Theorem: $\displaystyle\smash{\lim_{x \to \infty }}\tfrac{\pi (x)}{x/ln(x)}=1$, where $\pi (x)$ is the prime counting function.

Obviously, $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n})}{p_{n}/ln(p_{n})}=1$ and $\displaystyle\smash{\lim_{n \to \infty }}\tfrac{\pi (p_{n+1})}{p_{n+1}/ln(p_{n+1})}=1$ (as sub-sequences).

Also $\pi (p_{n})=n$ and $\pi (p_{n+1})-\pi (p_{n})=1$.

If we put all these together, does it mean that $\displaystyle\smash{\lim_{n \to \infty }} \left ( \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})} \right )=1$?

Nope, it doesn't, check this link for more details.

2.2 A positive result of the second attempt

According to the following article, in 2005 it was proved that $\displaystyle\smash{\lim_{n \to \infty }}inf \frac{g_{n}}{ln(p_{n})}=0$, where $g_{n}=p_{n+1}-p_{n}$ or the n-th gap.

It is also obvious that $\frac{p_{n+1}}{ln(p_{n+1})} < \frac{p_{n+1}}{ln(p_{n})}$ (because $p_{n} < p_{n+1}$ and $ln(p_{n}) < ln(p_{n+1})$). As a result: $$\sqrt{p_{n+1}}- \sqrt{p_{n}}\leq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}\leq \frac{g_{n}}{ln(p_{n})}, \forall n\geq 3$$ Or $$\displaystyle\smash{\lim_{n \to \infty }}inf\left ( \sqrt{p_{n+1}}- \sqrt{p_{n}} \right )=0$$ This means that Andrica's conjecture is true for an infinity pairs of $p_{n}$ and $p_{n+1}$. It doesn't prove the conjecture though, which states "it is true for all $p_{n}$ and $p_{n+1}$"

3. The third attempt

How about the following function $f_{3}(x)=\pi (x) - \frac{x}{ln(x)}$? Well, for this case I used a little Python program, as per below:

import math
import matplotlib.pyplot as plt

cache_prime = {}
cache_prime[1] = False
cache_prime[2] = True
cache_prime[3] = True

def is_prime(n):
if n in cache_prime:
return cache_prime[n]

print "calculate",n
l = int(math.sqrt(n)) + 1
for i in xrange(2,l):
if (n % i) == 0:
cache_prime[n] = False
return False
cache_prime[n] = True
return True

def p(x):
ret = 0
i = 2
while i <= x:
if is_prime(i):
ret += 1
i += 1
return ret

def f(x):
return p(x) - x/math.log(x)
#return p(x) - math.sqrt(x)

START = 0
N = 40000
step = 0.25
x = []
y = []
x1 = []
y1 = []

n = START + 1.5
for i in xrange(START, N):
val = f(n)
x.append(n)
y.append(val)

n_n = int(n)
if (abs(n_n - n) <= 0.0001) and is_prime(n_n):
x1.append(n_n)
y1.append(val)

n += step

plt.plot(x, y)
plt.plot(x1, y1)
plt.show()

First of all, $f_{3}(23)=1.66463325521 > f_{3}(29)=1.38774807317$. So, $f_{3}(x)$ is not ascending. The general tendency of $f_{3}(x)$ seems to be ascending though, according to this graphic (click to enlarge):
At least, for the areas where the function is ascending for consecutive primes (update the program to plot just plt.plot(x1, y1), i.e. primes and values of the function for the prime arguments), Andrica's conjecture is true, because if $$\pi (p_{n+1}) - \frac{p_{n+1}}{ln(p_{n+1})} \geq \pi (p_{n}) - \frac{p_{n}}{ln(p_{n})}$$ then (also consider (2)) $$1=\pi (p_{n+1}) - \pi (p_{n}) \geq \frac{p_{n+1}}{ln(p_{n+1})} - \frac{p_{n}}{ln(p_{n})}$$Still, this is not the proof.

4. What's next?

Well, probably the next logical thing is to analyse the function $f_{4}(x)=\pi (x) - \sqrt{x}$. At least it seems to be ascending for prime arguments.

But the work is still in progress...