theburningmonk.com

Prob­lem

The square root of 2 can be writ­ten as an infi­nite con­tin­ued fraction.

The infi­nite con­tin­ued frac­tion can be writ­ten, ?2 = [1;(2)], (2) indi­cates that 2 repeats ad infini­tum. In a sim­i­lar way, ?23 = [4;(1,3,1,8)].

It turns out that the sequence of par­tial val­ues of con­tin­ued frac­tions for square roots pro­vide the best ratio­nal approx­i­ma­tions. Let us con­sider the con­ver­gents for ?2.

Hence the sequence of the first ten con­ver­gents for ?2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

What is most sur­pris­ing is that the impor­tant math­e­mat­i­cal constant,

e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of con­ver­gents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of dig­its in the numer­a­tor of the 10^th con­ver­gent is 1+4+5+7=17.

Find the sum of dig­its in the numer­a­tor of the 100^th con­ver­gent of the con­tin­ued frac­tion for e.

Solu­tion

If you look at the con­ver­gents of ?2 and the numer­a­tors in the con­ver­gents of e, you’ll see a pat­tern emerging:

1    +    2    *   1    =    3

2    +    3    *   2    =    8

3    +    8    *   1    =    11

8    +   11   *   1    =    19

11  +   19   *   4    =    87

If you look at the sequence of numer­a­tors in the con­ver­gents of e ( 2, 3, 8, 11, … ) and the sequence of num­bers in the con­ver­gents of ?2 ( 1, 2, 1, 1, 4, 1, … ), given the cur­rent numer­a­tor ( n ) and the pre­vi­ous numer­a­tor ( n-1 ) in the sequence and the cor­re­spond­ing num­ber in the con­ver­gents of ?2 ( i )the next numer­a­tor ( n+1 ) can be cal­cu­lated using the formula:

( n+1) = ( n-1 ) + n * i

Once we have this for­mula to work with, the rest is sim­ple, the solu­tion runs in 7 mil­lisec­onds on my machine.

Prob­lem

Con­sider the frac­tion, n/d, where n and d are pos­i­tive inte­gers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper frac­tions for d <= 8 in ascend­ing order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the frac­tion imme­di­ately to the left of 3/7.

By list­ing the set of reduced proper frac­tions for d <= 1,000,000 in ascend­ing order of size, find the numer­a­tor of the frac­tion imme­di­ately to the left of 3/7.

Solu­tion

This prob­lem is fairly easy, given that the answer we’re look­ing for much be very close to 3 / 7 (0.4285714286) I sim­ply iter­ate through the denom­i­na­tors, d, and find the clos­est numer­a­tor, n, which will pro­duce a value less than 3 / 7. Then fil­ter the set so we end up with only the n, d pairs that have a GCD of 1 and pick the numer­a­tor from the n, d pair whose n / d frac­tion is the biggest.

Prob­lem

Each char­ac­ter on a com­puter is assigned a unique code and the pre­ferred stan­dard is ASCII (Amer­i­can Stan­dard Code for Infor­ma­tion Inter­change). For exam­ple, upper­case A = 65, aster­isk (*) = 42, and low­er­case k = 107.

A mod­ern encryp­tion method is to take a text file, con­vert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advan­tage with the XOR func­tion is that using the same encryp­tion key on the cipher text, restores the plain text; for exam­ple, 65 XOR 42 = 107, then 107 XOR 42 = 65.

For unbreak­able encryp­tion, the key is the same length as the plain text mes­sage, and the key is made up of ran­dom bytes. The user would keep the encrypted mes­sage and the encryp­tion key in dif­fer­ent loca­tions, and with­out both “halves”, it is impos­si­ble to decrypt the message.

Unfor­tu­nately, this method is imprac­ti­cal for most users, so the mod­i­fied method is to use a pass­word as a key. If the pass­word is shorter than the mes­sage, which is likely, the key is repeated cycli­cally through­out the mes­sage. The bal­ance for this method is using a suf­fi­ciently long pass­word key for secu­rity, but short enough to be memorable.

Your task has been made easy, as the encryp­tion key con­sists of three lower case char­ac­ters. Using cipher1.txt (right click and ‘Save Link/Target As…’), a file con­tain­ing the encrypted ASCII codes, and the knowl­edge that the plain text must con­tain com­mon Eng­lish words, decrypt the mes­sage and find the sum of the ASCII val­ues in the orig­i­nal text.

Solu­tion

Prob­lem

A com­mon secu­rity method used for online bank­ing is to ask the user for three ran­dom char­ac­ters from a pass­code. For exam­ple, if the pass­code was 531278, they may ask for the 2nd, 3rd, and 5th char­ac­ters; the expected reply would be: 317.

The text file, keylog.txt, con­tains fifty suc­cess­ful login attempts.

Given that the three char­ac­ters are always asked for in order, analyse the file so as to deter­mine the short­est pos­si­ble secret pass­code of unknown length.

Solu­tion

This prob­lem is actu­ally solved much eas­ier by hand with pen and paper, but regard­less here’s a F# solu­tion to the problem.

Prob­lem

Some pos­i­tive inte­gers n have the prop­erty that the sum [ n + reverse(n) ] con­sists entirely of odd (dec­i­mal) dig­its. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such num­ber­sre­versible; so 36, 63, 409, and 904 are reversible. Lead­ing zeroes are not allowed in either n or reverse(n).

There are 120 reversible num­bers below one-thousand.

How many reversible num­bers are there below one-billion (10⁹)? 

Solu­tion

The solu­tion I have posted here solves the prob­lem but it takes a good 15 mins or so to run so doesn’t meet the 1 minute rule.. unfor­tu­nately brute force is the only way I know how to solve this problem :-(