# About numbers which have very few little divisors

I will provide some context first, you can skip directly to the question down there if you are in a hurry.

Context.

I am interested in numbers which have very few little divisors. Let's denote by $\mathbb P$ the set of all prime numbers. I was searching for numbers $n$ which satisfies:

$$\forall p\in \mathbb P,\quad p\leqslant \sqrt n\implies n\equiv 1\pmod p.$$

We can prove that this condition will be impossible to satisfy for $n\geqslant 32$.

So I started to search for numbers satisfying:

$$\forall p\in \mathbb P,\quad p\leqslant \log n\implies n\equiv 1\pmod p.$$

If found a bunch of them:

$$2,3,5,7,11,13,17,19,31,37\ldots,8191,8821,9241,9661,9871\ldots$$

But again, since

$$\prod_{\substack p\in\mathbb P\\p\leqslant n} p \sim n^ne^n$$

I saw that this list will eventually end, which can be illustrated by these two lines crossing:

This is to avoid all these issues that I have chosen the following definition (to give chance to this list not to stop in particular).

At first, I tried to find an optimal condition, but it would end with finding a function $\phi$ such that

$$\Gamma\left(\frac{\phi(n)}{\log\phi(n)}\right)e^{\frac{\phi(n)}{\log\phi(n)}\log\log\frac{\phi(n)}{\log\phi(n)}-\mathrm{Li}\left(\frac{\phi(n)}{\log\phi(n)}\right)}\leqslant n$$

for all $n$, which seemed impossible to solve.

The question.

Let's define a harsh number as a number $n$ such that

$$\forall p\in \mathbb P,\quad F (p)\leqslant n\implies n\equiv 1\pmod p$$

where

$$F(x)=\prod_{\substack p\in\mathbb P\\p\leqslant x} p.$$

We can find the first harsh numbers up to $10^8$:

$$1,3,5,7,13,19,\ldots,6931,9241,11551,\ldots,60061,90091,120121,\ldots,510511,1021021,1531531,\ldots,9189181,9699691,\ldots$$

Does there exist infinitely many harsh numbers? (I think it does)

Can we find a formula wich would give the $n$-th harsh number?

• The intro is very good, but i did not get the definition of harsh numbers, it seemed to me that if the function is bigger than the number itself then its would certainly not fit the condition. – Ahmad May 31 '17 at 21:17
• @Ahmad You are absolutely right! I made a (bad) typo, I will fix this immediately. Thanks for the correction – E. Joseph May 31 '17 at 21:25

Assuming I understand your question properly, I believe the product of the first $n$ primes plus $1$ would give a harsh number (let's call it $N$). The only primes with $F(p)\leq N$ would be the first $n$ primes, and they each divide $N-1$.

For the second part, let $P_n$ be the product of the first $n$ primes (or we could let it be $F(p_n)$). Given a number $N$, define $n$ such that $P_n < N < P_{n+1}$. We must have that, since $F(p_k)<N$ for all $1\leq k \leq N$, $P_n|N-1$ (see that this is equivalent to it being harsh). So,

$$N=jP_n+1$$

for some $1\leq j < p_{n+1}$. Thus, the harsh numbers look like this:

$$\cdots,P_n+1,2P_n+1,\cdots,(p_{n+1}-1)P_n+1,P_{n+1}+1,2P_{n+1}+1,\cdots$$

It's hard to index them without knowing the first $n$ primes themselves, but knowing them it's relatively straightforward.

O.K. we can start the answer by seeing that the numbers $n=1+\prod \limits_{p_i \leq f(n)} p_i$ fit your condition, now we just need to see for what functions its true.

Easy to see that if $Max(p_i) \geq n$ then $n$ can not hold true to your condition so it means that $f(n) \geq n$ will give no valid $n$.(Actually we can reduce this to $f(n) \geq \frac{n}{2}$ by same reasoning.).

We know that $p_i \approx i \ln i$ and we want that $\prod \limits_{i=2}^{p} i \ln i \approx n$ and find $p$ using $n$ will give the proper function (An approximation to the function).

Now $\prod \limits_{i=2}^{p} i \ln i \approx e^{\sum\limits_{i=2}^{p} i \ln i}\approx e^{\int\limits_{i=2}^{p} i \ln i}= \frac{1}{4} e^{\frac{1}{4} p^2 (2 \log (p)-1)+1}\approx n$ solving for $p$(which is a symbol for the maximum prime) we get that $p=e^{\frac{1}{2} \left(W\left(\frac{4 (\log (4 n)-1)}{e}\right)+1\right)}$ and since $W(x) \approx \ln x + \ln \ln x$ where $W(x)$ is (Lambert W function) we can approximate to $p \approx \frac{2 \sqrt{\log (4 n)-1}}{\sqrt{\log (4 (\log (4 n)-1))-1}} \approx \frac{2\sqrt{\ln n}}{\sqrt{\ln \ln n}}.$

So when $f(n) \leq \frac{2\sqrt{\ln n}}{\sqrt{\ln \ln n}}$ we will have Infinitely many solutions

For $\frac{2\sqrt{\ln n}}{\sqrt{\ln \ln n}} << f(n) << n$ we could only have finitely many solutions as for your examples $f(n)=\sqrt{n},\ln n$

• Thank you so much for this detailed answer! When I did some calculation of my own, I found results involving Lambert function, but I didn't manage in using it. The majorant you found for $f(n)$ is great! – E. Joseph May 31 '17 at 22:09