$1$ as difference of composites with same number of prime factors and smallest examples

520 Views Asked by At

It is probably open can we for every $k \in \mathbb N$ find two composites $a_k$ and $b_k$ such that $a_k$ and $b_k$ have exactly $k$ prime factors and $a_k-b_k=1$.

Smallest examples found so far are:

for $k=1$ $$3^2-2^3=1$$ for $k=2$ $$3 \cdot 5 - 7 \cdot 2=1$$ for $k=3$ $$3\cdot7\cdot11-2\cdot5\cdot23=1$$ for $k=4$ $$5 \cdot 7 \cdot 11 \cdot 19 - 2 \cdot 3 \cdot 23 \cdot 53=1$$ for $k=5$ $$3\cdot7\cdot17\cdot23\cdot31-2^2\cdot5\cdot11\cdot13\cdot89=1$$

It is easy to see that $3$ is a factor of one of numbers that are smallest pair for $k=1,2,3,4,5$ so I will make a pretty dumb conjecture that could be ruled out with a clever computer-check:

If a pair $(a_k,b_k)$ is smallest pair then $3$ is a factor of one of those two numbers.

Until which $k$ is this true?

I am prepared to let this always be true because smallest pairs should tend to have small primes as factors of them and because there is a good chance that one of members is divisible by $3$ because they differ only by one.

I am not sure would I like to see a counterexample, but go for it.

This is true at least for $k=1,2,3,4,5,6,7,8,9,10,11$ by this list .

1

There are 1 best solutions below

2
On

I'll write currently the smallest known for me pairs $(a_k,b_k)$ for $k=12,...,19$ (so far).
Each of the examples has few smallest prime numbers as divisors of $a_k$ or $b_k$.
Hope it will help to optimize search of the smallest examples.

(underlined parts of $a_k$, $b_k$ prime factorizations are constructed of first prime numbers)

$k= 12$:
$a_k = 12\:633\:565\:576\:364\:596\:150$;
$\log_2(a_k)\approx 63.4539$;
$a_k = \underline{2 \cdot 5^2 \cdot 7 \cdot 17 \cdot 29} \cdot 41 \cdot 47 \cdot 79 \cdot 97 \cdot 107 \cdot 149 \cdot 311$;
$b_k = \underline{3 \cdot 11 \cdot 13 \cdot 19 \cdot 23} \cdot 43 \cdot 59 \cdot 61 \cdot 71 \cdot 89 \cdot 137 \cdot 503$;

$ $

$k=13$:
$a_k = 2\:132\:500\:253\:472\:667\:779\:415$;
$\log_2(a_k) \approx 70.8530$;
$a_k = \underline{5\cdot 11\cdot 13\cdot 17\cdot 23\cdot 29}\cdot 79\cdot 83\cdot 101\cdot 127\cdot 139\cdot 149\cdot 151$;
$b_k = \underline{2\cdot 3\cdot 7\cdot 31\cdot 37\cdot 41}\cdot 47\cdot 67\cdot 89\cdot 131\cdot 167\cdot 293\cdot 601$;

$ $

$k=14$:
$a_k = 385\:933\:998\:695\:788\:640\:214\:195$;
$\log_2(a_k) \approx 78.3527$;
$a_k = \underline{3\cdot 5\cdot 13\cdot 19\cdot 29\cdot 31} \cdot 47\cdot 61\cdot 71\cdot 73\cdot 83\cdot 263\cdot 523\cdot 683$;
$b_k = \underline{2\cdot 7\cdot 11\cdot 17\cdot 23\cdot 37} \cdot 67\cdot 89\cdot 103\cdot 131\cdot 137\cdot 139\cdot 167\cdot 677$;

$ $

$k=15$:
$a_k = 85\:227\:871\:774\:666\:834\:526\:775\:385$;
$\log_2(a_k) \approx 86.1395$;
$a_k = \underline{5 \cdot 7 \cdot 11 \cdot 23 \cdot 31 \cdot 37 \cdot 41} \cdot 61 \cdot 71 \cdot 109 \cdot 137 \cdot 139 \cdot 179 \cdot 193 \cdot 659$;
$b_k = \underline{2^3 \cdot 3 \cdot 13 \cdot 17 \cdot 19 \cdot 29} \cdot 47 \cdot 67 \cdot 79 \cdot 97 \cdot 113 \cdot 227 \cdot 263 \cdot 359 \cdot 499$;

