На прошлой неделе в сообщении блога, озаглавленном Поиск закономерностей, я представил загадку. Я попросил своего подростка решить его, используя только ручку / карандаш и бумагу.

Головоломка

Два целых числа отличаются на 22. Каждое, умноженное на его преемник, дает восьмизначный палиндром. Что из двух меньше?

Три шага

Совместными усилиями человека и машины мы можем достичь большего, весело решая проблемы и находя новые закономерности. Давайте попробуем это в три этапа. Шаг (I) - это чисто человеческое усилие. Шаг (II) - это грубая сила машины. Шаг (III) - это золотая середина, совместные усилия.

Шаг I: человеческое усилие

В этом разделе представлены только человеческие усилия, без использования Интернета или компьютерных программ. Для начала нам нужно перевести головоломку с английского на язык математики.

Перевод

  • Пусть p и q будут двумя целыми числами с q ›p
  • Нам говорят p + 22 = q (p - меньшее из двух)
  • Преемник p - (p + 1), а q - (q + 1)
  • Пусть два палиндрома будут P = abcddcba и Q = wxyzzyxw
  • Наша цель - найти p

Учитывая эти факты, мы можем записать их в виде математических уравнений:

abcddcba и wxyzzyxw - два палиндрома, каждая буква которых обозначает цифру - каждый разный или частично перекрывающийся, мы не знаем.

Основы

Рискуя потерять нескольких читателей, я постараюсь быть максимально сговорчивым. Если вы уже знаете это, можете перейти к разделу Шаблоны обнаружения.

  • Целые числа - это целые числа или счетные числа. Хотя это не объясняется явно, эта головоломка включает в себя положительные целые числа.
-7, -8, -67 are a few negative integers
56, 117, 2938 are a few positive integers
  • Палиндром - это число, которое читается вперед и назад одинаково.
25744752, 5665, 77, 8 are integers that are palindromes
  • Преемник целого числа - это тот, который следует сразу после. При совместном обращении это два последовательных целых числа.
7 is the successor to 6. 
28 is a successor to 27.

Десятичное разложение

Любое целое число (в десятичной системе или десятичной системе) может быть выражено как сумма степеней 10. Например, десятичное разложение 5665 выглядит следующим образом:

Главные факторы

Любое целое число может быть выражено как произведение его простых множителей. Простое число делится на 1 и само себя. 2 - четное простое число. Остальные странные.

Prime factors of 5665 are 5, 11 and 103 because 5665 = 5 x 11 x 103

Выявление узоров

(I) Проверка делимости на 11

Интересен тест на делимость на 11. Для любого целого числа, читая слева направо, возьмите сумму альтернативных цифр этого числа. У вас должно получиться две суммы.

Если суммы различаются кратно 11, число делится на 11.

EXAMPLE: Take the number 947683 for instance
Alternate digits are S = {9, 7, 8} and T = {4, 6, 3}
The sum of S = 9 + 7 + 8 = 24 
The sum of T = 4 + 6 + 3 = 13
Their difference is (T - S) = (13 - 24) = 11 x (-1), divisible by 11
Therefore 947683 is divisible by 11
In fact, 947683 = 86153 x 11

(II) Последовательные целые числа

Четные целые числа делятся на 2. Нечетные целые числа - нет. Два дополнительных интересных факта о паре последовательных целых чисел:

1) One of them is odd, and the other even. Their product is even
2) They share no prime factors. Their highest common factor is 1

(III) Совершенные квадраты

Два последовательных целых числа имеют вид {2k, 2k + 1}, где k = {0, 1, 2, 3,…} Полный квадрат должен иметь форму {(2k) ², (2k + 1) ²} = {4k², 4k (k + 1) + 1}.

Полный квадрат делится в точности на 4, ИЛИ остается 1 в качестве остатка при делении на 4

(IV) Полный квадрат с окончанием на 5

Любопытный факт о полных квадратах, оканчивающихся на 5, заключается в том, что предпоследняя цифра всегда равна 2! Если число заканчивается на 5, квадрат всегда оканчивается на 25.

EXAMPLES: Say you want to find 45². The only arithmetic we need is 4x5 = 20. Then attach 25 to it. The answer is 20|25!
45² = 4(4+1)| 25 = 2025 
Other examples:
75² = 7(7+1)| 25 = 5625
115² = 11(12+1)| 25 = 13225
(10a+5)² = 100a² + 100a + 25 = 100a(a+1) + 25

