

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

The set S must contain 1 and all primes p <= n. All semiprimes <= n are then in S*S.
Thus a(n)=a(n1) if n is a semiprime, and a(n)=a(n1)+1 if n is prime.
Is a(n)/A000720(n) bounded as n > infinity? (End)


LINKS



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[n1]+1;
V[n]:= V[n1] union {n};
elif numtheory:bigomega(n) = 2 then
A[n]:= A[n1];
V[n]:= V[n1];
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:


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



