7
$\begingroup$

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:

enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ahmad May 31 '17 at 21:17
  • 1
    $\begingroup$ @Ahmad You are absolutely right! I made a (bad) typo, I will fix this immediately. Thanks for the correction $\endgroup$ – E. Joseph May 31 '17 at 21:25
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – E. Joseph May 31 '17 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.