Author |
Topic: n-ugly numbers and perfect squares (Read 897 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
n-ugly numbers and perfect squares
« on: Jun 16th, 2007, 9:36am » |
 Quote  Modify
|
A number is called n-ugly if it is only divisible by primes among the first n primes.
You are given an arbitrary set U of n+1 n-ugly numbers.
Show that there is some non-empty subset of U with the property that the product of its elements is a perfect square.
Show that there is some set V of n n-ugly numbers without this property.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: n-ugly numbers and perfect squares
« Reply #1 on: Jun 16th, 2007, 10:05am » |
Quote Modify
|
You could make a bitstring for each number, where for each the ith prime the ith bit is set if the highest power of that prime dividing the number is odd. Now the problem is akin to the claim there is a non-empty subset of these n+1 bitstrings for which the XOR to 0.
I'm not sure what you mean with the last part. Is V still a subset of U?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: n-ugly numbers and perfect squares
« Reply #2 on: Jun 16th, 2007, 10:18am » |
Quote Modify
|
No, U and V are unrelated.
(I admit, the part about V is trivial, it was only put there for completeness)
|
| « Last Edit: Jun 17th, 2007, 11:23am by Aryabhatta » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: n-ugly numbers and perfect squares
« Reply #3 on: Jun 18th, 2007, 7:32am » |
Quote Modify
|
Well, since it's trivial:
V={pi}
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: n-ugly numbers and perfect squares
« Reply #4 on: Jun 18th, 2007, 11:07pm » |
Quote Modify
|
Is the U-part solved?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: n-ugly numbers and perfect squares
« Reply #5 on: Jun 19th, 2007, 12:45am » |
Quote Modify
|
on Jun 18th, 2007, 11:07pm, Barukh wrote:Not in this thread.
I just restated the problem in other terms for a different perspective. I haven't given it much more thought yet.
|
| « Last Edit: Jun 19th, 2007, 12:52am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: n-ugly numbers and perfect squares
« Reply #6 on: Jun 20th, 2007, 9:22pm » |
Quote Modify
|
on Jun 16th, 2007, 10:05am, towr wrote:| You could make a bitstring for each number, where for each the ith prime the ith bit is set if the highest power of that prime dividing the number is odd. |
|
And then you could take all those bits and put them in an array.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: n-ugly numbers and perfect squares
« Reply #7 on: Jun 20th, 2007, 11:59pm » |
Quote Modify
|
Aha! Linear dependency?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: n-ugly numbers and perfect squares
« Reply #8 on: Jun 21st, 2007, 10:11am » |
Quote Modify
|
Correct! Barukh. You got it!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print