Classifying all numbers $n$ with the property that if $p$ is a prime, then $p \mid n \iff p-1 \mid n$

If a number $n$ has the property that if $p$ is a prime, then $p \mid n \iff p-1 \mid n$, we call $n$ a nice number for brevity.

A recent question on MSE (edit: now deleted) asks to prove that $1806$ is the only squarefree nice number. (That question gives no context and looks like a contest problem, and was therefore ill-received, but the actual question is a nice puzzle.) After solving it, I relayed the question to some friends, but initially I accidentally forgot the squarefree condition. This led me to wondering about nice numbers that are not necessarily squarefree.

A fairly simple argument proves that all nice numbers must be multiples of $1806$, and this is the first step towards solving the puzzle as well. (Edit: namely, for any nice $n$, we have $2-1 \mid n$, so $2 \mid n$; but then also $3 \mid n$. It follows that $6 \mid n$, and therefore $7 \mid n$. Then $2 \cdot 3 \cdot 6 = 42 \mid n$, so $43 \mid n$, and we obtain that $2 \cdot 3 \cdot 6 \cdot 43 = 1806 \mid n$ -- but $1807$ is not prime, so the argument ends here.)

However, there are more examples that are not squarefree:

• $1806 = 2 \times 3 \times 7 \times 43$.
• $12642 = 2 \times 3 \times 7^2 \times 43$.
• $88494 = 2 \times 3 \times 7^3 \times 43$.
• $6030842622 = 2 \times 3 \times 7 \times 43^2 \times 77659$.

These are all examples up to $2 \times 10^{10}$ (via computer search). The sequence is not currently listed on OEIS. The sequence has now been listed, at A345765.

My question is: can we classify all nice numbers? Are there only four? Are there more? Infinitely many?

Solution 1:

Summary

• This is not a complete answer, but I think it's about as far as is both feasible and interesting.
• I've started calling these numbers saturated rather than nice, and will do so for the rest of this answer.
• There are a lot more saturated numbers than listed in the question and comments, but they are nonetheless scarce: there are 126 below $10^{1000}$.
• I now conjecture that there are infinitely many.

Downward/upward saturated

If $n$ has the property that for any prime $p$, $$ p \mid n \implies p-1 \mid n, $$ we call it downward saturated. (This is equivalent to: $\lambda(n) \mid n$, where $\lambda$ is the Carmichael function. This sequence is A124240 on OEIS.) If it has the property that for any prime $p$, $$ p - 1 \mid n \implies p \mid n $$ we call it upward saturated. Clearly $n$ is saturated if and only if it is both downward and upward saturated.

Suppose $n$ is already downward saturated. Then we can define $$ n' = n \times \prod \{p\text{ prime} \mid p \not \mid n, (p-1) \mid n\}. $$

Note that:

• $n \mid n'$;
• $n'$ is still downward saturated: the primes $p$ that we added to $n'$ by construction have $p-1 \mid n$, and thus $p-1 \mid n'$;
• if $n \mid m$ and $m$ is saturated, then $n' \mid m$;
• in particular, $n = n'$ if and only if $n$ is saturated.

This gives a recipe for generating saturated numbers up to a cutoff $C$: start with any downward saturated number $n$, and define the sequence $n, n', n'', \ldots$. If it eventually stabilizes, you have found a saturated number. If the sequence eventually exceeds $C$, then $n$ is not the divisor of any saturated number below $C$.

Note that the sequence $n, n', n'', \ldots$ typically grows very fast when it does not immediately stabilize: this allows us to quickly rule out $n$ and search up to quite large cutoffs $C$.

It remains to be seen how we can find the right 'seeds' $n$ to start running this generation algorithm.

Bases and saturation primes

For a fixed cutoff $C$, the (C-)saturation primes are those primes which occur as a prime factor of a saturated number below $C$. Note that we are currently unable to rule out any prime factor from being a saturation prime for some $C$.

If we know what the saturation primes are for a cutoff $C$, say $p_1, \ldots, p_k$, we are essentially done: we simply generate all numbers of the form $p_1^{e_1} \cdots p_k^{e_k}$ that are below $C$, check whether they are saturated, and we are done. Thus we need a procedure which finds these primes for us.

Suppose we have found a partial list of the saturation primes $p_1, \ldots, p_l$ (may be empty, but we may as well initialize with $2, 3, 7, 43$), and there is a saturated number $K$ which is divided by a different prime. Let $q$ be the least prime divisor of $K$ which is not yet among our list. Then the prime divisors of $q-1$ are among $p_1, \ldots, p_l$.

