# Ratios of numbers of distinct prime factors in successive numbers: is every n:1 ratio realizable by a composite number?

Let $$\omega(n)$$ refer to the number of distinct prime factors of $$n$$.

I'm curious about what values of $$\frac{\omega(n-1)}{\omega(n)}$$ (which I'll call $$\alpha(n)$$ for convenience) can be realized by composite numbers.

As it turns out, there are many composite $$n$$ such that $$\alpha(n)$$ is $$2,3,4,5,6$$ ...

$$2$$ is very easy to achieve with a prime power.

16
25
27
49


So is $$3$$.

121
169
256
343


And so on up to 6.

175561
212521
326041
434281


Seven has a few but they're harder to find.

2042041
7447441
9393931


I'm curious whether every possible for $$\alpha(n)$$ is realizable by some composite $$n$$.

The examples that have turned up so far are prime powers and mostly squares of primes at that.

Update #1:

Interestingly, if you remove the restriction that $$n$$ has to be composite, there are relatively small solutions for $$\alpha^{-1}(8)$$ and $$\alpha^{-1}(9)$$.

Here are the solutions for $$\alpha^{-1}(9)$$ that I've found so far, all are prime.

300690391
340510171
358888531
397687291
406816411


Another pattern that seems to hold is that the smallest solution to $$\alpha^{-1}(n)$$ is less than $$10^n$$.

Update #2

It's possible that $$\omega(-1 + 2^{\mathbb{N}_{\ge 1}})$$ is $$\mathbb{N}_{\ge 1}$$. Since powers of two have exactly one prime factor, this is useful for establishing the truth of the lemma.

This OEIS sequence has the number of distinct factors of $$-1+2^n$$ https://oeis.org/A046800.

Some cursory investigation using pari/gp also suggests that this hits every positive integer.

$$\omega(-1 + 64 ^ {60}) = 29 \\ \omega(-1 + 64 ^ {66}) = 27 \\ \omega(-1 + 64 ^ {70}) = 34$$

• +1 to your question, which I regard as interesting. Personally, I can't even imagine how to attack this question. Feb 1, 2022 at 6:03
• Are you only interested in integer values of $\alpha(n)$ ? Feb 1, 2022 at 10:05
• The reason that small solutions are usually prime powers is that in the case $\omega(n)>1$, $n-1$ must have many distinct prime factors. However, my guess is that every positve integer can be achieved by finding a semiprime (which is not a square) of the form $p_1^{a_1}\cdot p_2^{a_2}\cdots p_{2n}^{a{_2n}}+1$ where $p_j$ is the $j$-th prime and $a_j$ are positive integers. A proof will probably be out of reach. Feb 1, 2022 at 10:22
• Would you accept a table with an example for each $n$ (upto some reasonable limit) , perhaps together with a lower bound for for the smallest solution ? Feb 2, 2022 at 11:46
• With $\alpha^{-1}(8)$ , do you mean $\frac{\omega(n)}{\omega(n-1)}=8$ ? By the way, a solution with $\alpha(n)=8$ is $$214007641=14629^2$$ For the integers solutions , I guess for every $n$ there is a prime $p$ such that $\alpha(p^2)=n$ Feb 2, 2022 at 12:19

That every integer ratio $$n$$ can be achieved , is probably impossible to be proven. But in the range $$[2,16]$$ , there are solutions in form of $$p^4$$ , where $$p$$ is a prime number :

2     16     2
5     625     3
11     14641     4
13     28561     5
43     3418801     6
83     47458321     7
307     8882874001     8
463     45954068161     9
1597     6504586067281     10
4217     316238254381921     11
20747     185276879591884081     12
102829     111805314979382104081     13
328901     11702018374499428575601     14
1799797     10492865217042730623781681     15
6498419     1783326405035972793339192721     16


The smallest prime power solutions are

gp > for(k=1,10,n=1;gef=0;while(gef==0,n=n+1;if(ispower(n)>0,if(ispseudoprime(n)==0,if(omega(n)==1,if(omega(n-1)==k,gef=1;print(k,"   ",n)))))))
1   4
2   16
3   121
4   841
5   17161
6   175561
7   2042041
8   214007641


The smallest solutions with more than one prime factor (conjecture : all of them have $$2$$ prime factors) :

1   15    2
2   391    2
3   30031    2
4   9699691    2


Solutions for larger $$\alpha$$ :

• $$\alpha(n)=17$$ : $$1109^{12}$$
• $$\alpha(n)=18$$ : $$1627^{12}$$
• $$\alpha(n)=19$$ : $$137^{24}$$
• $$\alpha(n)=20$$ : $$211^{24}$$

UPDATE : Dirichlet's theorem guarantees that for infinite many positive integers $$\ n\$$ , a prime number $$\ p\$$ with $$\ \alpha(p^2)=n\$$ exists. And if the Schinzel hypothesis is true , such a prime exists for every positive integer $$\ n\$$ , hence the above conjecture is true.

Proof :

Define $$t:=\prod_{j=2}^n p_j$$ where $$\ n\ge 2\$$ and $$\ p_j\$$ is the $$j$$-th prime number. Dirichlet's theorem guarantees that there is a positive integer $$\ s\$$ such that $$\ q:=st+1\$$ is prime. Then $$\omega(q^2-1)\ge \omega(q-1)=\omega(st)\ge \omega(t)=n-1$$ Hence $$\ \omega(q^2-1)\$$ with prime $$\ q\$$ is unbounded. Therefore infinite many $$\ n\$$ must be realizable.

Assume that with the above $$t$$ , we can find a prime $$\ p>p_n\$$ such that $$\ 2tp+1\$$ and $$\ 4tp+1\$$ are both prime. This is possible if the Schinzel hypothesis is true. Then with $$\ q:=4tp+1\$$ we have $$\omega(q+1)=\omega(4tp+2)=\omega(2(2tp+1))=2$$ and $$\omega(q-1)=\omega(4tp)=n+1$$ Because of $$\ \gcd(q-1,q+1)=2\$$ , we get $$\omega(q^2-1)=\omega(q-1)+\omega(q+1)-1=n+2$$ hence every positive integer $$\ n'=n+2\ge 4\$$ is realizable.

• $\alpha(n)=21$ : $14669^{12}$ Feb 3, 2022 at 9:37
• $\alpha(n)=22 : 27967^{12}$ Feb 3, 2022 at 10:30
• $\alpha(n)=23 : 53129^{12}$ Feb 3, 2022 at 10:31
• $\alpha(n)=24 : 563^{24}$ Feb 3, 2022 at 10:46
• $\alpha(n)=25 : 3863^ {24}$ Feb 3, 2022 at 10:48