Как я проходил квест от Гугла

Многим знакомо утверждение, что Google рекламу не даёт. Но как же тогда фирма размещает объявления о наборе персонала? Вот один из способов, которыми действует Гугл.

9 июля 2004 года на магистрали из Сан-Франциско в Сан-Хосе (а чуть позже и ещё в некоторых городах США) появился рекламный щит, на котором был только следующий текст:

Там было написано: «{первое десятизначное простое число, найденное в последовательных цифрах e}.com». Этот рекламный щит и являлся частью рекрутинговой кампании Google. Те, кто смог найти нужное число, попадал на сайт, на котором давались ещё один адрес сайта и логин, а паролем был ответ ко второй задачке, которую тоже надо было решить. Справившимся со вторым испытанием и введшим пароль, предлагалось перейти на страницу подразделения исследований и разработок на сайте Google Labs. Там были размещены вакансии, а вместо приветствия надпись:

Google искал на работу людей с определёнными навыками, и очень хорошо довёл до них своё предложение. Не имеющие достаточной начальной подготовки отсеивались на нулевом этапе: они даже не понимали, о чём речь на этом рекламном щите. Ну и чтобы пройти далее, надо было уже обладать определёнными знаниями и навыками.

Причём, HR-щики Гугла пошли на этот квест, чтобы отобрать не столько тех, кто сможет пройти квест — сколько тех, кто не сможет пройти мимо плаката с задачей-загадкой и захочет найти ответ. Таким простым способом компания без труда отбирала не только кандидатов, знающих математику и умеющих программировать, но и людей с самым высоким коэффициентом любопытства.

Собственно, американская история про Гугл на этом заканчивается, и дальше начинается…

Однажды я делал ребус, в котором нужно было загадать отдельностоящую букву Е. Можно было просто написать букву «Е» и успокоиться. Но мне вспомнилось, что есть такое число e – число Эйлера, и можно было бы именно его и загадать. Но просто написать 2,71828 не очень интересно, и я пошёл дальше – сделал запрос в яндекс.

Мне почему-то первой выпала переведённая страничка про число «e» с англоязычной википедии. И там в самом конце упоминался упомянутый выше устроенный Гуглом квест.

В конце концов в ребусе я так и оставил «2,71828», но вот квест меня зацепил. Видимо, мой коэффициент любопытства зашкаливает, потому что мимо таких задачек я в принципе не могу пройти мимо.

Говорят, IQ развить практически невозможно, а вот любопытство — это такая черта, которую нужно прокачивать так же, как и уровень физической подготовки. Конечно же, мне захотелось попробовать решить все эти задачки самому (хотя устраиваться на работу в Гугл уже поздновато, да и не нужно) :).

В общем, нулевой уровень я прошёл: я понял, о чём идёт речь на рекламном щите, и задачка меня зацепила.

Самый простой, но при этом работающий подход к решению этой задачи – это забрутфорсить, то есть найти где-нибудь достаточное число знаков уже кем-то рассчитанного числа е, «порезать» его на последовательности из 10 знаков и по очереди пробовать их в качестве урла. Это можно сделать как при помощи простейшего скрипта, так и вообще вручную. То есть даже ни капли не надо быть математиком и/или программистом.

Более сложный, но имхо более привлекательный способ – написать программу, которая высчитает правильный ответ. То есть сама посчитает число e до нужной точности, «нарежет» его на кусочки, проверит их на простоту и найдёт самый первый из них. Конечно же, я решил пойти по второму пути :)

Для начала пришлось повнимательнее изучить несколько страничек с информацией про число e, в частности:

• Е (число) – на русскоязычной Википедии
• E (mathematical_constant) – на англоязычной Википедии (с которой всё и началось)

Они дали мне несколько интересных формул:

1. `e=\lim _{n\to \infty }\left(1+\frac {1}{n}\right)^{n} ` (второй замечательный предел)
2. `e = sum_(n=0)^oo(1)/(n!) = 1/(0!)+1/(1!)+1/(2!)+1/(3!)+1/(4!)+1/(5!)+cdots `
3. `e = 2+\frac{1} {1+\frac{1} {2+\frac{2} {3+\frac{3} {4+frac{4}\ldots} } } } `

Ещё в школе мы, заучивая число e, запомнили, что Лев Толстой два раза родился в 1828 году, а углы в равностороннем прямоугольном треугольнике 45+90+45 градусов. Но знания того, что число `e~=2,718281828459045... ` мне было недостаточно. Разве что можно было проверить несколько адресов (2718281828.com, 7182818284.com, 1828182845.com, 8281828459.com, 2818284590.com, 8182845904.com, 1828459045.com) и убедиться, что они не подходят.

