1

Let $N$ be a big integer. Let $p$ be a prime number. Is there a formula to count how many number less than $N$ such that they are divisible by $p$ and not divisible by any prime less than $p$.

For example,

$p = 3$, one has
$$\left\lfloor\frac{N}{3}\right\rfloor - \left\lfloor\frac{N}{6}\right\rfloor$$ $p = 5$, one has $$\left\lfloor\frac{N}{5}\right\rfloor - \left\lfloor\frac{N}{10}\right\rfloor - \left\lfloor\frac{N}{15}\right\rfloor + \left\lfloor\frac{N}{30}\right\rfloor$$

But, I don't know when $p$ arise big. For example, $N= 10^{15}$ and $p$ near to $\left\lfloor\sqrt{N}\right\rfloor$.

EDIT: I don't want know ALL number which is divisible by $p$, but only is divisible either by $p$ or by primes which is greater than $p$.

GAVD
  • 7,296
  • 1
  • 16
  • 30
  • An answer to this question is deeply related to legendre conjecture which is unsolved. – mahdokht Jul 23 '15 at 08:56
  • @mahdokht: Do you know any article or theorem/lemma about this problem? Thanks in advance. – GAVD Jul 23 '15 at 08:58
  • No,If you can show this number is less than N,you have proved an important unsolved conjecture. – mahdokht Jul 23 '15 at 09:14
  • If $p$ is close to $\sqrt{N}$, then apart from $p$ itself, the numbers are of the form $p\cdot q$ where $q$ is a prime $p \leqslant q \leqslant \frac{N}{p}$, which gives a count of $1 + \pi(N/p) - (\pi(p)-1) = 2+\pi(N/p) - \pi(p)$. That is if "close to $\sqrt{N}$" means $> \sqrt[3]{N}$. – Daniel Fischer Jul 26 '15 at 08:35

2 Answers2

0

Correct me if I'm wrong but,

Only multiples of p are divisible by p: p, 2p, 3p, 4p etc. However, all these numbers are also divisible by 2, 3, 4, etc. With the exceptions of: p, p^2, p^3 etc.

We know that p, p^2, p^3 etc are not divisible by anything else because p is prime.

Therefore, the answer to your question is how many times we can multiply p by itself and still have the result be lesser than or equal to N.

That's a log: log_p N. and in case we get a fractional part, we can cut it off.

So basically: floor(log_p N)

Amadeus
  • 1
  • 1
0

$n-\displaystyle\sum_p\bigg\lfloor\frac np\bigg\rfloor+\sum_{p<q}\bigg\lfloor\frac n{pq}\bigg\rfloor,~$ where p and q represent the primes lesser than the given value.

Lucian
  • 48,334
  • 2
  • 83
  • 154
  • Sorry, but it is not true. – GAVD Jul 23 '15 at 15:56
  • @GAVD: A certain famous Jack Nicholson line comes here to mind. :-$)$ If you want the formula to be truer, than you will have to add in extra terms, thereby making it more complicated. – Lucian Jul 23 '15 at 15:59
  • In fact, I have a formula $$\lfloor \frac{N}{p} \rfloor - \sum_{p_1 is prime, p_1 <p} \lfloor \frac{N}{p_1} \rfloor + \sum_{p_1,p_2 are primes, p_i < p}\lfloor \frac{N}{p_1p_2}\rfloor + \dots + (-1)^i \sum_{p_i is prime, p_i <p} \lfloor\frac{N}{p_1\dots p_i}\rfloor$$. – GAVD Jul 23 '15 at 16:06
  • @GAVD: And I assume you are interested in finding a nicer one... Unfortunately, when it comes to primes there are no meaningful formulas which are both short and precise. The exact ones are as true as they are meaningless, and the shorter ones have sometimes great absolute error, even if their relative error is small. I'm afraid I don't have any good news to give you. – Lucian Jul 23 '15 at 19:54