Если вы посмотрите на десятичное расширение квадрата, заканчивающегося на 5, этот образец легко заметить. Обратите внимание, что независимо от того, что означает «a», результат будет оканчиваться на 25. Также другие цифры в числе являются просто произведением двух последовательных чисел (a) (a + 1), сдвинутых влево на две цифры, чтобы освободить место для 25!

(V) Квадратичный дискриминант

В квадратном уравнении ax² + bx + c = 0 дискриминант (греческий символ Delta), определяемый как Δ = ⎷ (b²- 4ac), должен быть полным квадратом. Мы хотим, чтобы решения x были целыми числами!

Δ представляет собой полный квадрат квадратного уравнения с целыми решениями

(VI) Палиндром с четным числом цифр

Каждый палиндром состоит из четырех пар целых чисел. Давайте, например, посмотрим на десятичное разложение P.

Каждый член делится на 11. Обратите внимание, что каждая цифра соединяется с другой идентичной цифрой в другом месте, так что их сумма {10000001, 100001, 1001, 11} делится на 11. Следовательно, P и Q должны делиться на 11. Мы можем распространить это на любой палиндром с четным числом цифр. Используя модульную арифметику и отношения сравнения, мы можем показать, что они делятся на 11. Это уникальный образец!

Палиндром с четным числом цифр делится на 11

Детективная работа

Начнем с цифр {a, w}, которые могут принимать любое из значений {0,1,2, ... 9}. Но могут ли они? Не совсем, потому что у нас есть несколько заманчивых подсказок!

Процесс ликвидации

Используя шаблон (II), и P, и Q должны быть четными. Таким образом, они должны начинаться (и заканчиваться) следующими цифрами {2, 4, 6, 8}. Я исключил {0}, потому что они не могут быть равны нулю, если мы хотим, чтобы палиндромы были восьмизначными! Итак, мы исключили {1, 3, 5, 7, 9}. Это сокращение сразу на 5/9 = 55,5%!

{a,w} = {2, 4, 6, 8}

P = p² + p - квадратное уравнение с целочисленными решениями. Используя Pattern (V), дискриминант должен быть идеальным квадратом. Сравнивая его с ax² + bx + c = 0, мы имеем

a = 1, b = 1, c = -P и Δ² = (b²- 4ac) = 1 + 4P

Используя шаблон (III), полные квадраты точно делятся на 4 или оставляют остаток 1 при делении на 4. Мы также знаем набор крайних правых цифр P и Q. Давайте проверим, каковы крайние правые цифры 1 + 4P.

P = {2bcddcb2, 4bcddcb4, 6bcddcb6, 8bcddcb8}
Δ²= 1 + 4 {2bcddcb2, 4bcddcb4, 6bcddcb6, 8bcddcb8}
Δ² ends in digits {9, 7, 5, 3}
There aren't any perfect squares that end in 7 or 3 because they are neither divisible by 4 nor leave a remainder 1 when divided by 4. We can apply the same logic to Q

P не может быть {4bcddcb4, 8bcddcb8}. И Q не может быть {4xyzzyz4, 8xyzzyx4}. Используя этот паттерн, нам снова удалось сократить возможности вдвое!

{a,w} = {2, 6}

Поскольку палиндром состоит из восьми цифр, числа p и q должны быть четырехзначными. Начиная с {a} = {6} для P, мы можем показать {w} = {0} для Q; противоречие! Давайте разберемся как.

Следуйте инструкциям в таблице 1. Возьмите, например, строку № 5, где {a, w} = {6}. Два последовательных числа (p, p + 1) могут оканчиваться на (… 2,… 3) или (… 7,… 8), если последняя цифра P должна быть 6. Начальные точки обозначают цифры, которых мы еще не знаем. знать.

Поскольку q = p + 22, окончание цифр для (q, q + 1) будет либо (… 4,… 5), либо (… 9,… 0). Ни одна из этих пар при умножении не дает нам a, w = {6} для Q. Используя эту логику, можно исключить все пары, кроме строк, выделенных зеленым. {a, w} не может быть {6}.

Мы сделали это снова, сократив пространство для решения вдвое!

Когда {a, w} = {2}, p оканчивается цифрами {1, 6}

{a,w} = {2}  which implies the following 
P = 2bcddcb2 and p = { ...1, ...6 } 
Q = 2xyzzyx2 and q = { ...3, ...8 }

Мы знаем самый большой и самый маленький восьмизначный палиндром, который начинается (и заканчивается) цифрой 2. Они связаны P (min, max) = {20000002, 29999992}. Мы можем определить ведущую (т.е., первую) цифру числа p, используя приближение, которое не меняет его крайнюю правую цифру.

