A076734 Smallest squarefree number greater than or equal to n having the same number of prime factors as n (counted with multiplicity).

1, 2, 3, 6, 5, 6, 7, 30, 10, 10, 11, 30, 13, 14, 15, 210, 17, 30, 19, 30, 21, 22, 23, 210, 26, 26, 30, 30, 29, 30, 31, 2310, 33, 34, 35, 210, 37, 38, 39, 210, 41, 42, 43, 66, 66, 46, 47, 2310, 51, 66, 51, 66, 53, 210, 55, 210, 57, 58, 59, 210, 61, 62, 66, 30030, 65, 66, 67

Offset: 1

Author

Reinhard Zumkeller, Nov 08 2002

Keywords

• nonn

Comments

a(n) = n if and only if n is squarefree; A001222(a(n)) = A001222(n).

Suppose k = the number of prime factors of n. If p_k# is the product of the first k primes (i.e., a primorial), then the squarefree number a(n) will be p_k# if and only if p_k# <= n. This is because the smallest squarefree number with k prime factors is p_k#. - Michael De Vlieger, Aug 31 2014

Examples

			a(7) = 7 because 7 is squarefree.
a(8) = 30 because 8 has 3 prime factors but is not squarefree; 12, 18, 20 and 27 also have 3 prime factors each but are not squarefree either; so 30 is the smallest squarefree number with 3 prime factors.
a(9) = 10 because 9 has 2 prime factors but is not squarefree, while 10 has 2 prime factors and is squarefree.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A002110, A005117, A067535.

Programs

Maple

f:= proc(n)
     uses numtheory,Optimization;
     local k,P,m,Q;
     if issqrfree(n) then return n fi;
     k:= bigomega(n);
     m:= floor((n-1)/2);
     P:= select(isprime,{2,seq(2*i+1,i=1..m)});
     while nops(P) < k do
        m:= m+1;
        if isprime(2*m+1) then P:= P union {2*m+1} fi
     od:
     if convert(P[1..k],`*`) > n then return convert(P[1..k],`*`) fi;
     Q:= Minimize(add(x[i]*log(P[i]),i=1..nops(P)),
         { add(x[i]*log(P[i]),i=1..nops(P)) >= log(n),
           add(x[i],i=1..nops(P))=k},assume=binary);
     simplify(exp(Q[1]));
end proc:
seq(f(n),n=1..100); # Robert Israel, Sep 01 2014

Mathematica

f[n_, lim_] := If[n == 0, {1}, Block[{P = Product[Prime@ i, {i, n}], k = 1, c, w = ConstantArray[1, n]}, {P}~Join~Reap[Do[w = If[k == 1, MapAt[# + 1 &, w, -k], Join[Drop[MapAt[# + 1 &, w, -k], -k + 1], ConstantArray[1, k - 1]]]; c = Times @@ Map[If[# == 0, 1, Prime@#] &, Accumulate@ w]; If[c < lim, Sow[c]; k = 1, If[k == n, Break[], k++]], {i, Infinity}]][[-1, 1]]]]; Array[Which[SquareFreeQ@ #1, #1, #3 < #1, #3, True, SelectFirst[Sort@ f[#2, #1 + Product[Prime@ i, {i, 1 + #2}]], Function[k, k > #1]]] & @@ {#, PrimeOmega@ #, Times @@ Prime@ Range@ #} &, 10^4] (* Michael De Vlieger, Oct 20 2017 *)