This means we have two strikes with one stone: we will enumerate all products of powers of $p_1, \ldots, p_l$ that are below the cutoff. I call such numbers bases. For each basis $n$, we construct the sequence $n, n', n'', \ldots$ as above, until it exceeds the cutoff or until it saturates. Now note that $q - 1$ is a basis itself: this means it must be part of our enumeration, and through it some saturated number $s$ such that $q-1 \mid s \mid K$. We can then add $q$ to our list of primes, and continue our search.

What remains are just tricks to speed up the computation:

• Short-circuit past bases that are not downward saturated.
• If the saturation sequence of a basis exceeds the cutoff, then so does the saturation sequence of each multiple of that basis, so we short-circuit past these as well.
• Rather than using the sequence $n, n', n'', \ldots$ as above, we only add one prime at a time, to avoid creating gargatuan numbers with an infeasible number of divisors.
• Keep track of each large number's factorization, so that we never have to factorize.

Results

I have put my code implementing the above on Github: https://github.com/mjdv/saturated-numbers

With that code, I have listed all saturated numbers up to $10^{1000}$: https://pastebin.com/MkEfkSpY

I have also listed all saturated numbers up to $10^{1500}$, under the assumption that $7^4$ does not divide a saturated number below $10^{1500}$ (see below): https://pastebin.com/CT7hUDXi

There are 16 saturation primes for cutoff $10^{1000}$. They are $$ 2, 3, 7, 43, 77659, 21108889701347407, 5474088843701260097485589623, 5474159333397668466502066699, 14409061174110271629491692889111901658580261328754207, 12187898054314878179186265415000535659762253573563119365846458063397719, 4432982211548497951181997741316103259463454892983224005155108393681585716520...\\ 47036741930999, 5608017333924641389333679842752042439016754139199524596804923772035677581183...\\ 43740900139639, 1872705977981591020313336244505607714217889071693212286852076373413830346691...\\ 635632706249598340007, 9724040345982427116322290520909526374336288011833033457100867657726910715963...\\ 7823909035022095182893334450446173318074919, 3261106282862834686088755611243542924322840903892344944538844883173926466304...\\ 3468198518796043304218142825248440850700658152098958744500089400281673745399...\\ 0562312935495319926909431192160160253334732061914415799939878042598694784290...\\ 509218689159009145647650418769156819250302503, 3758874354521422972974642113256353902974703838722946991775778945748849417310...\\ 8680865452438274881828114249910402060654847053902299762834024507515311159860...\\ 0956871660411763936550716357782852055668471710382751800336614044465508091526...\\ 9963990635230724828608976209217399558456147493114652686096883786754935980432...\\ 41430009359. $$ Edit: here are the same primes, in a compact notation suggested by @Vepir below: the primes are numbered $p_1, \ldots, p_n$, and a vector $(e_1, \ldots, e_k)$ stands for $p_1^{e_1} \cdots p_k^{e_k} + 1$. $$ (), (1,), (1, 1), (1, 1, 1), (1, 1, 1, 2), (1, 1, 1, 9), (1, 1, 1, 3, 1, 1), (1, 1, 1, 10, 2), (1, 1, 1, 1, 10), (1, 1, 1, 1, 3, 0, 0, 0, 1), (1, 1, 1, 1, 7, 0, 0, 0, 1), (1, 1, 1, 7, 1, 1, 2), (1, 1, 1, 8, 2, 1, 2), (1, 1, 1, 1, 13, 0, 0, 0, 1), (1, 1, 1, 9, 1, 1, 2, 0, 0, 0, 0, 2), (1, 1, 1, 1, 6, 0, 0, 0, 1, 2, 1). $$ It seems to work as follows: once a saturation sequence incorporates a small prime (apart from the few special ones in this list), it will no longer stabilize. However, if it incorporates a large prime, this is fairly frequently fine: the large prime does not cause a snowball effect. In fact, the number of 'safe' large primes grows fairly steadily. Up to cutoff $10^{1500}$, there are at least 4 more. This leads me to the conjecture that there are infinitely many saturated numbers.

There are two obstructions to searching larger ranges for saturated numbers:

• For large cutoffs, it is slow to check that the saturation sequence of $2 \times 3 \times 7^4 \times 43$ diverges past the cutoff. I have checked this up to $10^{1000}$, and it takes up the majority of the computation time (hours, compared to minutes for the rest of the computation). The code linked above hard-codes this case as impossible, which allows listing all the other numbers up to $10^{1500}$ without too much patience.
• Primality checking of very large numbers is somewhat slow. This seems to be a fairly impenetrable barrier.

Some notes:

• It seems extremely unlikely that $4$ divides any saturated number (and therefore any prime of the form $4k + 1$). If it does, that saturated number must have more than 10,000 distinct prime factors.
• With the all the computational short-cuts, even for very large bounds, there are only a few-hundred paths $n, n', n'', \ldots$ that we follow through to either saturation or until they exceed the cutoff. Most are ruled out by earlier computations.