Если p² + p = P, приблизительно p² ~ P и p ~ ⎷P

p находится в диапазоне p (min, max) = {⎷20000002, ⎷29999992} ~ [45 00, 55 00)

Я использовал шаблон (IV) - технически нам не нужен калькулятор, потому что 5500² = 55² x 10⁴ = 30250000 и аналогично 4500² = 45² x 10⁴ = 20250000.

Первые две цифры p входят в этот набор {45, 46, 47,…, 53, 54}. Обратите внимание, что я ex включил 55, потому что 55² ›29999992 и in включил 45, потому что 45²› 20000002. Мы можем записать это более компактно:

p = {4mn1, 4mn6, 5st1, 5st6}  m = {5,6,7,8,9} and s={0,1,2,3,4}

Используя Шаблон (II) и (VI), {2, 11} - простые множители P = p (p + 1) и Q = q (q + 1). Но p не может иметь в качестве простых множителей 2 и 11. Это потому, что они являются последовательными, их наивысший общий (простой) множитель равен 1. Таким образом, мы должны распределить {2, 11} между {p, p + 1}.

Случай 1: p нечетное

Если p нечетное, 11 - его простой множитель. В этом случае p + 1 четно и делится на 2

p = {4mn1} m = {5,6,7,8,9} or p = {5st1} s={0,1,2,3,4}

Рассмотрим p = 45n1 {m = 5}: применим критерий делимости на 11. n + 4 = 5 + 1, что дает нам n = 2. Для остальных {m, n} и {s, t} мы можем свести в таблицу возможные значения p. Если n ›9, мы отбрасываем число, потому что n - цифра!

Случай 2: p четно

Если p четно, оно делится на 2. В этом случае p + 1 нечетно, а 11 - его множитель.

p = {4mn6} m = {5,6,7,8,9} or p = {5st6} s={0,1,2,3,4}

Рассмотрим p = 45n6. В этом случае p + 1 = 45n7 делится на 11. n + 4 = 7+ 5, что дает нам n = 8. Для остальных {m, n} и {s, t} мы можем табулировать возможные значения p. . Опять же, если n ›9, мы отбрасываем число, потому что n - это цифра! Если p ›5470, мы его отбрасываем.

Возможные подозреваемые

Наша детективная работа почти завершена. Мы подошли к короткому списку подозреваемых (шестнадцать кандидатов). Могут быть один или несколько виновников, которые соответствуют шаблону!

p = { 4521, 4631, 4741, 4851, 4961, 5071, 5181, 5291, 5401 }
p = { 4586, 4696, 5026, 5136, 5246, 5356, 5466 }

Теперь можно вставить эти числа в карманный калькулятор и проверить. Например, давайте проверим p = 4521

p = 4521 
P = p(p+1) = 4521(4522) = 20443962
We can save ourselves some time with long multiplication by spotting more patterns! 
If we multiply the last two digits 21 x 22 = 462 
Similarly the first two digits 45 x 45 = 2025
Notice the first two digits of P are 20, and last two are 62
Since P isn't a palindrome, there is no need to check Q. We move on.

Я не знаю других закономерностей. Я исследовал простые множители, окончание предпоследних цифр (разряды десятков) и свойства последовательных целых чисел и палиндромов. Но у меня кончились идеи. Меня интересуют другие умные идеи по дальнейшему сокращению набора решений! Используя простые числовые шаблоны для целых чисел, нам удалось сократить пространство для сканирования. Гистограмма показывает, как произошло это снижение. Первоначальный счет был 9000, в итоге осталось 16.

Виновник

Оказывается, только p = 5291, q = 5313 обладают этим уникальным свойством, где они отличаются на 22, и каждое умножение на его преемника дает восьмизначный палиндром. Мы наконец решили проблему, найдя значения p, которые обладают этим свойством!

p = 5291 = (11 ⨯ 13 ⨯ 37)
p+1 = 5292 = (2² ⨯ 3² ⨯ 7²)
P = p(p+1) = 5291(5292) = 27999972 Bingo! a palindrome
  ⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤⏤
q = p + 22 = 5313 = (3 ⨯ 7 ⨯ 11 ⨯ 23)
q+1 = 5314 = (2 ⨯ 2657)
Q = q(q+1) = 5313(5314) = 28233282 Another palindrome!

Таблица 4: Кандидаты в палиндромный продукт. Только p = 5291, q = 5313 подходят под шаблон

Шаг II: вычислительная мощность

