cp's OEIS Frontend

A346970 Smallest c which can be split into positive integers a,b with a+b=c, such that a*b*c is divisible by each of the first n primes.

%I A346970 #66 Sep 08 2022 08:16:16
%S A346970 2,3,5,10,21,55,182,357,1105,2958,16588,51243,106981,608685,3003455,
%T A346970 7497910,52350909,168539462,1822961393,3079378759
%N A346970 Smallest c which can be split into positive integers a,b with a+b=c, such that a*b*c is divisible by each of the first n primes.
%C A346970 From _David A. Corneth_, Aug 10 2021: (Start)
%C A346970 Let k be a candidate value for a(n) and let g = gcd(c, primorial(n)) = gcd(c, A002110(n)). Let p be the largest prime that primorial(n)/g is divisible by. Then at least one of a and b is divisible by p.
%C A346970 So we can check multiples m of p < k and see if m*(k-m)*k is divisible by primorial(n).
%C A346970 If that is the case then k can be written as a + b where 0 < a,b < k and a*b*k is divisible by primorial(n) and a(n) = k when each of 1..k-1 do not have that property. (End)
%C A346970 From _Kevin P. Thompson_, Jun 30 2022 and Sep 07 2022: (Start)
%C A346970    n   a(n) = c          a           b       a * b * c
%C A346970 ---- ---------- ---------- ----------- ---------------
%C A346970    1          2          1           1       prime(1)#
%C A346970    2          3          1           2       prime(2)#
%C A346970    3          5          2           3       prime(3)#
%C A346970    4         10          3           7       prime(4)#
%C A346970    5         21         10          11       prime(5)#
%C A346970    6         55         13          42       prime(6)#
%C A346970    7        182         17         165       prime(7)#
%C A346970    8        357        110         247       prime(8)#
%C A346970    9       1105        231         874       prime(9)#
%C A346970   10       2958       1463        1495      prime(10)#
%C A346970   11      16588       1615       14973  2 * prime(11)#
%C A346970   12      51243      16835       34408  4 * prime(12)#
%C A346970   13     106981      49335       57646      prime(13)#
%C A346970   14     608685      81548      527137  2 * prime(14)#
%C A346970   15    3003455     595034     2408421  7 * prime(15)#
%C A346970   16    7497910    2741301     4756609  3 * prime(16)#
%C A346970   17   52350909    2975429    49375480  4 * prime(17)#
%C A346970   18  168539462   55318167   113221295  9 * prime(18)#
%C A346970   19 1822961393  223726938  1599234455 83 * prime(19)#
%C A346970   20 3079378759  256763535  2822615224  4 * prime(20)# (End)
%C A346970 a(21) <= 111610913771, a(22) <= 111610913771 both via (a, b, c) = (54966571731, 56644342040, 111610913771). a(24) <= 8163073396289 via (a, b, c) = (133445799584, 8029627596705, 8163073396289). - _David A. Corneth_, Sep 07 2022
%F A346970 A002110(n)^(1/3) < a(n) <= A002110(n). - _David A. Corneth_, Aug 10 2021
%F A346970 a(2k) <= Product_{i=1..k} p_2i, a(2k+1) <= Product_{i=0..k} p_{2i+1} where p_i is the i-th prime. - _Chai Wah Wu_, Oct 14 2021
%F A346970 a(n) >= (4*A002110(n))^(1/3), strengthening David's result above. This inequality is strict for n > 1. - _Charles R Greathouse IV_, Jun 30 2022
%e A346970 a(4) = 10 via 3+7=10 and 3*7*10 = 210 which is divisible by each of the first 4 primes, namely 2, 3, 5 and 7.
%e A346970 a(7) = 182 via 17+165=182. 17*165*182 = 510510 which is divisible by each of the first 7 primes, namely 2, 3, ..., 13, 17.
%t A346970 Do[Monitor[k=1; While[!Or@@And@@@(IntegerQ/@(#/Prime@Range@n)&/@Times@@@(Join[{k}, #]&/@IntegerPartitions[k, {2}])), k++]; Print@k,k], {n, 20}] (* _Giorgos Kalogeropoulos_, Aug 16 2021 *)
%o A346970 (PARI) a(n) = { if(n <= 3, return(prime(n))); P = vecprod(primes(n)); for(i = sqrtnint(P, 3) + 1, oo, if(iscanforA(n, i), return(i) ) ) }
%o A346970 iscanforA(n, k) = { my(g = gcd(k, P), step); if(k^2*g < P, return(0)); step = hpf(P/g); forstep(i = step, k, step, if((i*(k-i)*k)%P == 0,  return(1) ) ); 0 }
%o A346970 hpf(n) = my(f = factor(n)); f[#f~, 1] \\ _David A. Corneth_, Aug 10 2021
%o A346970 (Python)
%o A346970 from sympy import primorial, primefactors, gcd
%o A346970 def A346970(n):
%o A346970     c, ps = 2, primorial(n)
%o A346970     while True:
%o A346970         m = ps//gcd(ps,c)
%o A346970         if m == 1:
%o A346970             return c
%o A346970         p = max(primefactors(m))
%o A346970         for a in range(p,c,p):
%o A346970             if a*(c-a) % m == 0:
%o A346970                 return c
%o A346970         c += 1 # _Chai Wah Wu_, Oct 13 2021
%Y A346970 Cf. A002110, A346971.
%K A346970 nonn,more
%O A346970 1,1
%A A346970 _Steven M. Altschuld_, Aug 09 2021
%E A346970 a(12)-a(16) from _David A. Corneth_, Aug 10 2021
%E A346970 a(17)-a(18) from _Kevin P. Thompson_, Jun 30 2022
%E A346970 a(19)-a(20) from _Kevin P. Thompson_, Sep 07 2022
%E A346970 a(20) corrected by _David A. Corneth_, Sep 07 2022