Найдите наибольшее натуральное число десятичной записи которая все цифры различны и сумма любых двух из них является простым числом

Сумма двух различных десятичных цифр не превосходит 9+8=17.

Далее, пусть в числе есть цифра 0, тогда в нем не может быть цифры 4, потому что 0+4 = 4 - составное. Выпишем по этой логике всю таблицу несовместимостей (1 - не простое число)

Несовместимы с 
0: 1, 4, 6, 8, 9
1: 0, 3, 5, 7, 8, 9
2: 4, 6, 7, 8
3: 1, 5, 6, 7, 9
4: 0, 2, 5, 6, 8
5: 1, 3, 4, 7, 9
6: 0, 2, 3, 4, 8, 9
7: 1, 2, 3, 5, 8, 9
8: 0, 1, 2, 4, 6, 7
9: 0, 1, 3, 5, 6, 7

Наибольшее двузначное видно легко - это 98.

Можно ли выбрать трехзначное число? Заметим, что в этом трехзначном числе
1) сумма первой и второй цифры - простое число
2) сумма второй и третьей цифры - простое число

Если оба этих простых числа - нечетные, то первая и третья цифра обязаны иметь одинаковую четность. А сумма таких цифр будет четная, и может быть простой лишь в случае 0+2. Заметим, что с 0 и 2 совместимы цифры 3 и 5, поэтому кандидат в наибольшие трехзначные числа : 520

Кстати, это же число получится, если мы предположим, что хотя бы одна из сумм (первая+вторая цифры) и (вторая+третья цифры) четна. Тогда эти цифры будут 0 и 2, и третью возможную цифру мы также будем выбирать из 3 и 5

Итак у нас всего две совместимых тройки (3,2,0) и (5,2,0). Совместимую четверку мы из них не сделаем, потому что 3 несовместимо с 5

Отсюда мы понимаем, что трехзначное число - наш предел. И наибольшее возможное - это 520