Number theory help!

Can someone give a hint for the last "deduce" part of quetion11?

Link: http://tartarus.org/gareth/maths/stuff/introductory_sheet.pdf

I know pi(2n)-pi(n)=N, where pi(n) is the number of primes
less than or equal to n. But cannot seem to finish it off!

Thanks.

Reply 1

twig

Bump!

Just realised the link states this "final part of question 11 is perhaps a bit hard". Makes me feel slightly better!

Also, I think the questions are from a first week Cambridge maths problem sheet(?). Are there any solutions to these available online?

(edited 11 years ago)

Reply 2

ghostwalker

Original post by twig

I know pi(2n)-pi(n)=N, where pi(n) is the number of primes
less than or equal to n. But cannot seem to finish it off!

Thanks.

Not an expert on this (my usual caveat), but I don't think that gets you anywhere. This is somewhat more involved.

I think given n, you need to define

N_0

, such that

Unparseable latex formula:

2^{N_0}< n\leq 2^{N_0+1}}

, then consider the number of primes in the intervals,

(1,2], (3,4], (5,8],(9,16],...,(2^{N_0},2^{N_0+1}]

But, I may be wrong.

I'm sure someone more knowledgeable will correct me, if that's the case.

(edited 11 years ago)

Reply 3

twig

Original post by ghostwalker

Not an expert on this (my usual caveat), but I don't think that gets you anywhere. This is somewhat more involved.

I think given n, you need to define

N_0

, such that

Unparseable latex formula:

2^{N_0}< n\leq 2^{N_0+1}}

, then consider the number of primes in the intervals,

(1,2], (3,4], (5,8],(9,16],...,(2^{N_0},2^{N_0+1}]

But, I may be wrong.

I'm sure someone more knowledgeable will correct me, if that's the case.

Thanks for the response.

I tried something similar to that too initially, but did not get far:

We know

\pi(n)

is the number of number of primes less than or equal to n.

Let

n\leq 2^b

. Let primes q be such that

2^i < q_i \leq 2^{i+1}

, and let

N_i

correspond to the number of

q_i

in such intervals. We have

N_i\leq \frac{(log4)2^i}{log(2^i)}=2 (\frac{2^i}{i})

from the previous part of the question.

So,

\pi(n) \leq\pi(2^b)=N_0+N_1+N_2+...+N_{b-1}\leq 2 \sum_{i=0}^{b-1}\frac{2^i}{i}=2 \sum_{i=0}^{b-1}\left (\int_{0}^{2}x^{i-1}dx \right )

Then it gets untidy trying to evaluate the sum using integration. I stopped here because the required form for

\pi(n)

seemed a lot neater.

Reply 4

jack.hadamard

Not quite sure what is going on here, but thought to contribute some input.

Maybe the intention is to write it as

\displaystyle \pi(n) \leq N + \pi(n/2) \leq \frac{an}{\ln(n)} + \frac{a(n/2)}{\ln(n/2)} + \pi(n/4) ...

and then repeating this to show that eventually such a constant exists for large

n

.

Otherwise, you can induct

\displaystyle \pi(2^k) \leq 3\cdot\frac{2^k}{k}

and use

\displaystyle \frac{k}{\ln(k)} \leq \frac{2^k}{k}

for

k \geq 4

Reply 5

Vadevalor

Lol i cant continue after question one the MOD part.. Havent learnt such complex stuff yet 0.0

This was posted from The Student Room's iPhone/iPad A

Quick Reply

Latest

Articles for you

What is an LLM and how could it benefit your career?

How to revise for GCSE Psychology exams: AQA explains what to do

Calculating Ucas points based on predicted grades

Personal statement secrets – universities reveal all

Number theory help!

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you