mersenneforum.org Perfect square or not?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-28, 10:41 #1 jnml   Feb 2012 Prague, Czech Republ 132 Posts 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? ;-)
 2012-04-28, 11:31 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 3×3,049 Posts 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
2012-04-28, 11:48   #3
jnml

Feb 2012
Prague, Czech Republ

132 Posts

Quote:
 Originally Posted by LaurV 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. (?)

 2012-04-28, 16:31 #4 alpertron     Aug 2002 Buenos Aires, Argentina 32·149 Posts 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.
2012-04-28, 17:21   #5
jnml

Feb 2012
Prague, Czech Republ

A916 Posts

Quote:
 Originally Posted by alpertron 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.

 2012-04-28, 17:27 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100001010112 Posts He counts from 0 being the LSB bit, as in ...n2 * 22 + n1 * 21 + n0 * 20
2012-04-28, 17:28   #7
jnml

Feb 2012
Prague, Czech Republ

132 Posts

Quote:
 Originally Posted by Batalov He counts from 0 being the LSB bit, as in ...n2 * 22 + n1 * 21 + n0 * 20
Me too AFAICS.

2012-04-28, 17:44   #8
LaurV
Romulan Interpreter

Jun 2011
Thailand

216738 Posts

Quote:
 Originally Posted by jnml 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

2012-04-28, 17:54   #9
jnml

Feb 2012
Prague, Czech Republ

2518 Posts

Quote:
 Originally Posted by LaurV 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 ;-)

 2012-04-28, 18:04 #10 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts Code: for(x=1,100,print(binary(x^2)))
2012-04-28, 18:56   #11
alpertron

Aug 2002
Buenos Aires, Argentina

53D16 Posts

Quote:
 Originally Posted by alpertron 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".

 Similar Threads Thread Thread Starter Forum Replies Last Post al3ndaleeb Miscellaneous Math 50 2015-06-17 18:42 soumya Miscellaneous Math 1 2013-03-28 02:06 davar55 Puzzles 9 2008-05-21 12:54 Fusion_power Puzzles 14 2008-04-25 11:37 dsouza123 Math 2 2003-07-19 17:17

All times are UTC. The time now is 11:36.

Tue Jan 19 11:36:49 UTC 2021 up 47 days, 7:48, 0 users, load averages: 1.48, 1.48, 1.58