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

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A194806 Size of the smallest subset S of T = {1,2,3,...,n} such that S*S contains T, where S*S is the set of all products of elements of S. 1
 1, 2, 3, 3, 4, 4, 5, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 15, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 21, 21, 21, 22, 22, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 27, 27, 28, 28, 28, 28, 29, 29, 29, 29, 30, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 33, 34, 34, 34 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS From Robert Israel, Jan 09 2017: (Start) The set S must contain 1 and all primes p <= n. All semiprimes <= n are then in S*S. Thus a(n)=a(n-1) if n is a semiprime, and a(n)=a(n-1)+1 if n is prime. In particular, a(n) >= A000720(n). Is a(n)/A000720(n) bounded as n -> infinity? (End) LINKS Robert Israel, Table of n, a(n) for n = 1..3000 Robert Israel, An optimal set S for each n = 1..400 Robert Israel, Code for MATLAB with CPLEX EXAMPLE {1,2,3}*{1,2,3} = {1,2,3,4,6,9}, which contains {1,2,3,4}, but no smaller set than {1,2,3} has this property, so a(4) = 3. MAPLE N:= 100: # to get a(1) to a(N) makecon:= proc(m) local F, t; F:= select(t -> t^2 <= m, numtheory:-divisors(m)); subs(Known, add(`if`(t^2=m, X[t], X[t]*X[m/t]), t=F)>=1); end proc: P:= {1}: Known:= {X[1]=1}: Cons:= {}: M:= {}: A[1]:= 1: V[1]:= {1}: Ycount:= 0: for n from 2 to N do if isprime(n) then P:= P union {n}; Known:= Known union {X[n] = 1}; A[n]:= A[n-1]+1; V[n]:= V[n-1] union {n}; elif numtheory:-bigomega(n) = 2 then A[n]:= A[n-1]; V[n]:= V[n-1]; else newcons:= makecon(n); newycons:= NULL; M:= indets(newcons, `*`); for t in M do Ycount:= Ycount+1; newycons:= newycons, op(1, t) >= Y[Ycount], op(2, t) >= Y[Ycount]; newcons:= subs(t = Y[Ycount], newcons); od; Cons:= Cons union {newcons, newycons}; Obj:= convert(select(t -> op(0, t)=X, indets(Cons)), `+`); Res:= Optimization:-Minimize(Obj, Cons, assume=binary); A[n]:= Res[1] + nops(P); V[n]:= select(t -> subs(Res[2], X[t])=1, {\$1..n}) union P; fi od: seq(A[i], i=1..N); # Robert Israel, Jan 09 2017 CROSSREFS Sequence in context: A319246 A280026 A323080 * A229790 A156261 A071823 Adjacent sequences: A194803 A194804 A194805 * A194807 A194808 A194809 KEYWORD nonn AUTHOR John W. Layman, Sep 20 2011 STATUS approved

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.

Last modified June 9 21:19 EDT 2023. Contains 363183 sequences. (Running on oeis4.)