cp's OEIS Frontend

A282686 Least sum of two proper prime powers (A246547) that is the product of n distinct primes.

%I A282686 #65 Mar 31 2017 03:49:16
%S A282686 13,33,130,966,14322,81510,3530730,117535110,2211297270,131031070170,
%T A282686 1295080356570,163411918786830,3389900689405230,414524121952915590,
%U A282686 2951531806477464210,754260388389042905370
%N A282686 Least sum of two proper prime powers (A246547) that is the product of n distinct primes.
%C A282686 Least value of A225102 that is the product of n distinct primes.
%C A282686 From _Jon E. Schoenfield_, Mar 18 2017: (Start)
%C A282686 For each n, we can write a(n) = p^j + q^k where p and q are prime and 2 <= j <= k; since a(n) is squarefree, p and q are distinct.
%C A282686 Suppose j and k are both even. Then a(n) cannot have any prime factor f such that f == 3 (mod 4) (see A002145). Thus, a(n) is the product of n distinct terms of {2, 5, 13, 17, 29, 37, 41, ...} = A002313, so a(n) >= Product_{i=1..n} A002313(i) = A185952(n).
%C A282686 In fact, however, a(n) < A185952(n) for n = 4..15, and it seems nearly certain that this holds for all n > 3. In any case, if we search for a(n) by generating products of n distinct primes and, for each such product P, testing whether there exists a solution for P = p^j + q^k, then we need not consider solutions in which both j and k are even unless P >= A185952(n).
%C A282686 Additionally, since the sum of any two cubes that is divisible by 3 is also divisible by 9 (hence nonsquarefree), any P that is divisible by 3 cannot be the sum of two cubes, so the exponents j and k cannot both be divisible by 3. (Every P < 2*5*7*11*...*prime(n+1) = A002110(n+1)/3 is divisible by 3.) Thus, for every P that is divisible by 3 and < A185292(n), we can rule out every ordered pair (j,k) except (2,3) and (3,4) (which could be tested together by computing t = P - r^3 for each prime r < P^(1/3) and, if t is square, checking whether sqrt(t) is a prime or the square of a prime) and those with k >= 5 (which could be tested by checking whether t = P - q^k is a prime power for each prime power q^k that is less than P and has k >= 5). (End)
%C A282686 a(17) <= 63985284333636413237490 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 37 * 41 * 43 * 59 * 61 * 103 * 409 = 10461281^3 + 250679912393^2. - _Jon E. Schoenfield_, Mar 31 2017
%e A282686 a(1) = 13 = 2^2 + 3^2.
%e A282686 a(2) = 33 = 5^2 + 2^3 = 3 * 11.
%e A282686 a(3) = 130 = 3^2 + 11^2 = 2 * 5 * 13.
%e A282686 a(4) = 966 = 5^3 + 29^2 = 2 * 3 * 7 * 23.
%e A282686 a(5) = 14322 = 17^3 + 97^2 = 2 * 3 * 7 * 11 * 31.
%e A282686 a(6) = 81510 = 29^3 + 239^2 = 2 * 3 * 5 * 11 * 13 * 19.
%e A282686 a(7) = 3530730 = 41^4 + 89^3 = 2 * 3 * 5 * 7 * 17 * 23 * 43.
%e A282686 a(8) = 117535110 = 461^3 + 4423^2 = 2 * 3 * 5 * 7 * 11 * 17 * 41 * 73.
%e A282686 From _Jon E. Schoenfield_, Mar 14 2017: (Start)
%e A282686 a(9) = 2211297270 = 1301^3 + 3037^2 = 2 * 3 * 5 * 7 * 13 * 17 * 29 * 31 * 53.
%e A282686 a(10) = 131031070170 = 1361^3 + 358483^2 = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 43 * 47 * 127. (End)
%e A282686 From _Giovanni Resta_, Mar 14 2017: (Start)
%e A282686 a(11) = 810571^2 + 8609^3,
%e A282686 a(12) = 12694849^2 + 13109^3. (End)
%e A282686 From _Jon E. Schoenfield_, Mar 18 2017: (Start)
%e A282686 a(13) = 24537703^2 + 140741^3.
%e A282686 a(14) = 639414679^2 + 178349^3.
%e A282686 a(15) = 1632727069^2 + 658649^3. (End)
%e A282686 a(16) = 1472015189^2 + 9094049^3. - _Jon E. Schoenfield_, Mar 19 2017
%p A282686 N:= 1.2*10^8: # to get all terms <= N
%p A282686 PP:= {seq(seq(p^k,k=2..floor(log[p](N))), p = select(isprime, [2,seq(i,i=3..floor(sqrt(N)),2)]))}:
%p A282686 PP:= sort(convert(PP,list)):
%p A282686 A:= 'A':
%p A282686 for i from 1 to nops(PP) do
%p A282686   for j from 1 to i do
%p A282686      Q:= PP[i]+PP[j];
%p A282686      if Q > N then break fi;
%p A282686      F:= ifactors(Q)[2];
%p A282686      if max(seq(f[2],f=F))>1 then next fi;
%p A282686      m:= nops(F);
%p A282686      if not assigned(A[m]) or A[m] > Q then A[m]:= Q fi
%p A282686 od od:
%p A282686 seq(A[i],i=1..max(map(op,[indices(A)]))); # _Robert Israel_, Mar 01 2017
%t A282686 (* first 8 terms *) mx = 1.2*^8; a = 0 Range[8] + mx; p = Sort@ Flatten@ Table[ p^Range[2, Log[p, mx]], {p, Prime@ Range@ PrimePi@ Sqrt@ mx}]; Do[ j=1; While[j <= i && (v = p[[i]] + p[[j]]) < mx, f = FactorInteger@v; If[Max[Last /@ f] == 1, c = Length@f; If[c < 9 && v < a[[c]], a[[c]] = v]]; j++], {i, Length@p}]; a (* _Giovanni Resta_, Mar 19 2017 *)
%o A282686 (PARI) do(lim)=my(v=List(),u=v,t,f); t=1; for(i=1,lim, t*=prime(i); if(t>lim,break); listput(v, oo)); v=Vec(v); for(e=2,logint(lim\=1,2), forprime(p=2,sqrtnint(lim-4,e), listput(u,p^e))); u=Set(u); for(i=1,#u, for(j=1,i, t=u[i]+u[j]; if(t>lim, break); f=factor(t)[,2]; if(vecmax(f)==1 && t<v[#f], v[#f]=t))); apply(k->if(k==oo,"?",k), v) \\ _Charles R Greathouse IV_, Mar 19 2017
%o A282686 (PARI) do(lim)=my(v=List(),u=v,t,f,p2); t=1; for(i=1,lim, t*=prime(i); if(t>lim,break); listput(v, oo)); v=Vec(v); for(e=3,logint(lim\=1,2), forprime(p=2,sqrtnint(lim-4,e), listput(u,p^e))); u=Set(u); for(i=1,#u, for(j=1,i, t=u[i]+u[j]; if(t>lim, break); f=factor(t)[,2]; if(vecmax(f)==1 && t<v[#f], v[#f]=t))); forprime(p=2,sqrtint(lim), p2=p^2; for(i=1,#u, t=u[i]+p2; if(t>lim, break); f=factor(t)[,2]; if(vecmax(f)==1 && t<v[#f], v[#f]=t))); forprime(p=2,sqrtint(lim), p2=p^2; forprime(q=2,min(sqrtint(lim-p2),p), t=p2+q^2; if(t>lim, break); f=factor(t)[,2]; if(vecmax(f)==1 && t<v[#f], v[#f]=t))); apply(k->if(k==oo,"?",k), v) \\ _Charles R Greathouse IV_, Mar 19 2017
%Y A282686 Cf. A225102, A246547.
%K A282686 nonn,more
%O A282686 1,1
%A A282686 _Altug Alkan_, Feb 20 2017
%E A282686 a(7)-a(8) from _Giovanni Resta_, Feb 21 2017
%E A282686 a(9)-a(10) from _Jon E. Schoenfield_, Mar 14 2017
%E A282686 a(11)-a(12) from _Giovanni Resta_, Mar 14 2017
%E A282686 a(13)-a(15) from _Jon E. Schoenfield_, Mar 18 2017
%E A282686 a(16) from _Jon E. Schoenfield_, Mar 19 2017