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

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