В этом разделе мы исследуем силу тактовой частоты гигагерц! Любой, у кого есть базовый опыт кодирования / программирования, может оценить разницу в скорости по сравнению с человеком с ручкой / бумагой.

Я использую MacBook с оперативной памятью 16 ГБ и процессором Intel Core i7 с тактовой частотой 2,5 ГГц.

Сколько восьмизначных палиндромов?

Ради любопытства давайте узнаем, сколько существует восьмизначных палиндромов. Следующий фрагмент кода дает ответ. Это занимает ~ 10,0 ± 0,2 с.

Ответ: существует 9000 восьмизначных целочисленных палиндромов

Как быстро?

Это очень медленно для простой программы. Современные ноутбуки имеют скорость обработки, которая легко превышает 10 миллиардов шагов или операций в секунду. Тактовый цикл процессора составляет примерно 0,3 нс (менее половины наносекунды). Но чтобы оценить, насколько быстро на самом деле работает машина, нам нужно что-то, к чему мы (как люди) можем относиться.

Мы понимаем и можем относиться к одной секунде (Одна Миссисипи). Допустим, мы произвольно назначаем 1 цикл ЦП (0,3 нс) равным одной секунде.

1 CPU cycle = (0.3 ns or 0.0000000003 s)  = 1 s

Учитывая эту шкалу, сколько времени потребовалось 10,0 секунд для создания всех восьмизначных палиндромов?

10s / 0.0000000003 = 1056 years!

Мы можем намного лучше генерировать и считать, если знаем, как выглядит палиндром. И мы, конечно, делаем. Мы знаем половину цифр (первые четыре или последние четыре), мы можем построить вторую половину. Давайте воспользуемся этим шаблоном, чтобы сгенерировать и подсчитать, сколько существует восьмизначных палиндромов.

P = 11000*i - 9900* (i//10) - 990 * (i//100) - 99*(i//1000)
i = [1000, ..., 9999]

Используя этот шаблон, мы можем сгенерировать и подсчитать их все за 4,0 ± 0,2 миллисекунды (мс), что является значительным (на три порядка) улучшением!

Грубая сила

Мы можем просканировать все восьмизначные палиндромы и проверить это свойство. Давайте посмотрим, сколько времени нужно, чтобы сгенерировать, проверить и найти целые числа, обладающие этим свойством. Программа представлена ​​ниже. Это занимает примерно (7,1 ± 0,3 мс)

Шаг III: Сотрудничество

Мы выполнили ручное упражнение в Шаге I. Нам удалось сократить пространство для решения вдвое, за три шага. К тому времени, как мы закончили, у нас было несколько кандидатов для проверки. Для решения поставленной задачи можно использовать любой или все шаблоны. Я решил начать здесь:

p = {4mn1, 4mn6, 5st1, 5st6}  m = {5,6,7,8,9} and s={0,1,2,3,4}

Давайте запрограммируем это и узнаем, сколько времени это займет! Фрагмент кода показан ниже. Требуется (55,6 ± 9 мкс), что в тысячу раз меньше!

Теперь давайте сравним, насколько быстро выполняется исполнение в человеческое время. Напомним, мы начали с 1056 лет, чтобы перечислить все восьмизначные палиндромы. Если посчитать, сколько времени, получится около 2 дней! Это замечательное сокращение, которое осталось незамеченным. Людям трудно представить себе как большие, так и малые числа.

56 μs ~ 2 days

Сотрудничайте, создавайте

Люди и машины - мощные сущности. Мы развили способность решать сложные проблемы с помощью наших навыков распознавания образов, способности к абстрактному мышлению и творческих талантов. Если мы будем сотрудничать с машиной, чтобы использовать ее сверхчеловеческую силу и интеллект, сотрудничество человека и компьютера составило бы выигрышную комбинацию!

использованная литература

  1. Некоторые задачи о простых факторах целых чисел - П. Эрдеш, Л. Селфридж, Illinois J. Math., Том 11, выпуск 3 (1967), 428–430. Ссылка на PDF
  2. Делимость на одиннадцать - Mudd Math Fun Facts
  3. Положительные числа k такие, что k * (k + 1) - палиндром. A028336 - OEIS, Патрик Де Гест
  4. Проблема впервые появилась в Mindsport, Sunday Times of India, автор: Мукул Шарма, начало 1990-х гг.
  5. Рост сотрудничества человека и компьютера, TED Talk 2012, Шьям Санкар
  6. Сообщение в блоге Coding Horror: Бесконечное пространство между словами, 2014, Джефф Этвуд

© ️ Venkat Kaushik 2020. Все права защищены.