Hard number theory problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Hard number theory problem

G H J

Reveal topic tags

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Iran 2002

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#1 h Apr 9, 2004, 8:52 AM • 2 Y

Y by Adventure10, Mango247

$\pi(n)$ is the number of primes that are not bigger than $n$ . For $n=2,3,4,6,8,33,\dots$ we have $\pi(n)|n$ . Does exist infinitely many integers $n$ that $\pi(n)|n$ ?

This post has been edited 1 time. Last edited by Omid Hatami, Aug 8, 2006, 4:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#2 h Apr 12, 2004, 7:30 AM • 5 Y

Y by Adventure10, Mango247, MS_asdfgzxcvb, and 2 other users

Here's an argument which makes me think the answer is "yes":

Assume there is an N s.t. for all n>=N \pi(n) doesn't divide n. We reach such an n and then we start increasing n with step 1. We can see that if \pi(n+\pi(n))=\pi(n) then when we increase n to n+\pi(n) we will eventually reach a number which is 0(mod \pi(n)), so the answer to the initial quastion would be "yes" in this case. We have assumed that the answer is "no", so there must be an N s.t. \pi(n+\pi(n))>\pi(n) for all n>=N. This can be translated to \pi(p<sub>n</sub>+n)>n or, in other "words", p<sub>n+1</sub><=p<sub>n</sub>+n for all sufficiently large n (n>=N, for example). This doesn't yield an obvious contradiction, but it looks too strong. If it were true, we would have known about it.

This isn't a proof, but it seems a good enough argument to show us what we should prove. I'm not convinced, however. What are your opinions?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5526 posts

harazi

#3 h Apr 17, 2004, 2:29 PM • 5 Y

Y by Adventure10, Mango247, kiyoras_2001, and 2 other users

The following is not my solution, but it surely is memorable:
We prove that for any m>=2 we can find n such that mpi(n)=n. Take m>1. Since pi(mk)/mk has limit 0 when k tends to infinity, there is a maximal k such that pi(mk)/mk>=1/m ( k=1 verifies this inequality). If we have equality, we are done. Otherwise, pi(mk)>k. Since k is maximal, we have pi(mk+m)/(mk+m)<1/m and thus k>=pi(km+m)>=pi(km)>k, false.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7849 posts

#4 h Apr 17, 2004, 4:58 PM • 2 Y

Y by Adventure10, Mango247

This is just beautiful! I did struggle on this problem for a day or so, and the proof was 3-lines long! Where did you find this?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5526 posts

harazi

#5 h Apr 17, 2004, 4:59 PM • 2 Y

Y by Adventure10, Mango247

I found it in one of my materials and I just love it.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4464 posts

Myth

#6 h Apr 17, 2004, 5:17 PM • 2 Y

Y by Adventure10, Mango247

Excellent!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

390 posts

#7 h Apr 23, 2004, 12:44 PM • 2 Y

Y by Adventure10, Mango247

Not solution , just a small remark :

We can replace the function $\pi\left(n\right)$ by any function $f: \mathbb{N}\to\mathbb{Z}^{+}$ which is increasing and satisfies $f\left(n\right)=O\left(n\right)$ when $n$ tends to infinity.

For example, $f\left(n\right)=c$ for a constant positive integer $c$ satisfies the requirement of the problem.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

736 posts

#8 h Dec 20, 2008, 6:27 AM • 3 Y

Y by atharvatekawade, Adventure10, Mango247

