Le Monde puzzle [#1048]

An arithmetic Le Monde mathematical puzzle:

A magical integer m is such that the remainder of the division of any prime number p by m is either a prime number or 1. What is the unique magical integer between 25 and 100? And is there any less than 25?

The question is dead easy to code

primz=c(1,generate_primes(2,1e6))
for (y in 25:10000)
  if (min((primz[primz>y]%%y)%in%primz)==1) print(y)

and return m=30 as the only solution. Bon sang but of course!, since 30=2x3x5… (Actually, the result follows by dividing the quotient of the division of a prime number by 2 by 3 and then the resulting quotient by 5: all possible cases produce a remainder that is a prime number.) For the second question, the same code returns 2,3,4,6,8,12,18,24 as further solutions. There is no solution beyond 30.

2 Responses to “Le Monde puzzle [#1048]”

  1. Hans W Borchers Says:

    You did not *prove* that 30 is a magical number, just gave some evidence for primes smaller than one million. It is quite easy to actually prove by hand that 4,6,8,12,18,24,30 are the only magical numbers up to 30. That there are no more magical numbers follows from Dirichlet’s theorem and the fact, if p1,p2,…,pn are the first n primes, that p_{n+1}^2 < p1*…*pn !

    • As in most of my mathematical puzzle resolutions here, I indeed do not solve the mathematical question! Although in this special case, it was indeed easy to demonstrate that all numbers returned were indeed magical. Thank you for the final argument.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.