2
$\begingroup$

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

$\endgroup$
21
  • $\begingroup$ Not sure why this is down- and closevoted. It is surely interesting (+1). However, I am not sure whether the actual records can be found with the sources as the cases you mentioned. Are you content with huge examples to begin with ? Or do you actually want to have the current world records ? $\endgroup$
    – Peter
    Dec 25, 2022 at 10:42
  • $\begingroup$ For $k=32$ , the largest $n$ I found so far is $4793$ $\endgroup$
    – Peter
    Dec 25, 2022 at 10:56
  • 1
    $\begingroup$ For $k=12$, the only further example up to $10^{12}+11$ is $n=1676641693$. The next example in the case $k=12$ is $n=1852069955839$. For $k=2$, a large example is $n=3^{541}-1$ ($n/2$ and $n-1$ are both prime). $\endgroup$
    – user1115547
    Dec 27, 2022 at 7:59
  • 1
    $\begingroup$ What did you find in OEiS? Can you post a link to your findings? $\endgroup$
    – Mason
    Dec 29, 2022 at 17:39
  • 1
    $\begingroup$ related $\endgroup$
    – Peter
    Jan 2 at 14:52

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ The largest solutions appeared as close to $300000$ for small $k$, but for larger $k$, they became small for $k\gt9$, approximately $c(k)\cdot k^e$ for some function $c(k)=k^{o(1)}$. Why did this happen? $\endgroup$
    – user1115547
    Dec 26, 2022 at 10:43
  • $\begingroup$ Exaclty that is what I wondered as well. Can we reformulate the requirement in terms of prime tuples ? Would that explain the break ? $\endgroup$
    – Peter
    Dec 26, 2022 at 10:45
  • $\begingroup$ Yes, it would. Use the conjecture that the sum of the prime factors (counted with multiplicity) of $\binom{n}{k}$ is at least $k\cdot log(log(n)-log(k))-(2+o(1))(log(n))$ as the positive integers $n$ and $k\ge n$ both vary. $\endgroup$
    – user1115547
    Dec 26, 2022 at 11:13
  • 1
    $\begingroup$ It is difficult to find large examples from about $k=10$ on. As I said , everyone is invited to edit my answer who found a (significantly) larger example than the given one. An example for $k=8$ (and all smaller $k$) is the $42$ digit number $k=lcm([1..80])\cdot 15688070-1$ $\endgroup$
    – Peter
    Jan 2 at 8:55
  • 1
    $\begingroup$ Although I tried various approaches , I did not find a solution for $15\le k\le 32$ larger than those in the table. There are no larger solutions upto $n=10^8$ , for $k=15$ and $k=16$ even upto $10^9$. $\endgroup$
    – Peter
    Jan 10 at 17:05

You must log in to answer this question.