login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A076734 Smallest squarefree number greater than or equal to n having the same number of prime factors as n (counted with multiplicity). 5

%I #32 Oct 21 2017 22:05:09

%S 1,2,3,6,5,6,7,30,10,10,11,30,13,14,15,210,17,30,19,30,21,22,23,210,

%T 26,26,30,30,29,30,31,2310,33,34,35,210,37,38,39,210,41,42,43,66,66,

%U 46,47,2310,51,66,51,66,53,210,55,210,57,58,59,210,61,62,66,30030,65,66,67

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

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

%C 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

%H Michael De Vlieger, <a href="/A076734/b076734.txt">Table of n, a(n) for n = 1..10000</a>

%e a(7) = 7 because 7 is squarefree.

%e 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.

%e a(9) = 10 because 9 has 2 prime factors but is not squarefree, while 10 has 2 prime factors and is squarefree.

%p f:= proc(n)

%p uses numtheory,Optimization;

%p local k,P,m,Q;

%p if issqrfree(n) then return n fi;

%p k:= bigomega(n);

%p m:= floor((n-1)/2);

%p P:= select(isprime,{2,seq(2*i+1,i=1..m)});

%p while nops(P) < k do

%p m:= m+1;

%p if isprime(2*m+1) then P:= P union {2*m+1} fi

%p od:

%p if convert(P[1..k],`*`) > n then return convert(P[1..k],`*`) fi;

%p Q:= Minimize(add(x[i]*log(P[i]),i=1..nops(P)),

%p { add(x[i]*log(P[i]),i=1..nops(P)) >= log(n),

%p add(x[i],i=1..nops(P))=k},assume=binary);

%p simplify(exp(Q[1]));

%p end proc:

%p seq(f(n),n=1..100); # _Robert Israel_, Sep 01 2014

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

%Y Cf. A002110, A005117, A067535.

%K nonn

%O 1,2

%A _Reinhard Zumkeller_, Nov 08 2002

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)