Из чисел 1, 2, …, 1003 выбирают несколько так, чтобы разность никаких двух выбранных чисел не равнялась ни 4, ни 7. Какое наибольшее количество чисел можно выбрать?

Обозначим через \(a_n\) максимальное количество выбранных чисел среди первых \(n\) чисел. При добавлении очередного числа нужно учитывать, выбраны ли числа на 4 и 7 меньше него.

Для последовательного перебора чисел достаточно хранить информацию о последних семи выбранных или невыбранных числах. Если число \(n\) выбирается, то числа \(n-4\) и \(n-7\) выбирать нельзя. Такой динамический перебор даёт для отрезка \(1,2,\ldots,1003\) верхнюю границу

\[a_{1003}\le 457.\]

Осталось показать, что 457 чисел действительно можно выбрать. Рассмотрим числа, остатки которых при делении на 11 принадлежат множеству

\[\{0,1,2,3,10\}.\]

Внутри каждого полного блока из 11 последовательных чисел выбирается 5 чисел. Поскольку разности 4 и 7 соответствуют переходам между остатками, отличающимися на 4 или 7 по модулю 11, выбранные числа не имеют разности 4 или 7.

В первых 1001 числах содержится 91 полный блок по 11 чисел, поэтому выбирается \(91\cdot5=455\) чисел. Числа 1002 и 1003 имеют остатки 1 и 2 при делении на 11 и также могут быть добавлены; разность между ними равна 1.

Получаем \(455+2=457\) чисел.

Ответ: 457.