Solving Lucy's secret number puzzle

DataGenetics proposed a neat number puzzle:

You are at a party and overhear a conversation between Lucy and her friend. In the conversation, Lucy mentions she has a secret number that is less than 100. She also confesses the following information:
"The number is uniquely describable by the answers to the following four questions:"

Is the number divisible by two?

Is the number divisible by three?

Is the number divisible by five?

Is the number divisible by seven?

She then proceeds to whisper the answers to these questions to her friend. Unfortunately, because of the ambient noise at the party, you only hear the answer to one of the questions. However, knowing just this one answer allows you to determine Lucy’s secret number.

Questions

Which question and answer did you overhear?

If the answer to this question is “Yes”, what is Lucy’s secret number?

(Tommaths on Twitter pointed it out to me as something to pose at the next Bletchley MathsJam he organises.)

Rather than solve the puzzle by hand, I reached for a computational approach (implemented in Python).

My approach is to take all the numbers from 1–100 and calculate the signature for each: the signature is the answer to Lucy's four questions.

def signature(n):
    return ( n % 2 == 0
           , n % 3 == 0
           , n % 5 == 0
           , n % 7 == 0
           )

The question is about going from the signature to a unique number, so I want to find, for each signature, which numbers have that signature.

I do that by going through all the numbers and generating the signature for each one. I store the results in a dict called signatures which has a key of the signature and a value which is a list of all the numbers with that signature.

import collections

signatures = collections.defaultdict(list)
for i in range(1, 100):
    signatures[signature(i)] += [i]

(I use the collections.defaultdict just so I don't have to bother checking for non-existent keys in the loop.)

I can then see which signatures have just one number:

[(s, ns) for s, ns in signatures.items() if len(ns) == 1]

# -> [((False, False, True, True), [35]), ((True, False, True, True), [70])]

Only two signatures have unique numbers: False, False, True, True for 35 and True, False, True, True for 70. Those signatures are the same, except for the first question ("is the number divisible by 2?").

So that's the answer:

You overheard the first question.
If you heard, "Yes," Lucy's number is 35.

Sai De Silva Photo by Sai De Silva on Unsplash.

Solving Lucy's secret number puzzle

Questions

Neil Smith