Largest known positive integer n such that $\binom{n}{k}$ has k prime factors (counted with multiplicity) for each $k\le32$

249 Views Asked by At

The numbers n such that $\binom{n}{1}$ have $1$ prime factor (counted with multiplicity) are simply the primes. Therefore, for $k=1$ this gives the largest known prime, $n=2^{82589933}-1$. For $k=2$, the numbers n such that $\binom{n}{2}$ have $2$ prime factors (counted with multiplicity) are $2p$ such that $p$ and $2p-1$ are primes and the safe primes, primes $p$ such that $(p-1)/2$ is also prime. Since $2618163402417\cdot2^{1290001}-1$, the largest known prime $p$ such that $(p-1)/2$ is also prime, is greater than $7775705415\cdot2^{175116}+2=2p$, where $p$ is the largest known prime such that $2p-1$ is also prime, $2618163402417\cdot2^{1290001}-1$ is the largest known such $n$ for $k=2$. This will change from time to time.

What about $3\le k \le 32$?

For $3\le k\le 14$, I found in OEIS that $\binom{2918756139031688155200+k}{k}$, where $n=2918756139031688155200+k$, $k\le 14$, and $\binom{7272877497848202239}{k}$, where $n=7272877497848202239$, $k\le 14$, have k prime factors (counted with multiplicity). These are just the lower bounds for such $n$'s. Definitely these aren't the largest known $n$'s such that $\binom{n}{k}$ has $k$ prime factors (counted with multiplicity) for $3\le k \le6$.

Main problem: Find at least one positive integer $n\gt10^4$ such that $\binom{n}{k}$ has exactly $k$ prime factors (counting multiplicity) for each $15\le k\le 32$.

1

There are 1 best solutions below

10
On

This is a partial answer. As above mentioned, those values are probably much too small. The table (created with the free calculator PARI/GP) lists the largest solution $n\le 3\cdot 10^5$ for $k=3,\cdots ,32$ :

gp > for(k=3,32,maxi=0;for(m=k,3*10^5,s=binomial(m,k);if(bigomega(s)==k,maxi=m));print(k,"  ",maxi))
3  299723
4  298204
5  280223
6  280223
7  280223
8  280223
9  2089
10  362
11  319
12  797
13  797
14  719
15  799
16  1241
17  593
18  2099
19  2399
20  1052
21  2103
22  2974
23  2399
24  1403
25  2239
26  2106
27  5179
28  3548
29  3229
30  5182
31  5183
32  4793
gp >

For small $k$ , we can find at least lower bounds for the desired values. Define $n(k)$ to be the largest known $n$ for the corresponding $k$ , we can say $$n(3)\ge 10^{1000}+1401064021050844540399$$ $$n(4)\ge 10^{200}+6985786741233199$$ $$n(5)\ge lcm([1..200])\cdot 5012200-1$$ $$n(6)\ge lcm([1..200])\cdot 5012200-1$$ $$n(7)\ge lcm([1..80])\cdot 15688070-1$$ $$n(8)\ge lcm([1..80])\cdot 15688070-1$$ $$n(9)\ge lcm([1..35])\cdot 160479169-1$$ $$n(10)\ge 101114034374873519$$ With increasing $k$ , it will become more and more difficult to find huge examples. Everyone finding larger examples can edit the question accordingly.