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,2

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

Links

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

Example

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.

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 *)

Crossrefs

Cf. A002110, A005117, A067535.

Sequence in context: A361480 A142151 A003968 * A242314 A242311 A097723

Adjacent sequences: A076731 A076732 A076733 * A076735 A076736 A076737

Keyword

nonn

Author

Reinhard Zumkeller, Nov 08 2002

Status

approved