[seqfan] Re: Phil Scovis's problem

[israel at math.ubc.ca]

It seems to me  a(m) is the least n such that n has at least m-1 divisors,
i.e. A061799(m-1).
Given x that has at least m-1 divisors d_1, ..., d_{m-1}, take distinct 
primes p_1, ...,p_{m-1}, q_1, ..., q_{m-1} that are coprime to x, and
let S = {x, d_1 p_1 q_2 ... q_{m-1}, d_2 p_1 p_2 q_3 ... q_{m-1}, ...,
    d_{m-1} p_1 ... p_{m-1}}

Note that gcd(x, S_j) = d_{j-1} for j = 1,...,m-1
while for 1 < i < j, gcd(S_i, S_j) is divisible by 
p_k iff k <= i-1 and is divisible by q_k iff k >= j.

Robert Israel
University of British Columbia


On Mar 5 2013, Neil Sloane wrote:

>Dear Sequence Fans:
>
>If you look at the History tab for A213909 you see the following problem,
>studied by Phil Scovis:
>
>Definition. Let S be a set of n positive numbers such that
>all n choose 2 pairwise GCD's are distinct, and let
>m(S) (resp. M(S)) denote the smallest and greatest elements of S;
>a(n) is the minimal value of m(S) over all choices for S.
>
>and a second sequence,
>
>b(n) is the minimal value of M(S) over all choices for S.
>
>Example: For n=4, S = {4,9,12,18} has its six GCD's equal to
>1,4,2,3,9,6, so it satisfies the condition, and shows that
>a(4) <= 4, b(4) <= 18.
>But S = {8,9,10,12} is not legal, since GCD(8,9) = 1 = GCD(9,10), and the
>GCD's are not all distinct.
>
> The values that were submitted - probably intended to be the b(n) 
> sequence - don't look right, and the submitter, perhaps wisely, withdrew 
> the sequence.
>
>But the questions seem interesting. What are the a(n) and b(n) sequences,
>and are they in the OEIS?
>(The closest entry I can find is Alois Heinz's A196719.)
>
>I get a(1)=b(1)=1; a(2)=1, b(2)=2 from S={1,2}; a(3)=2, b(3)=6 from
>S={2,3,6}.
>Of course in general the best S for a(n) will probably be different
>from the best S for b(n), and won't be unique, either.
>
>Neil
>
>
>