Нужно было знать хотя бы первую тысячу знаков, чтобы устраивать среди них более-менее нормальный поиск. Заходя немного вперёд, скажу, что для прохождения квеста понадобилось всего 108 первых знаков. Но кто ж знал, что нужно так мало?

В принципе, это абсолютно не важно. Я думаю, если упереться рогом, то подобную задачу можно реализовать практически на любом языке программирования. Вот примеры, как разные программисты реализуют одну и ту же программу Hello World на более чем 600 различных языках и системах программирования.

Обычно языки не поддерживают работу с числами с такой большой точностью, все эти float, double, long и прочие long long в лучшем случае дадут пару десятков цифр, а мне надо тысячу. Значит, нужна так называемая "длинная арифметика", в данном случае арифметика произвольной точности.

Можно было, конечно, заморочиться и такую арифметику реализовать самому. Когда-то я такое даже делал на языке С++, а у участников олимпиад по программированию это вообще должно входить в базовые знания, и набивать с нуля алгоритмы работы с длинными числами надо уметь минут за 15 :) Но сейчас у меня была немного другая задача. Мне надо было это сделать достаточно простым и быстрым, но при этом точным способом.

Я решил использовать язык Java, в нём есть специальный класс BigDecimal для работы с большими числами, позволяющий хранить любые значения без ограничения на размер как целой, так и дробной части. Поэтому мне не придётся отвлекаться на изобретение колеса.

Если использовать «метод пристального вглядывания» и посмотреть на вторую из найденных мною формул, то можно заметить, что её, во-первых, довольно просто загнать в цикл. А во-вторых, в ней используются факториалы в знаменателе, из-за чего члены ряда будут быстро уменьшаться, а сам ряд быстро сходиться, а значит, нужная точность будет довольно быстро достигнута. Причём считать факториалы отдельно для каждого шага не придётся, он будет автоматически с каждым шагом «накапливаться» сам собой.

`e = sum_(n=0)^oo(1)/(n!) ~= 1/(0!)+1/(1!)+1/(2!)+1/(3!)+1/(4!)+1/(5!)+cdots+1/(N!) `

Основной вопрос был – сколько шагов цикла N надо сделать. Можно, конечно, задать нужную точность и на каждом шаге проверять, не получился ли очередной член ряда меньше заданной точности, но я просто тупо задал для начала четверть. Оказалось мало. Задал половину – много. Методом дихотомии пришёл к оптимальному значению. В моём случае оказалось, что для нахождения n цифр надо будет сделать ~n/3 шагов цикла.

Для поиска числа e я написал вот такую программку:

getPrime.java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.math.BigInteger;
 
public class getPrime
{
  public static void main(String[] args) 
  {
    var e=BigDecimal.ONE;
    var fact=BigDecimal.ONE;
    var mlrd=new BigInteger("1000000000");
    BigInteger e10=BigInteger.ZERO;
    String se;
 
    //ищем ~1000 знаков числа е
    for (int n=1; n<1000/3; n++) {
      fact=fact.multiply(BigDecimal.valueOf(n)); //вычисляем n!
      e=e.add((BigDecimal.ONE).divide(fact, 1000, RoundingMode.CEILING)); //прибавляем 1/n!
    }       
 
    //преобразуем в строку и последовательно нарезаем её на 10-значные числа 
    se=e.toString(); se=se.substring(2, Math.min(se.length(), 1000));
    for(int i=0; i<se.length()-10; i++) {
      e10=new BigInteger(se.substring(i,i+10)); //вырезаем 10 цифр
      //проверяем число на простоту встроенным вероятностным методом
      if (e10.isProbablePrime(1) && e10.compareTo(mlrd)==1) { break; }
    }
 
    //кандидат найден
    long probablePrime = e10.longValue();
    System.out.println(probablePrime+" ?");
 
  }
}

И она выдала мне: 7427466391 ?.

В принципе, на этом этапе уже можно было бы его проверить в качестве адреса 7427466391.com (и оно бы сработало, если бы сайт не перестал существовать в 2005 году через год после открытия!). Более того, когда я начинал решать эту задачу, мне уже точно был известен правильный ответ. Ну и, конечно же, я увидел, что нужное число моей программой было найдено. Можно было бы и остановиться. Но, как я уже говорил, мы не ищем лёгких путей. Поэтому мне предстояло доказать, что это число не вероятно, а абсолютно точно простое. И только после этого его использовать.

Итак, надо было проверить найденное число на простоту.

Оказалось, что практически все точные алгоритмы поиска простых чисел основаны на просеивании. Берётся весь диапазон чисел и из него вычёркиваются по различным правилам все точно не простые числа. В результате остаются только простые. Алгоритмов просеивания придумано уже довольно много – какие-то быстрее, какие-то используют меньше памяти – но суть от этого не меняется, надо отсеивать.

