Question

Prime thing. ;)

Answer 1

\(\pi(n)\) is the prime counting function, it just tells you how many prime numbers are less than or equal to n. For example,
\[\pi(7)=4\]
since there are 4 primes less than or equal to 7, which are 2, 3, 5, and 7.

Prove for all k there are infinitely many cases such that:

\[\pi(n)=\pi(n+k)\]

So for instance, one of the times this happens for k=2 is:

\[\pi(14) = \pi(16)\]

Answer 2

TOTIENT FUNCTION

Answer 3

its a bold strategy idk tho

Answer 4

Hint:

\[\pi(n)=\pi(n+k)\]

This is the same as saying there is a sequence of k-1 consecutive composite numbers.

Answer 5

Well, if that hint tell us that.. if we have:

n,n+1,n+2,......,n+k

Answer 6

Oh, hang on! Does it say k-1 consecutive composite? k-1?

Answer 7

I think it should be k tho

Answer 8

becauce either only the n is prime or the n+k is prime but not both

Answer 9

So basically we have to prove that for any k. We can always find k consecutive composite numbers...

Answer 10

Yup :D

Answer 11

So its like this: We first fix our k and then we should be able to find:
pi(x1) = pi(x1+k)
pi(x2) = pi(x2+k)
and so on...
pi(xn) = p(xn+k)

Answer 12

Those x's we can find infinitely many times.
Now, when I first saw the problem, I was thinking we should do it like this so we start by fixing our k and then assume to the contrary that it can't be done infinitely many times

So that means, there is a largest number say big N so that pi(N)=pi(N+k) ... we then just have to produce another number, bigger than N say M such that pi(M)=pi(M+k) and that will give us a contradiction (since we assumed that N is the largest) which will prove the statement.

Answer 13

Let me first see if we can produce such a number M larger than N. We can produce a bigger number this way by multiplying 1*2*3*4*...*N that is obviously way larger than N.

Now, if we choose this to be our M there will be a slight problem because the next number after this is: 1*2*3*4...*N+1 but we cannot guarantee that this will be composite - its possible that is it prime which will ruin the pi function it will be increased by 1, do you see what I'm saying, kai?

Answer 14

That's an interesting way to think of it, I like that and this is why I like to make questions to hear how other people approach this so that I'm sorta like technically stealing some of your cleverness heheh.

Answer 15

Yeah I see exactly what you're saying, you're actually pretty close in a way to my proof of this, but in a strange way.

Answer 16

but what about: the next number after that, the: 1*2*3...*N + 2, is the prime composite?

Answer 17

:)

Answer 18

is it prime or composite, which one? kai kai

Answer 19

Surely you can factor a 2 out, right?

Answer 20

yeah !

Answer 21

2 is a common factor

Answer 22

hence composite, right?

Answer 23

I can't think of any prime numbers that are divisible by two numbers, so yeah, composite for sure.

Answer 24

Lets investigate further, what about the next number after that the: 1*2*3*..*N + 3 prime or composite?

Answer 25

Yeah, this is essentially the proof I had in mind that you've come to. :P

Answer 26

Ya, the factorial thing is to prove a softer statement: for any given \(n\), we can find a subset of \(n\) consecutive numbers where all of them are composite. All numbers from \((n+1)! + 2\) to \((n+1)! + n+1\) are composite, right? But as I understand, for us to have a prime gap of length \(n\), we must have the initial and final thing to be prime.

Answer 27

Luckily the question I asked is not looking for prime gaps. :P

Answer 28

So there's absolutely no way we can prove your conjecture using this. :\

Answer 29

Oh, then we can just consider further factorials... \((n+2)! + 2\) through \((n+2)! + n+1\). And \( (n+3)! + 2\) to \((n+3)! + n+1\).

Answer 30

\[\pi(22)=\pi(26)\] is one of infinitely many cases for k=4

Answer 31

So that is also composite, since 3 is a common factor and that goes on and on so to summarize, we have established that: starting with:
1*2*3*4*...*N + 2
1*2*3*4*...*N + 3 and 1*2*3*4*...*N + 4
and so on
are all composite but we need k of them so we say that up to: 1*2*3*4*...*N (k+1) are all composite and that pretty much proves it

Answer 32

We just have to choose our M to be: 1*2*3*4...*N+1 and it will follow that: Pi(M)=P(M+K)

Answer 33

Yup, you can pick N to be arbitrarily large, and because of that all the other choices of k are subsets of that, so you get the smaller cases of k for free really.

Answer 34

**(This is the complete proof which is a proof by contradiction, I'm just summarizing it so it's all together)** :)

π (n) = π(n+k)

Let k be a positive integer.
Suppose N is the larger number so that π(N) = π(N+K)
We have to show that there is a number larger than N, say M, so that: π(M) = π(M+K)

Let M = 2*3*4*…*N+1
Note that
M + 1 = 2*3*4*…*N + 2 is composite (since 2 is a factor)
M+2 = 2*3*4*…*N+3 is composite (since 3 is a factor)
*
* and so on up to
*

M+K = 2*3*4…N+(K+1) (this is possible since N is arbitrarily large, and so K+1 < N)

Therefore, we have produced a number bigger than N that satisfies the equation, hence we have a contradiction.