[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.

[Guest]

Password is: BUGLE

Integer is 992

Don't know the other integer.

[superprismatic]

Password is: BUGLE

Integer is 992

Don't know the other integer.

Answer to the second is *MUCH* harder!

[Guest]

bugle

At first I got bugpi, but then found a way to up the precision a little on the root.

[Guest]

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.

[dms172]

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

[Guest]

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?

[bushindo]

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

[bushindo]

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 )² = 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

K² + 2*K*S + S² = 0 modulo 1

2*K*S + S² = 0 modulo 1 since K² is an integer (Equation 1)

Expand this back into a normal equation

K = i * ( 1 - S^² )/( 2*S) where i is some integer (Equation 2)

Let i = 10^L+1 * ( 2*S)/( 1 - S^². That is, we let i equal to the the floor function of the inverse of ( 1 - S^² )/( 2*S) multiplied by 10^L+1. In that case, K = 10^L+1. We can plug K and S back into equation 1, and derive an N = (K + S )² 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)² = ( K² + 2*K*S + S² ) <--- 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)², which reduces down to 2R/K = 2R/10^{L + 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 = ( 10^{L + 1} + S )². Apply the floor function if needed.

3) This N is your desired number.

[bushindo]

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 = 10^L+1. The real number x that contains the sub-sequence S in its square root is

x = (K + S)^L+1 = K² + 2*K*S + S²

We approximate this with the integer N = K² + 2*K*S, which essentially amount to applying the floor function to x. Note that because we choose K = 10^L+1, N is guaranteed to be an integer. The error term is S²/(K + S)². 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

[Guest]

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)²

x = y² + 2yr + r²

In addition, we know that y is integral, so we know that x-y² = y.

Substituting, we know that

2yr + r² = y

2yr - y + r² = 0

y(2r - 1) + r² = 0

y = -(r²/(2r-1))

So, if we minimize e to 0, we can obtain an approximation of y:

y = -(0.4960314960²/(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)² (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...

[Guest]

Check that real quick...the following:

In addition, we know that y is integral, so we know that x-y² = y.

Should have read:

We know that BOTH X AND Y are integral. So we know that x-y² = y.

[superprismatic]

Check that real quick...the following:

Should have read:

We know that BOTH X AND Y are integral. So we know that x-y² = y.

Please explain further. If x and y are both integral, all I can see is that x-y² is integral.

[Guest]

Please explain further. If x and y are both integral, all I can see is that x-y² 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.