Я решил воспользоваться простейшим и самым старым алгоритмом – решетом Эратосфена. Мне предстояло организовать массив для хранения ~7,5 миллиардов признаков, является ли число с заданным порядковым номером простым или нет. Так как признак бинарный (да/нет), то на каждое число будет достаточно одного бита (false или true). Вначале массив будет пуст (все элементы будут 0), а потом будем «вычёркивать» составные числа, помечая их единичками. В конце работы алгоритма все простые числа останутся «нулями».

7,5 миллиардов битов – это очень много, а типа данных «бит» в java нет. Если попробовать объявить байтовый массив на 7,5 млрд, то, во-первых, компилятор ругнётся, что индекс массива не помещается в int, а во-вторых, даже если индекс уместить, то тупо не хватит памяти в куче, потому что 7,5 млрд байт это, на минуточку, 6 гигабайт. А может быть и больше, потому что byte, как выясняется, не такой уж и byte, и памяти на него системой выделяется не 8 бит, а больше.

Класс BitSet также не может сделать массив битов длиной больше, чем 2³² = 4 294 967 296, а мне надо 7 500 000 000, что почти в два раза больше. Можно было, конечно, разбить массив на несколько и переключаться между массивами в зависимости от значения индекса. Но я решил сделать свою реализацию битового массива, и вместо массива одиночных битов или байтов работать с массивом целых 32-битных чисел. Переходя к хранению 32 битов в одном числе я уменьшал требования к памяти как минимум в 32 раза.

Если бы и с таким подходом не влезло бы, можно было бы переводить числа в систему счисления более высокого порядка, например, в 10000-ричную, тем самым ещё уменьшив требования по памяти в 4 раза. Но у меня влезло :)

Результирующая программа должна была состоять из нескольких блоков:

• расчёт числа е с заданным количеством цифр после запятой
• «нарезка» из этих цифр числа е 10-значных чисел
• поиск первого кандидата на простоту при помощи встроенного вероятностного алгоритма
• поиск простых 10-значных чисел
• проверка наличия найденного кандидата среди точно простых чисел

При этом поиск простого числа сводился бы к обычной проверке бита в нужной позиции.

Программа получилась вот такой:

getPrime.java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.math.BigInteger;
 
public class getPrime
{
  public static void main(String[] args) 
  {
    var e=BigDecimal.ONE;
    var fact=BigDecimal.ONE;
    var mlrd=new BigInteger("1000000000");
    BigInteger e10=BigInteger.ZERO;
    String se;
 
    //ищем ~1000 знаков числа е
    for (int n=1; n<1000/3; n++) {
      fact=fact.multiply(BigDecimal.valueOf(n));
      e=e.add((BigDecimal.ONE).divide(fact, 1000, RoundingMode.CEILING)); 
    }       
 
    //преобразуем в строку и последовательно нарезаем её на 10-значные числа 
    se=e.toString(); se=se.substring(2, Math.min(se.length(), 1000));
    for(int i=0; i<se.length()-10; i++) {
      e10=new BigInteger(se.substring(i,i+10));
      //проверяем число на простоту встроенным вероятностным методом
      if (e10.isProbablePrime(1) && e10.compareTo(mlrd)==1) { break; }
    }
 
    //кандидат найден
    long probablePrime = e10.longValue();
    System.out.println(probablePrime+" ?");
 
    //===================================================================
 
    //большой битовый массив храним в массиве 32-битных чисел
    int len=(int)(probablePrime/32+1);
    int bits[]=new int[len];
 
    //ищем простые числа Решетом Эратосфена
    for (int p=2; p*p<len; p++) { //достаточно сделать корень из len шагов
      boolean isPrime=(bits[p/32]&1<<(p%32))==0;
      //если текущий индекс простой, то помечаем единичками все остальные кратные ему
      if (isPrime) { for (int i=p*p; i<len; i+=p) { bits[i/32]|=(1<<(i%32)); } } 
    }
 
    //проверяем, есть ли наш кандидат среди найденных простых чисел
    if ((bits[(int)(probablePrime/32)]&1<<((int)(probablePrime%32)))==0) { System.out.println("ОК"); }
  }
}

И она мне выдала: ОК

То есть, первым 10-значным простым числом в последовательности десятичных цифр числа e действительно оказалось то самое число 7427466391, которое выдал вероятностный алгоритм. Так что он не так уж плох. И начиналось это число с 99-й цифры, то есть мне в общем-то достаточно было рассчитать всего 108 десятичных знаков числа e.

2,
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193

Итак, программа это сама всё посчитала и выдала единственное правильное решение :) Вот теперь я был спокоен. Соответственно, адрес сайта получался 7427466391.com (сейчас сайт не существует, хотя домен всё равно числится за компанией Гугл).

Сам я точно не знаю, но говорят, что при заходе на этот сайт возникало сообщение:

Что может быть общего у чисел 7182818284, 8182845904, 8747135266, 7427466391?

