For 1 <= j <= k, does there always exist n with exactly j divisors <= k?
Let j be a prime >= k/2. If n has exactly j divisors then n=p^(j-1) for some prime p. If k>= 10 then 2^(k/2-1) > k so the statement is false for that j,k. Victor Sent from my iPhone On Apr 21, 2012, at 16:16, David Wilson <davidwwilson@comcast.net> wrote:
For 1 <= j <= k, does there always exist n with exactly j divisors <= k?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Sat, Apr 21, 2012 at 11:18 PM, Victor S. Miller <victorsmiller@gmail.com> wrote:
Let j be a prime >= k/2. If n has exactly j divisors then n=p^(j-1) for some prime p.
As I read the question, n can have more than j divisors, but it has exactly j divisors that are less than or equal to k.
If k>= 10 then 2^(k/2-1) > k so the statement is false for that j,k.
Victor
Sent from my iPhone
On Apr 21, 2012, at 16:16, David Wilson <davidwwilson@comcast.net> wrote:
For 1 <= j <= k, does there always exist n with exactly j divisors <= k?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
n=1 satisfies the j=1 case for all k. n=2 satisfies the j=2 case for all k. The first slightly interesting case is j=3. For k=3, n=6 is the only possible solution, but for all larger k, n=4 works. For j=4: if j=4 or 5, n=12. If j=6, n=6 is, I believe, forced. And n=6 works for all larger k. In general, we can say that for j=k, k! works (and there are smaller solutions). And if n is the smallest number with exactly j divisors, it works for all k>=n. But in the gap, things can probably get tricky. On 4/21/12, Mike Stay <metaweta@gmail.com> wrote:
On Sat, Apr 21, 2012 at 11:18 PM, Victor S. Miller <victorsmiller@gmail.com> wrote:
Let j be a prime >= k/2. If n has exactly j divisors then n=p^(j-1) for some prime p.
As I read the question, n can have more than j divisors, but it has exactly j divisors that are less than or equal to k.
If k>= 10 then 2^(k/2-1) > k so the statement is false for that j,k.
Victor
Sent from my iPhone
On Apr 21, 2012, at 16:16, David Wilson <davidwwilson@comcast.net> wrote:
For 1 <= j <= k, does there always exist n with exactly j divisors <= k?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The following construction appears to answer the question affirmatively. Let N(S,k) be the number of divisors of lcm(S) which are <= k. Construct S with N(S,k) = j as follows: initialize S <- {1} repeat { select the minimum prime power p^a s.t. p^(a-1) in S, p^a not in S, and N (S union {p^a}, k) <= j set S <- S union {p^a} } until N(S,k) = j Examples: lcm(S) with 23 divisors <= 420 constructs S = {1,2,3,4,5,8,16,107}. lcm(S) with k divisors <= k constructs S = (prime powers in 1..k}. If a prime power is always selectable, divisor count increases at each iteration and the construction terminates. Because the construction gives priority to small divisors in S, there are many primes and powers available for selection at each stage. This observation can probably be turned into a proof.
-----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun- bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Saturday, April 21, 2012 3:34 PM To: math-fun Subject: Re: [math-fun] divisor question
n=1 satisfies the j=1 case for all k.
n=2 satisfies the j=2 case for all k.
The first slightly interesting case is j=3. For k=3, n=6 is the only possible solution, but for all larger k, n=4 works.
For j=4: if j=4 or 5, n=12. If j=6, n=6 is, I believe, forced. And n=6 works for all larger k.
In general, we can say that for j=k, k! works (and there are smaller solutions). And if n is the smallest number with exactly j divisors, it works for all k>=n. But in the gap, things can probably get tricky.
On 4/21/12, Mike Stay <metaweta@gmail.com> wrote:
On Sat, Apr 21, 2012 at 11:18 PM, Victor S. Miller <victorsmiller@gmail.com> wrote:
Let j be a prime >= k/2. If n has exactly j divisors then n=p^(j-1) for some prime p.
As I read the question, n can have more than j divisors, but it has exactly j divisors that are less than or equal to k.
If k>= 10 then 2^(k/2-1) > k so the statement is false for that j,k.
Victor
Sent from my iPhone
On Apr 21, 2012, at 16:16, David Wilson <davidwwilson@comcast.net> wrote:
For 1 <= j <= k, does there always exist n with exactly j divisors
<= k?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Ah, I parsed it differently. Sent from my iPhone On Apr 21, 2012, at 18:21, Mike Stay <metaweta@gmail.com> wrote:
On Sat, Apr 21, 2012 at 11:18 PM, Victor S. Miller <victorsmiller@gmail.com> wrote:
Let j be a prime >= k/2. If n has exactly j divisors then n=p^(j-1) for some prime p.
As I read the question, n can have more than j divisors, but it has exactly j divisors that are less than or equal to k.
If k>= 10 then 2^(k/2-1) > k so the statement is false for that j,k.
Victor
Sent from my iPhone
On Apr 21, 2012, at 16:16, David Wilson <davidwwilson@comcast.net> wrote:
For 1 <= j <= k, does there always exist n with exactly j divisors <= k?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Allan Wechsler -
David Wilson -
Huddleston, Scott -
Mike Stay -
Victor S. Miller