Interesting puzzle I found

[PhysicForumz]

A natural integer N can be written as x mod p, for instance:

N... 1 2 3 4 5 6 7 8 9 10 11 12

p=2 1 2 1 2 1 2 1 2 1 2 1 2

p=3 1 2 3 1 2 3 1 2 3 1 2 3

p=5 1 2 3 4 5 1 2 3 4 5 1 2

p=7 1 2 3 4 5 6 7 1 2 3 4 5

Etc.

The puzzle is quite difficult to state in this format but I'll have a go:

You choose any value x from each row of mod p (up to the maximum value of p, in the above case 7) and eliminate them. You have to find the minumum number N where it is impossible to eliminate all values of N.

Examples:

For p=2, the minimum N is 2. This is because eliminating any value of x (1 or 2), you will always have one remaining.

N... 1 2 3 4 5 6 7 8 9 10 11 12

p=2 1 2For p=3.

N... 1 2 3 4 5 6 7 8 9 10 11 12

p=2 1 2 1

p=3 1 2 3

Having a minimum of N=3 would not work: if you chose x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then you eliminate x=2 in the p=3 row and you eliminate them all.

N... 1 2 3 4 5 6 7 8 9 10 11 12

p=2 1 2 1 2

p=3 1 2 3 1

Having a minimum of N=4 would work however. There is no combination of x you could use to eliminate all values of N. For instance, with x=1 in the p=2 row, you'd eliminate N=1 and N=3. Then whether you choose x=2 or x=1 on the p=3 row, you'd have one left. I.e N=4

For p=5.

N... 1 2 3 4 5 6 7 8 9 10 11 12

p=2 1 2 1 2 1 2

p=3 1 2 3 1 2 3

p=5 1 2 3 4 5 1

I'll leave this to you, but you could try N=6. Try some combinations of x on each row. Is it possible to eliminate every value of N with N=6? (Answer is no :p)

The question is: how do you generalise this up to any p? E.g. how would you find out the minimum N needed when p = 41? What about when p = 211? Etc.

I've had a go, but it gets very tricky after a while trying to eliminate every value of N and finding all the combinations of x to use! I've started to make a program to do this for higher values of p!

Tell me if you need any clarifications / I haven't explained the problem properly

 

[bpet]

To rephrase the question, you're asking what is the largest N such that
$$\{1,...,N-1\} \subseteq \bigcup_{j=1}^k(r_j+p_j\mathbb{Z})$$ for some values $r_j$ and where $p_j$ is the jth prime number?