login
A076734
Smallest squarefree number greater than or equal to n having the same number of prime factors as n (counted with multiplicity).
5
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
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
KEYWORD
nonn
AUTHOR
Reinhard Zumkeller, Nov 08 2002
STATUS
approved