20120428, 10:41  #1 
Feb 2012
Prague, Czech Republ
251_{8} 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? ;) 
20120428, 11:31  #2 
Romulan Interpreter
Jun 2011
Thailand
9265_{10} 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 20120428 at 11:32 
20120428, 11:48  #3  
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Quote:
Quote:
Quote:


20120428, 16:31  #4 
Aug 2002
Buenos Aires, Argentina
1342_{10} 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. 
20120428, 17:21  #5  
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Quote:
Otherwise it doesn't seem to work: Code:
pos 3210 bits 1001 // 9 

20120428, 17:27  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×4,663 Posts 
He counts from 0 being the LSB bit, as in ...n_{2} * 2^{2} + n_{1} * 2^{1} + n_{0} * 2^{0}

20120428, 17:28  #7 
Feb 2012
Prague, Czech Republ
13^{2} Posts 

20120428, 17:44  #8 
Romulan Interpreter
Jun 2011
Thailand
5×17×109 Posts 
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 20120428 at 17:52 
20120428, 17:54  #9  
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Quote:
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 ;) 

20120428, 18:04  #10 
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Code:
for(x=1,100,print(binary(x^2))) 
20120428, 18:56  #11 
Aug 2002
Buenos Aires, Argentina
2·11·61 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Perfect square in Fermat  al3ndaleeb  Miscellaneous Math  50  20150617 18:42 
Next perfect square after 2^n.  soumya  Miscellaneous Math  1  20130328 02:06 
Square of Primes  davar55  Puzzles  9  20080521 12:54 
red square  Fusion_power  Puzzles  14  20080425 11:37 
Identifing perfect squares and calculating square roots..  dsouza123  Math  2  20030719 17:17 