$k=16$:
$a_k = 26\:178\:447\:467\:854\:363\:658\:945\:915\:661$;
$\log_2(a_k) \approx 94.4024$;
$a_k = \underline{3\cdot 11\cdot 13\cdot 17\cdot 31\cdot 41}\cdot 53\cdot 59\cdot 61\cdot 67\cdot 71\cdot 107\cdot 127\cdot 383\cdot 569\cdot 1051$;
$b_k = \underline{2^2\cdot 5\cdot 7\cdot 19\cdot 23\cdot 29\cdot 37}\cdot 47\cdot 97\cdot 109\cdot 137\cdot 179\cdot 239\cdot 337\cdot 541\cdot 751$;

$ $

$k=17$:
$a_k = 10\:605\:529\:576\:824\:631\:399\:932\:870\:736\:771$;
$\log_2(a_k) \approx 103.065$;
$a_k = \underline{7\cdot 11\cdot 19\cdot 23\cdot 29}\cdot 43\cdot 53\cdot 67\cdot 71\cdot 79\cdot 97\cdot 113\cdot 163\cdot 167\cdot 223\cdot 269\cdot 709$;
$b_k = \underline{2\cdot 3\cdot 5\cdot 13\cdot 17\cdot 31\cdot 37}\cdot 47\cdot 89\cdot 101\cdot 103\cdot 131\cdot 151\cdot 307\cdot 463\cdot 941\cdot 12113$;

$ $

$k=18$:
$a_k = 2\:721\:339\:663\:582\:565\:833\:514\:546\:530\:863\:095$;
$\log_2(a_k) \approx 111.068$;
$a_k = \underline{5\cdot 7\cdot 11\cdot 17\cdot 23\cdot 29\cdot 37\cdot 59}\cdot 83\cdot 97\cdot 103\cdot 137\cdot 163\cdot 229\cdot 307\cdot 461\cdot 487\cdot 977$;
$b_k = \underline{2\cdot 3\cdot 13\cdot 19\cdot 31\cdot 41\cdot 43\cdot 47\cdot 53\cdot 61}\cdot 89\cdot 101\cdot 127\cdot 157\cdot 191\cdot 421\cdot 2749\cdot 5581$;

$ $

$k=19$:
$a_k = 1\:466\:984\:471\:113\:689\:102\:348\:101\:689\:630\:431\:526$;
$\log_2(a_k) \approx 120.142$;
$a_k = \underline{2\cdot 7\cdot 13\cdot 29}\cdot 41\cdot 59\cdot 67\cdot 71\cdot 73\cdot 83\cdot 89\cdot 103\cdot 151\cdot 163\cdot 173\cdot 211\cdot 397\cdot 577\cdot 2113$;
$b_k = \underline{3\cdot 5^2\cdot 11\cdot 17\cdot 19\cdot 23}\cdot 37\cdot 43\cdot 47\cdot 53\cdot 61\cdot 79\cdot 97\cdot 181\cdot 257\cdot 317\cdot 677\cdot 3359\cdot 3853$;


We can define theoretical (unreachable) lower bound for given $k$ as $$m_k = \sqrt{p_{2k}\#},$$ where $p_n\#$ is primorial ($p_n\# = p_1\cdot p_2\cdots p_n$).

This way we can estimate efficiency of incoming new values:
denote 'defect' $\Delta$: $$\Delta = \log_2(a_k)-\log_2(m_k)$$ (if 'defect' is less, then estimation is better);
one can note that $\Delta$ growth more-or-less linearly in the range $k=2 \ldots 19$, so the values for $k=12,13,\ldots,19$ are not far from the smallest examples:

\begin{array}{|l|r|l|l|} \hline k & \log_2(m_k) & \log_2(a_k) & \Delta \\ \hline ... & ... & ... & ... \\ 7 & 26.7693 & 29.8460 & 3.077\\ 8 & 32.4105 & 35.9390 & 3.528 \\ 9 & 38.3172 & 42.3748 & 4.058 \\ 10 & 44.4251 & 48.7998 & 4.375 \\ 11 & 50.6719 & 56.0886 & 5.417 \\ \hline 12 & 57.0973 & 63.4539 & 6.357 \\ 13 & 63.7263 & 70.8530 & 7.127 \\ 14 & 70.4404 & 78.3527 & 7.912 \\ 15 & 77.2345 & 86.1395 & 8.905 \\ 16 & 84.2455 & 94.4023 & 10.157 \\ 17 & 91.3541 & 103.065 & 11.710 \\ 18 & 98.5829 & 111.068 & 12.485 \\ 19 & 105.905 & 120.142 & 14.237 \\ ... & ... & ... & ... \\ \hline \end{array}

And plot of the current values $\Delta$:

Delta plot