The following is almost the same idea as the above solution (post #3). But I feel it is more revealing (easier to visualize).

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

233 posts

#9 h Dec 21, 2008, 5:52 PM • 2 Y

Y by Adventure10, Mango247

Akashnil wrote:

To visualize this: consider the graph of $f(x)$ and $g(x) = x$ ( $g: \mathbb N\to \mathbb N$ ). At some point $f$ is above $g$ and after some interval it is below $g$ . together with $f$ non-decreasing, $f$ and $g$ must intersect in that interval.

Excuse me,
$f(x)$ and $g(x) = x$ ( $g: \mathbb N\to \mathbb N$ ) are not continuous functions. so they may not intersect. or even if continuous,may not intersect at an integral point.
am i right ?

:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1275 posts

#10 h Dec 22, 2008, 7:50 AM • 2 Y

Y by Adventure10, Mango247

Notice that if you consider the function $h(x) = f(x) - x$ because $f$ is non-decreasing we have the inequality
$h(x + 1) - h(x)\geq - 1$
So when $g(a) > 0$ , $g(b < 0)$ then there will be a $c\in[a,b]$ s.t. $g(c) = 0$ which proves the lemma.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

736 posts

#11 h Dec 22, 2008, 9:00 AM • 2 Y

Y by Adventure10, Mango247

ith_power wrote:

Excuse me,
$f(x)$ and $g(x) = x$ ( $g: \mathbb N\to \mathbb N$ ) are not continuous functions. so they may not intersect. or even if continuous,may not intersect at an integral point.
am i right ?

:

Note that what I said was "To visualize this" . It wasn't a rigorous proof. The functions aren't continuous, they aren't even defined on the reals.

If you think of their graphs as dots on integral points their will be a slanted wall of dots of $g(x)$ and $f(x)$ begins above it and it can't jump below the wall because it is increasing.

To prove the lemma rigorously see post #10

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1479 posts

#12 h Oct 16, 2013, 4:10 PM • 2 Y

Y by Adventure10, Mango247

Today I was trying this problem and observed some stuffs writting a "Haskell programme". Now, let $f(x)=x-k\pi(x)$ where $k>2$ some natural number. So $f(2)<0$ . Now $f(x+1)=f(x)+1$ whenever $x+1$ is prime otherwise $f(x+1)=f(x)+1-k$ and so $f(x+1)-f(x)+1$ but also $f(x)\sim x(1-\frac{k}{log x}) >0$ so after some stage we must have that $f(x)>0$ so if there doesn't exist a $x$ with $f(x)=0$ then exist some $x$ so that $f(x)<0$ and $f(x+1)>0$ and so $f(x+1)-f(x)>2$ . So that's the contradiction. So for any $k$ we get some $x$ so that $f(x)=0$ and so there must be infinitely many $x$ so that $\pi(x)|x$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

167 posts

#13 h Oct 23, 2024, 12:19 PM

Y by

pluricomplex wrote:

Not solution , just a small remark :

We can replace the function $\pi\left(n\right)$ by any function $f: \mathbb{N}\to\mathbb{Z}^{+}$ which is increasing and satisfies $f\left(n\right)=O\left(n\right)$ when $n$ tends to infinity.

For example, $f\left(n\right)=c$ for a constant positive integer $c$ satisfies the requirement of the problem.

Not big $O$ , it should be small $o$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

220 posts

kingu

#14 h Oct 23, 2024, 12:50 PM

Y by

Clean and Conceptual

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1299 posts

#15 h Oct 23, 2024, 1:17 PM • 1 Y

Y by MihaiT

Cool NT+ Analysis Problem

It suffice to show the below claim:
Claim: For every $m \ge 2$ , we can find $n \ge 2$ such that: $m \pi(n) = n$ .
Proof: Let $m > 1$ . Consider $f(k) = \frac{\pi(mk)}{mk}$ . Notice that: $\lim_{k \to \infty} f(k) \to 0$ . Thus, let $c$ denote the maximum value of $k$ such that: $\frac{\pi(mc)}{mc} \ge \frac{1}{m}$ (we can find such maximum value due to the limit $\lim_{k \to \infty} f(k) \to 0$ ). If $\pi(mc) = c$ then we are done. Else $\pi(mc) > c$ : Notice that: $\frac{\pi(mc+m)}{mc+m} < \frac{1}{m}$ due to the maximality of $k$ to be $c$ , which implies: $c \ge \pi(mc+m) \ge \pi(mc) > c$ which results to a contradiction. Thus, we have $\pi(mc) = c$ , and the claim is true.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3177 posts

#16 h Nov 24, 2024, 1:46 PM

Y by

We prove that for any positive integer $k\ge 2$ , there exists a positive integer $n$ satisfying $f(n)=k\pi(n)-n.$
Choose a number $n$ so that $f(n)<<0$ (which is possible by the Prime Number Theorem). As we decrease $n$ , we have $f(n-1)=f(n)+1$ or $f(n-1)=f(n)-(k-1).$ But we always have $f(2)\ge 0$ , so $f(n)$ will not stay negative forever as $n$ decreases. Therefore, $f(n)$ will eventually make the cross from $<0$ to $\ge 0$ as $n$ decreases. But $f(n)$ can never jump up by more than $1$ number, so there exists a value $n$ for which $f(n)=0$ , done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

97 posts

#17 h Saturday at 11:09 AM

Y by

Infact we can $\pi(n)$ by any non decreasing function $f(n)\in o(n)$ and there would be infinitely many values $k$ such that $f(k)\mid k$ .

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a