mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2012-04-28, 10:41   #1
jnml
 
Feb 2012
Prague, Czech Republ

22×41 Posts
Default Perfect square or not?

Bob has a huge, zillion digits number and needs to know if it is a perfect square or not. Unfortunately, the number is so big no usual computer methods are able to give the answer in any reasonable time. The number has no apparent special form.

Bob consults Alice. Alice asks Bob what is the value of bit X in the binary representation of the number. Bob says it is Y. Alice tells Bob that his number is not a perfect square.

The above is enough to now know what are the values of X and Y.

(Addmited, this one is so easy it may even not belong here, but I still find surprisingly many people not being able to solve it. Can you? ;-)
jnml is offline   Reply With Quote
Old 2012-04-28, 11:31   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

212278 Posts
Default

Bob has a huge.. Wow, for a moment I saw you are talking about our Bob.. (RDS)

- all odd squares are 1 mod 8 (the end of their binary form is ...x001)
- all even squares are 0 mod 4 (the end of bla bla is ..x00).
So, if the former but last bit is 1, the number is not perfect square.

Now the real interesting question would be if Alice says she doesn't know, and she keeps asking Bob, till eventually he tells her the most part (or all) the number. Can she answer efficiently? That would be interesting to solve, as a puzzle.

Last fiddled with by LaurV on 2012-04-28 at 11:32
LaurV is online now   Reply With Quote
Old 2012-04-28, 11:48   #3
jnml
 
Feb 2012
Prague, Czech Republ

22·41 Posts
Default

Quote:
Originally Posted by LaurV View Post
Bob has a huge.. Wow, for a moment I saw you are talking about our Bob.. (RDS)
LOL

Quote:
- all odd squares are 1 mod 8 (the end of their binary form is ...x001)
- all even squares are 0 mod 4 (the end of bla bla is ..x00).
So, if the former but last bit is 1, the number is not perfect square.
On a nit picking side note, mod 8 is an overkill ;-)

Quote:
Now the real interesting question would be if Alice says she doesn't know, and she keeps asking Bob, till eventually he tells her the most part (or all) the number. Can she answer efficiently? That would be interesting to solve, as a puzzle.
Hmm. Now, I'm puzzled ;-) Just guessing: No. (?)
jnml is offline   Reply With Quote
Old 2012-04-28, 16:31   #4
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31×43 Posts
Default

If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.

If the "1" is found in the even bit position, the next two more significant bits bits must be zero (the 001 string) otherwise the number is not square.

Otherwise you will need more than half of the bit representation of the number in order to know whether it is a perfect square or not (in the worst situation you will need the entire number). If the number is so large that cannot be sent from Bob to Alice, she will not be able to answer the question.
alpertron is offline   Reply With Quote
Old 2012-04-28, 17:21   #5
jnml
 
Feb 2012
Prague, Czech Republ

22×41 Posts
Default

Quote:
Originally Posted by alpertron View Post
If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.
Did you mean "least significant bit set" instead of "not set"?

Otherwise it doesn't seem to work:
Code:
 pos 3210
bits 1001 // 9
Least significant bit not set is at position 1, which is an odd number - but 9 == 32.
jnml is offline   Reply With Quote
Old 2012-04-28, 17:27   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011101001002 Posts
Default

He counts from 0 being the LSB bit, as in ...n2 * 22 + n1 * 21 + n0 * 20
Batalov is offline   Reply With Quote
Old 2012-04-28, 17:28   #7
jnml
 
Feb 2012
Prague, Czech Republ

22×41 Posts
Default

Quote:
Originally Posted by Batalov View Post
He counts from 0 being the LSB bit, as in ...n2 * 22 + n1 * 21 + n0 * 20
Me too AFAICS.
jnml is offline   Reply With Quote
Old 2012-04-28, 17:44   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

5×7×11×23 Posts
Default

Quote:
Originally Posted by jnml View Post
Me too AFAICS.
He wants to say "the number of zeroes at the end must be even and after the first 1 (counting from the right, i.e. from the end) there must be another two (at least) zeros (i.e. in front of it, to the left)" to (have a chance to) be a square. Which is right. That is, the last "1" in the normal order from left to right, as you read the number, that is the rightmost "1", must be preceded by at least 2 zeroes and followed by an even number of zeroes. Otherwise there is no way to be a square. There is always a confusion when you say "set bit", "clear bit", "reset bit", bla bla. Not everybody understand that the bit is in 1 or in 0.

edit: like this ......xxxxxxx001*, where the * can be replaced with nothing, or with an even number of zeroes.
edit2: xxxx from above it is always a triangular number, so if you can test this fast... :P

Last fiddled with by LaurV on 2012-04-28 at 17:52
LaurV is online now   Reply With Quote
Old 2012-04-28, 17:54   #9
jnml
 
Feb 2012
Prague, Czech Republ

22×41 Posts
Default

Quote:
Originally Posted by LaurV View Post
He want to say "the number of zeroes at the end must be even and after the first 1 (counting from the right, i.e. from the end) there must be another two (at least) zeros (i.e. in front of it, to the left)" to be a square. There is always a confusion when you say "set bit", "clear bit", "reset bit", bla bla. Not everybody understand that the bit is in 1 or in 0.
I believe I understand that and I agree (odd number of right trailing zeroes means the factorization will include an odd power of 2 which a perfect square cannot have).

I still think that both the above from me and quoted from you means the same which is "the index of the right most set bit must be even (not odd)", while alpertron wrote "not set". I think it's just that he made a simple typo, nothing more. (I produce them hundred times a day in code ;-)
jnml is offline   Reply With Quote
Old 2012-04-28, 18:04   #10
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Code:
for(x=1,100,print(binary(x^2)))
science_man_88 is offline   Reply With Quote
Old 2012-04-28, 18:56   #11
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24658 Posts
Default

Quote:
Originally Posted by alpertron View Post
If you number the least significant bit as bit zero and scan it from LSB to MSB, you can say with 100% certainty that if the least significant bit not set is in an odd position, the number is not a perfect square.
Sorry, it is not "not set", it is "set".
alpertron is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Perfect square in Fermat al3ndaleeb Miscellaneous Math 50 2015-06-17 18:42
Next perfect square after 2^n. soumya Miscellaneous Math 1 2013-03-28 02:06
Square of Primes davar55 Puzzles 9 2008-05-21 12:54
red square Fusion_power Puzzles 14 2008-04-25 11:37
Identifing perfect squares and calculating square roots.. dsouza123 Math 2 2003-07-19 17:17

All times are UTC. The time now is 12:20.

Fri Oct 23 12:20:55 UTC 2020 up 43 days, 9:31, 0 users, load averages: 1.42, 1.40, 1.38

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.