1
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ An answer to this question is deeply related to legendre conjecture which is unsolved. $\endgroup$
    – mahdokht
    Jul 23, 2015 at 8:56
  • $\begingroup$ @mahdokht: Do you know any article or theorem/lemma about this problem? Thanks in advance. $\endgroup$
    – GAVD
    Jul 23, 2015 at 8:58
  • $\begingroup$ No,If you can show this number is less than N,you have proved an important unsolved conjecture. $\endgroup$
    – mahdokht
    Jul 23, 2015 at 9:14
  • $\begingroup$ 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}$. $\endgroup$ Jul 26, 2015 at 8:35

2 Answers 2

0
$\begingroup$

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)

$\endgroup$
3
  • 1
    $\begingroup$ For example, $p=5$, you must count $5$, $25$, $35 = 5*7$, $55 = 5*11$, etc not only $5^k$. Is it clear? $\endgroup$
    – GAVD
    Jul 23, 2015 at 9:04
  • $\begingroup$ that's not what he wrote. $\endgroup$
    – Amadeus
    Jul 23, 2015 at 9:06
  • $\begingroup$ oh I didn't read the edit part. $\endgroup$
    – Amadeus
    Jul 23, 2015 at 9:06
0
$\begingroup$

$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.

$\endgroup$
4
  • $\begingroup$ Sorry, but it is not true. $\endgroup$
    – GAVD
    Jul 23, 2015 at 15:56
  • $\begingroup$ @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. $\endgroup$
    – Lucian
    Jul 23, 2015 at 15:59
  • $\begingroup$ 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$$. $\endgroup$
    – GAVD
    Jul 23, 2015 at 16:06
  • $\begingroup$ @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. $\endgroup$
    – Lucian
    Jul 23, 2015 at 19:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .