Pseudonymous Socks

Laura Charlotte Graham has upcoming exams and wants to know how long her personalised monogrammed sock collection will last before she has to wash them. Unfortunately she hasn't had time to fold them, so her collection is in a random pile. She starts to pick out socks, one-by-one:

How many days until she runs out?


author: Will Earley

The title, thumbnail (some coloured gaussian noise) and the text all hint towards the idea of (pseudo)randomness. The text also suggests that Laura's initials, LCG, are important. Searching for 'lcg random', or even just lcg and looking a bit further down the results, we find that an LCG is a type of PRNG, pseudo-random number generator, where each term is generated like so (for three free parameters, a, c and m):

We then look to the image. We can identify each sock with a term in the LCG sequence via their hex codes (#d5eb51, #c94c59 and #ae87a1, or 14019409, 13192281 and 11437985 in decimal notation). Thus we have three terms, giving us two simultaneous equations from which we can find two of the three parameters. We can fix another parameter by realising that the RGB colour space has size 2^24=16777216, giving the simplest choice for m.

Solving the simultaneous equations is slightly trickier due to the modular arithmetic component, but it can be done, e.g. with the following mathematica code:

f[x_, y_, z_] := Reduce[{y == a x + c, z == a y + c}, {a, c}, Modulus -> 2^24]

Yielding a=365129 and c=64 (up to irrelevant additive constants). We can finally solve the puzzle, which asks how many days of socks Laura has left. Assuming she uses one pair per day and that she has no duplicate pairs, then the number of pairs amounts to the length of the cycle, which can be found with, e.g., the following python code:

lcg = lambda x: (365129*x+64) % 2**24
x0 = 14019409
x = lcg(x0)
n = 1
while x != x0:
    x = lcg(x)
    n += 1

Thus the answer is 2097152.