Во-первых, они десятизначные, такие же, как и число из первой задачи. Во-вторых, они идут не по порядку. Для начала я попробовал найти их среди цифр числа е. И они легко нашлись. Программу я писать не стал, а тупо нашёл их обычным поиском в текстовом редакторе.

Числа 7182818284, 8182845904, 8747135266, 7427466391 начинаются, соответственно, с 1,5,23 и 89 цифры после запятой):

2,
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193
71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193

Логично предположить, что наше пятое число также должно быть найдено среди цифр числа е. Что же ещё может быть общего в этих числах? Они точно не простые, т.к. три из них чётные, да и первое простое мы уже нашли ранее, оно идёт далеко за этими числами.

Посчитаем сумму цифр, произведение цифр, числовой ключ, среднее значение и чего-нибудь ещё. Если не найдём ничего общего, будем пробовать найти что-то общее в их «координатах» (может быть, надо продолжить ряд 1,5,23,89…).

Самая первая гипотеза, как ни странно, подтвердилась – суммы цифр у этих чисел оказались равны:

• 7+1+8+2+8+1+8+2+8+4 = 49
• 8+1+8+2+8+4+5+9+0+4 = 49
• 8+7+4+7+1+3+5+2+6+6 = 49
• 7+4+2+7+4+6+6+3+9+1 = 49

Для поиска пятого числа пришлось тоже написать программку, которая последовательно искала в последовательности цифр числа е десятизначные числа с суммой цифр =49 и выводила пятое число.

find49.java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.math.BigInteger;
 
public class find49
{
  public static void main(String[] args) 
  {
    var e=BigDecimal.ONE;
    var fact=BigDecimal.ONE;
    var mlrd=new BigInteger("1000000000");
    BigInteger e10=BigInteger.ZERO;
    String se;
    int sum;
    int cnt=0;
 
    //ищем ~1000 знаков числа е
    for (int n=1; n<1000/3; n++) {
      fact=fact.multiply(BigDecimal.valueOf(n));
      e=e.add((BigDecimal.ONE).divide(fact, 1000, RoundingMode.CEILING)); 
    }       
 
    //преобразуем в строку и последовательно нарезаем её на 10-значные числа 
    se=e.toString(); se=se.substring(2, Math.min(se.length(), 1000));
    for(int i=0; i<se.length()-10; i++) {
      e10=new BigInteger(se.substring(i,i+10));
      long num=e10.longValue();
 
      sum=0; while(num!=0) { sum+=(num%10); num/=10; } //считаем сумму цифр
      if (sum==49) { cnt+=1; if (cnt<=5) { System.out.println(e10); } if (cnt==5) { break; } } //выводим пять первых чисел
 
    }
  }
}

И она выдала:

7182818284
8182845904
8747135266
7427466391
5966290435

Пятым 10-значным числом с суммой цифр 49 было 5966290435, и начиналось оно со 127-й позиции.

2,
7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540

Собственно, на этом всё. Проверить правильность я уже не мог, но я уверен на 100%, что ответ правильный.

Применённые мною при решении язык и приёмы программирования в 2004 году были и активно применялись. Производительность компьютеров тогда была пониже, поэтому расчёты длились бы дольше, но не критично долго. У меня сейчас программа работала пару секунд, тогда отработала бы за пару минут, то есть вполне приемлемо.

В общем-то, эту задачу можно было решить ручным брутфорсом (правда, пришлось бы перебрать сотню урлов и потом посчитать сумму цифр в трёх десятках 10-значных чисел), но «так нельзя». Программист просто обязан всё алгоритмизировать и автоматизировать, если число повторений более трёх :) А вдруг числа нашлись бы не в 100-й и 138-й позициях, а в 1100-й и 2138-й? Программа их с такой же лёгкостью нашла бы, а вот вручную пришлось бы лопатить до скончания веков. А ещё бывают задачи, в которых число попыток ограничено, чтобы как раз исключить возможность подбора ответа простым перебором всех возможных значений.

Так что, считаю, что квест от гугловских хэдхантеров я успешно прошёл.

Может быть, это можно было бы сделать ещё проще и быстрее, но уж как смог.

В процессе решения этой задачи я просмотрел много информации и нашёл несколько интересных ресурсов на тему числа е, простых чисел и вообще программирования. Ссылки на некоторые из них размещены ниже.

• https://habr.com/ru/articles/526924/ – Ищем простые числа до триллиона за тридцать минут (на C#)
• https://www.cyberforum.ru/csharp-net/thread1577023.html – Как инициализировать BitArray размером более 32int
• https://apod.nasa.gov/htmltest/gifcity/e.2mil – 2 миллиона знаков числа e после запятой
• https://devmark.ru/article/eratosthene-sieve – Решето Эратосфена для поиска простых чисел