superprismatic Posted August 20, 2009 Report Share Posted August 20, 2009 Members of a certain gang communicate with each other by means of the following system. The square root of an agreed-upon integer is extracted and carried out to a number of decimal places equal to the length of the message. Then each letter of the message is advanced (cyclically) in the normal alphabetic sequence a number of places given by the corresponding digit of the decimal part. For example, if the number agreed upon were 2, the word STOP would be enciphered as WUSR since Sqrt(2)=1.4142 to four decimal places. One day a detective found the following message on the body of a gangster slain by a member of a rival mob: TJYSZPVM OS FBIPI. He assumed (correctly) that this began PASSWORD IS. What is the password? SUPERPRISMATIC ANECDOTE ABOUT THIS: I know of two solutions to this -- the one Penney intended as well as one that two smart co-workers of his found. They found a 31-digit integer which also gave a (different) common English word as the password. For this to happen, of course, the fractional part of its square root must begin with the same ten decimal digits that Penney's gave, then somehow differ in the next five. A super-hard secondary problem would be to find this 31-digit number. By the way, I don't know what that 31-digit number is -- I only know what password it produces. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 20, 2009 Report Share Posted August 20, 2009 Password is: BUGLE Integer is 992 Don't know the other integer. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 21, 2009 Author Report Share Posted August 21, 2009 Password is: BUGLE Integer is 992 Don't know the other integer. Answer to the second is *MUCH* harder! Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 bugleAt first I got bugpi, but then found a way to up the precision a little on the root. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 Answer to the second is *MUCH* harder! Yeah, I don't know how to find that. I wrote a program to search out these passwords. I'm afraid 31 digits is too much for it though. I got ZZZAI for N = 253016616, that's only 9 digits, and my program is spitting out the wrong letters : it instead says ZZCLG; Maybe it's a round off error or something. The highest number I bothered checking was 363948563454 which gave a password: ZZZGH It's odd that ZZZ is so common, I've seen this for many integers. I'm not sure if I can trust my calculator. Quote Link to comment Share on other sites More sharing options...
0 dms172 Posted August 21, 2009 Report Share Posted August 21, 2009 (edited) Eagle .496031496011244 pretty easy to find. each letter fbipi has 9 others that go with it. then you look for a word. F B I P I E A H O H D Z G N G C Y F M F B X E L E A W D K D z V C J C Y U B I B X T A H A W R Z G Z Edited August 21, 2009 by dms172 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 21, 2009 Report Share Posted August 21, 2009 Eagle .496031496011244 pretty easy to find. each letter fbipi has 9 others that go with it. then you look for a word. F B I P I E A H O H D Z G N G C Y F M F B X E L E A W D K D Z V C J C Y U B I B X T A H A W S Z G Z How do you know it isn't AWAKE? I'm sure there are many words you can form by taking one letter from each column. How about CYCLE? Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 21, 2009 Report Share Posted August 21, 2009 (edited) F B I P I E A H O H D Z G N G C Y F M F B X E L E A W D K D Z V C J C Y U B I B X T A H A W S Z G Z How do you know it isn't AWAKE? I'm sure there are many words you can form by taking one letter from each column. How about CYCLE? AWAKE and CYCLE would have worked. And so would BADGE, CABOB, and CABLE. Claim: For any finite decimal sequence S of length L (i.e. S = .34566554, S = .23123124, ...), there exist a integer number N such that the square root of N includes the subsequence S. Proof: Imagine the plot of sqrt(x), x being a real number. This plot is continuous, and monotonically increasing from 0 to infinity. If we take g(x) = sqrt(x) modulo 1 (basically taking only the part behind the decimal point), then the range of g(x) goes between 0 and 1. g(x) increases from 0 to 1, then cycles over back to 0 and increases again, this continues ad infinitum. By continuity, it is not difficult to see that we can easily find a real number, x, such that sqrt(x) modulo 1 includes the subsequence S. Our problem is that only integers, N, are allowed. So the graph of g(N) looks very much like g(x), except that it is only evaluated at discrete integers. The overall properties of g(N) remains the same in that it increases from 0 to 1, and then cycles back to 0 and increases again. Without loss of generality, let's say that our subsequence S = .12345678. In order for the claim to be false, g(N) must not fall within the interval I = [.12345678, .12345679) for any N. As N increases, g(N) must cycle through (0,1) monotonically, but with ever smaller step size increase. Eventually, the step size will become smaller than the interval length I, and will have to fall inside I, producing a N that satisfies the claim. This is an existence proof, meaning that while we know such an integer N exist for any subsequence S, we can't produce the number N. My guess is that if we quantity the step size as some function of N, then we can work out some sort of method to predict how many steps it would take before g(N) falls inside the desired interval I. That said, it seems that any word constructed from dms172's list might have been a password, since we just showed that for any arbitrary subsequence we can find a integer N that satisfies the original post. There are 5^10 possible words, but here are the non-gibberish words. fudge fugle fable facia fadge faena etape ethic eying eagle dwine dying dacha dagga cubic cuing cycle cable cabob cache cadge budge bugle build bwana babka badge asana asdic awake awing azine azine abaka abele wacke Edited August 21, 2009 by bushindo Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 22, 2009 Report Share Posted August 22, 2009 AWAKE and CYCLE would have worked. And so would BADGE, CABOB, and CABLE. Claim: For any finite decimal sequence S of length L (i.e. S = .34566554, S = .23123124, ...), there exist a integer number N such that the square root of N includes the subsequence S. Proof: Imagine the plot of sqrt(x), x being a real number. This plot is continuous, and monotonically increasing from 0 to infinity. If we take g(x) = sqrt(x) modulo 1 (basically taking only the part behind the decimal point), then the range of g(x) goes between 0 and 1. g(x) increases from 0 to 1, then cycles over back to 0 and increases again, this continues ad infinitum. By continuity, it is not difficult to see that we can easily find a real number, x, such that sqrt(x) modulo 1 includes the subsequence S. Our problem is that only integers, N, are allowed. So the graph of g(N) looks very much like g(x), except that it is only evaluated at discrete integers. The overall properties of g(N) remains the same in that it increases from 0 to 1, and then cycles back to 0 and increases again. Without loss of generality, let's say that our subsequence S = .12345678. In order for the claim to be false, g(N) must not fall within the interval I = [.12345678, .12345679) for any N. As N increases, g(N) must cycle through (0,1) monotonically, but with ever smaller step size increase. Eventually, the step size will become smaller than the interval length I, and will have to fall inside I, producing a N that satisfies the claim. This is an existence proof, meaning that while we know such an integer N exist for any subsequence S, we can't produce the number N. My guess is that if we quantity the step size as some function of N, then we can work out some sort of method to predict how many steps it would take before g(N) falls inside the desired interval I. That said, it seems that any word constructed from dms172's list might have been a password, since we just showed that for any arbitrary subsequence we can find a integer N that satisfies the original post. There are 5^10 possible words, but here are the non-gibberish words. fudge fugle fable facia fadge faena etape ethic eying eagle dwine dying dacha dagga cubic cuing cycle cable cabob cache cadge budge bugle build bwana babka badge asana asdic awake awing azine azine abaka abele wacke Here's your second number, and a third, and a four, and so on... In the last post we have an existence proof, namely that for any sequence S there exist an integer N such that sqrt(N) includes the subsequence S. This is the construction proof for deriving such an N. Let S be a finite sequence of decimals after the decimal point (S= .12345678, S = .45324543, etc. ). Let L be the length of S. We wish to find an integer K such that (K + S )2 = 0 mod 1 Of course, for finite S, there is no such integer K so that the equation above is exactly true. But we can get the differences between the two terms to be artitrarily small, which is good enough. Expand the equation above K2 + 2*K*S + S2 = 0 modulo 1 2*K*S + S2 = 0 modulo 1 since K2 is an integer (Equation 1) Expand this back into a normal equation K = i * ( 1 - S^2 )/( 2*S) where i is some integer (Equation 2) Let i = 10L+1 * ( 2*S)/( 1 - S^2. That is, we let i equal to the the floor function of the inverse of ( 1 - S^2 )/( 2*S) multiplied by 10L+1. In that case, K = 10L+1. We can plug K and S back into equation 1, and derive an N = (K + S )2 as the integer that satisfies the original post. Because of the truncation we did to i to make it an integer, these K and i do not make Equation 2 exactly equal. However, the error is very small, and let's examine it. Let R, 0 < R < 1, be the error remainder term such that (K + R + S)^2 is an integer. We can expand this term as (K + R + S)2 = ( K2 + 2*K*S + S2 ) <--- this is our estimate N + R( 2K + R + 2S ) <---- this is the integer distance from N to the next perfect square. The error in decimal term is R( 2K + R + 2S )/(K + R + S)2, which reduces down to 2R/K = 2R/10L + 1. As it is, the error is small enough in magnitude that it doesn't affect the subsequence S after the decimal point. So, the summary is 1) Select the sequence S of length L. 2) Construct N = ( 10L + 1 + S )2. Apply the floor function if needed. 3) This N is your desired number. Quote Link to comment Share on other sites More sharing options...
0 bushindo Posted August 22, 2009 Report Share Posted August 22, 2009 (edited) I just reviewed this, and I found that the construct proof can be simplified greatly. For any sequence S of length L after the decimal point (i.e. S = .12345678), we would like to construct an N such that sqrt(N) contains the subsequence S. Let K = 10L+1. The real number x that contains the sub-sequence S in its square root is x = (K + S)L+1 = K2 + 2*K*S + S2 We approximate this with the integer N = K2 + 2*K*S, which essentially amount to applying the floor function to x. Note that because we choose K = 10L+1, N is guaranteed to be an integer. The error term is S2/(K + S)2. Note that this error term is very small, even smaller than the smallest digit in S. We can arbitrarily make the error term even smaller by choosing a even larger K. Edited August 22, 2009 by bushindo Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 22, 2009 Report Share Posted August 22, 2009 So, taking a clue from bushindo I got the following without using a brute force method. Someone please correct me if I'm out in left field but it actually gave the correct answer so there has to be SOMETHING to it... The square root of a positive real number can be written root(x) = y + r such that y = floor(root(x)). Therefore 0 <= r < 1 and y is a non-negative integer. We are given an r=0.4960414960 + e (where e is the error). We can therefore write our problem as: x = (y+r)2 x = y2 + 2yr + r2 In addition, we know that y is integral, so we know that x-y2 = y. Substituting, we know that 2yr + r2 = y 2yr - y + r2 = 0 y(2r - 1) + r2 = 0 y = -(r2/(2r-1)) So, if we minimize e to 0, we can obtain an approximation of y: y = -(0.49603149602/(2(0.4960314960) - 1)) = 30.9999996350473750 We know that y is integral, so rounding gives us a y of 31. Substituting 31 into x=(y+r)2 (again keeping our e estimate of 0), we obtain an approximation of x to be 991.999999997023998016. Rounding to get 992, we obtain a value of root(992) to be 31.4960314960472440 Taking 47244 and applying it to the last five digits, we get BUGLE (note that at one point, instead of minimizing e to 0 for solving, I incorporated the e into the giant equation. When I did this, I noted that there was at least one denominator in some of my equations that were x.xxxx*10-30. Perhaps this is a clue to the 31 digit number?? I don't know about that...once I saw bushindo's posts I went down the above path... Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 22, 2009 Report Share Posted August 22, 2009 Check that real quick...the following: In addition, we know that y is integral, so we know that x-y2 = y. Should have read: We know that BOTH X AND Y are integral. So we know that x-y2 = y. Quote Link to comment Share on other sites More sharing options...
0 superprismatic Posted August 22, 2009 Author Report Share Posted August 22, 2009 Check that real quick...the following: Should have read: We know that BOTH X AND Y are integral. So we know that x-y2 = y. Please explain further. If x and y are both integral, all I can see is that x-y2 is integral. Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 22, 2009 Report Share Posted August 22, 2009 Please explain further. If x and y are both integral, all I can see is that x-y2 is integral. You're right. See, i told you that there was a pretty big hole in there somewhere I don't know where i leaped to that conclusion. Maybe i made the conclusion fit the answer. Maybe in this case, it just so happens that x - y^2 - y = 0 992 - 31^2 - 31 = 0 Or I worked backwards from somewhere. I don't know. That would suck that an invalid method twists and turns and actually gives the right answer. (I wanted to get 2yr + r^2 = y) because once I got there I was able to get to the answer. Quote Link to comment Share on other sites More sharing options...
Question
superprismatic
Members of a certain gang communicate
with each other by means of the
following system. The square root of
an agreed-upon integer is extracted
and carried out to a number of decimal
places equal to the length of the
message. Then each letter of the
message is advanced (cyclically) in
the normal alphabetic sequence a
number of places given by the
corresponding digit of the decimal
part. For example, if the number
agreed upon were 2, the word STOP
would be enciphered as WUSR since
Sqrt(2)=1.4142 to four decimal places.
One day a detective found the
following message on the body of a
gangster slain by a member of a rival
mob: TJYSZPVM OS FBIPI. He assumed
(correctly) that this began PASSWORD
IS. What is the password?
SUPERPRISMATIC ANECDOTE ABOUT THIS:
I know of two solutions to this --
the one Penney intended as well as
one that two smart co-workers of his
found. They found a 31-digit integer
which also gave a (different) common
English word as the password. For
this to happen, of course, the
fractional part of its square root
must begin with the same ten decimal
digits that Penney's gave, then
somehow differ in the next five.
A super-hard secondary problem would
be to find this 31-digit number. By
the way, I don't know what that
31-digit number is -- I only know
what password it produces.
Link to comment
Share on other sites
13 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.