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

Question

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

Answer 1

PARTIAL ANSWER

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.