В этот раз не будет графики, однако, без математики эта статья не останется — математики будет хоть и много, но она не настолько сложна и доступна любому, кто спокойно доучился хотя бы до 6-ого класса средней школы.
Давайте обратим внимание на такую штуку (которой в школах и университетах уделяют слишком мало времени), как теория чисел. Теория чисел — это область математики, которая занимается изучением различных чисел, их свойств, а также занимается нахождением закономерностей (в том числе и довольно любопытных и интересных) между классами чисел и решением некоторых прикладных и теоретических проблем.
Поразительно, но трепетное отношение математиков к разным классам чисел и выделяющимся из этих классов числам, заставляет множество людей думать, что теория чисел не имеет никакого отношения к жизни и является лишь развлечением для очкастых ботаников. Хочу сразу сказать, эта область математики является сама по себе интересна, кроме того, большинство достижений теории чисел используются в современной криптографии и построении высокопроизводительных алгоритмов в самых разных сферах программирования (и не только).
Итак, теорема 1: неинтересных чисел не бывает.
Доказательство: будем использовать метод «от противного». Допустим удалось все числа разделить на интересные и неинтересные. Возьмем самое маленькое (или самое большое) из неинтересных чисел. Оба-на, а это интересное свойство данного числа, а это противоречие (противоречит исходной гипотезе), следовательно, теорема доказана.
Конечно, это всего лишь математическая шутка, однако, давайте же рассмотрим некоторые интересные числа.
Есть ряд чисел, которые делятся только на само себя и единицу, этот ряд чисел принято называть множеством простых чисел. Эти числа, довольно-таки просто получить, но с ними связан целый ряд нерешенных математических проблем, а их уникальные свойства обуславливают применение больших таких чисел в генераторах псевдослучайных чисел и криптографии.
Как узнать простое число или нет?
Чтобы узнать является ли число n простым нужно всего лишь убедится, что это число не делится ни на что в диапазоне от 2 до n-1, т.е. достаточно в цикле перебрать все возможные делители числа. Все просто, однако, не эффективно.
Для увеличения эффективности алгоритма, воспользуемся предложением арабского математика ибн аль-Банна, который предложил сильно сократить диапазон перебора, путем использования другого, а именно диапазона от 2 до sqrt(n), где sqrt — это квадратный корень из числа, округленный до ближайшего целого.
Воспользуемся этим дельным предложением, реализовав для начала вспомогательную функцию для вычисления целочисленного квадратного корня без всяких округлений и использований модуля std.math:
// квадратный корень
uint squareRoot(uint n)
{
uint i = 1, counter = 0;
while (i <= n) {
n -= i;
counter++;
i += 2;
}
return counter;
}
Работает это просто. Рассмотрим возрастающую последовательность квадратов неотрицательных целых чисел:
1 * 1 = 1
2 * 2 = 4
3 * 3 = 9
4 * 4 = 16
и т.д.
Найдем теперь разности соседних квадратов чисел:
4 - 1 = 3
9 - 4 = 5
16 - 9 = 7
и т.д.
Нетрудно заметить, что при продолжении этого ряда из разностей, мы будем получать все возрастающее нечетное число, следовательно, для извлечения квадратного корня из числа нужно вычитать из него последовательно (в порядке возрастания) нечетные числа до тех пор, пока не получим в результате ноль. И тогда, искомый квадратный корень будет равен количеству сделанных вычитаний, возьмем для примера число 16:
16 - 1 - 3 - 5 - 7 = 0
Таким образом, было сделано 4 вычитания, что и равно квадратному корню из 16.
Теперь, переходим к проверке некоторого числа на простоту:
// число простое ? (алгоритм, придуманный ибн аль-Банна)
bool isPrime(uint n)
{
bool result = true;
for (uint i = 2; i < squareRoot(n) + 1; i++)
{
if (n % i == 0)
{
result = false;
break;
}
}
return result;
}
Алгоритм довольно простой: в начале функции устанавливаем переменную result в true, полагая изначально, что переданный аргумент функции будет простым.
После установки переменной, в цикле проходим все числа от 2 до squareRoot(n) + 1 (добавляем 1, поскольку иначе сам квадратный корень не попадает в диапазон) и проверяем делится ли наше число на переменную-счетчик цикла, и если остаток от деления равен нулю, то число не является простым, следовательно, result установится в false, а дальнейшая проверка не имеет смысла и цикл прерывается, после чего функция возвращает значение переменной result.
Имея функцию isPrime, возвращающую true, если число простое, можно попробовать получить целый список простых чисел от 2 до n:
// список простых чисел от 2 до n
uint[] primeNumbers(uint n)
{
uint[] primes;
for (uint i = 2; i < n + 2; i++)
{
if (isPrime(i))
{
primes ~= i;
}
}
return primes;
}
Тут все тоже тривиально: проходим в цикле все числа от 2 до n и если число оказывается простым, то добавляем его в изначально пустой массив-аккумулятор.
Кроме того, можно добиться и другого результата: возьмем пустой массив-накопитель и будем добавлять в него простые числа, до тех пор пока длина массива не станет равной n - таким образом мы сможем получить список, состоящий из n простых чисел:
// n - прстых чисел
uint[] nPrimeNumbers(uint n)
{
uint[] primes;
uint counter = 2;
while (primes.length < n)
{
if (isPrime(counter))
{
primes ~= counter;
}
counter++;
}
return primes;
}
Результат (осторожно, много данных - 500 простых чисел):
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571]
И все это получено за 0.349 секунды на моем потертом нетбуке eMachines eM350!
Однако, рассмотренный алгоритм получения простых чисел от 2 до n, неэффективен (по мнению Википедии) и в принципе, можно придумать кое-что более стоящее, но при этом очевидно простое.
Древнегреческий математик Эратосфен придумал весьма простой метод поиска простых чисел: он брал вощенную дощечку, записывал при помощи стила (такая палочка заостренная, если кто не знает) числа от 2 до n, а затем прокалывал дырочки сначала в тех местах, в которых написаны все числа, которые делятся на 2 (кроме 2, естественно); затем прокалывал дырочки в тех местах, где написаны числа, делящиеся на 3; затем прокалывал те места, в которых написаны числа делящиеся на 5 - и так далее.
Не удивительно, что дощечку, получившуюся после выполнения всех этих пунктов, назвали Эратосфеновым решетом (или решетом Эратосфена) - ведь она действительно по внешнему виду напоминала решето!
Вот этот алгоритм, но в улучшенном виде, мы и реализуем: само решето использует массив, заполненный числами от 2 до n, из которого берется некоторое число p (изначально равное двум - наименьшему простому числу), а потом из массива удаляются числа 2*p, 3 *p и т.д, при последнее вычеркнутое число меньше или равно n, после этого шага изменяется число p, которое становится равным следующему неудаленному числу - и далее процедура повторяется; улучшение проявляется в следующем - мы будем удалять из массива числа, начиная с p ^^ 2, а остановлена процедура удаления будет тогда когда p ^^ 2 превысит n (а в случае, неулучшенного алгоритма, критерием остановки будет превышение p по сравнению с n).
Однако, вместо удаления проще реализовать другую стратегию: возьмем массив из булевых переменных и заполним все его ячейки значением true, а в роли чисел будут индексы этого массива и вместо удаления ячейки будет занесение в нее false.
Но вот проблема: индексация массива начинается не с 2, а с 0, а ноль, как и единица, не является простым числом, соответственно, на время прохода по массиву нужно две ячейки установить в false (ячейки с номерами 0 и 1).
Таким образом изначальный алгоритм решета изменяется практически до неузнаваемости - после прохода отсеивания, будут в массив-накопитель попадать индексы тех ячеек, которые будут иметь значение true:
// решето эратосфена (улучшенная реализация)
uint[] erathosphen(uint n)
{
bool[] primeIndex = [false, false];
uint[] primeNumbers;
// заполняем массив
for (uint i = 0; i < n; i++)
{
primeIndex ~= true;
}
// вычеркиваем числа
for (uint i = 2; i * i <= n; i++)
{
if (primeIndex[i])
{
for (uint j = i * i; j <= n; j += i)
{
primeIndex[j] = false;
}
}
}
// массив из простых чисел
for (uint i = 0; i < n; i++)
{
if (primeIndex[i])
{
primeNumbers ~= i;
}
}
return primeNumbers;
}
Вот и все с простыми числами.
В теории чисел есть довольно интересный класс: совершенные числа. Совершенные числа - это числа, которые равны сумме своих делителей, за исключением себя самого.
Алгоритм поиска таких чисел прост:
uint[] perfectNumbers(uint n)
{
uint[] perfect;
for (uint i = 1; i < n; i++)
{
uint sum = 0;
for (uint j = 1; j < i - 1; j++)
{
if (i % j == 0)
{
sum += j;
}
}
if (i == sum)
{
perfect ~= i;
}
}
return perfect;
}
Работает это просто: мы для каждого числа i из диапазона от 2 до n, проверяем, является ли это число равным сумме своих делителей, и если это действительно так, то помещаем число i в массив.
Интересным фактом является тот факт, что совершенные числа абсолютно бесполезны, однако, они ставят две нерешенные проблемы: существуют ли нечетные совершенные числа и конечно ли их множество - для разрешения подобных вопросов нужны гигантские вычислительные ресурсы, поэтому анализом подобных вопросов занимаются математики, использующие распределенные вычисления (что-то мне подсказывает, что мы возможно попробуем организовать нечто подобное, наверное, в некотором обозримом будущем...).
Евклид, основатель всем известной евклидовой геометрии, доказал, что если при некотором значении числа p, число (2 ^^ p) - 1 является простым, то число (2 ^^ (p - 1)) * ((2 ^^ p) - 1) является совершенным (кстати, из этой формулы очевиден факт, что таким образом можно находить лишь четные совершенные числа, поскольку происходит умножение на степень двойки).
Числа (2 ^^ p) - 1 являющиеся простыми, называются простыми числами Мерсенна. Такие числа очень важны для математики и криптографии, поскольку им принадлежит первенство в списке самых больших известных простых чисел (а все потому, что существует довольно эффективный тест на простоту для таких чисел), помимо того один любопытный факт: простые числа Мерсенна используются в довольно мощном алгоритме генераторе псевдослучайных чисел, называемом вихрем Мерсенна - этот алгоритм имеет гигантский период повторения выдаваемой последовательности, и именно на основе этого алгоритма работает модуль std.random стандартной библиотеки D.
Для поиска таких чисел будем проверять каждую степень p для числа (2 ^^ p) - 1, начиная проверку с 1, если число (2 ^^ p) - 1 окажется простым, то поместим его в массив (предупреждение: переменной p в данном коде соответствует переменная i):
uint[] mersennNumbers(uint n)
{
uint[] mersenn;
for (uint i = 2; i < n; i++)
{
auto tmp = (2 ^^ i) - 1;
if (isPrime(tmp))
{
mersenn ~= tmp;
}
}
return mersenn;
}
В данном случае n является концом диапазона возможных степеней, и соответственно, последним числом на проверку соответствия множеству простых чисел Мерсенна будет число (2 ^^ n) - 1 - приведенный алгоритм достаточно простой.
Пифагор, как-то сказал: "Мой друг тот, кто является моим вторым я, как числа 220 и 284". Так что же он имел в виду и чем так примечательны эти два числа?
Дело в том, что 220 и 284 - это первая пара дружественных чисел. Дружественными числами называются числа, сумма делителей каждого из которых равна второму числу. И действительно:
делители числа 220:
1, 2, 4, 5, 10, 11, 20, 22, 40, 44, 45, 55, 110
делители числа 284:
1, 2, 4, 71, 142
результат:
1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 40 + 44 + 45 + 55 + 110 = 284
1 + 2 + 4 + 71 + 142 = 220
Прикольно Пифагор выразился, а?!
А теперь ложка дегтя: алгоритм поиска таких чисел я не нашел, а потому пришлось изобретать самому и, на мой взгляд, то что удалось придумать вышло не столь эффективным и простым для понимания, а потому объяснение работы этого чуда может быть несколько кривым и косноязычным.
Для начала нам потребуется небольшая процедура, которая будет генерировать массив, содержащий суммы делителей чисел от 2 до n (само число при этом не считается делителем):
uint[] divisorsSum(uint n)
{
uint[] sumList;
for (uint i = 2; i < n; i++)
{
uint sum = 0;
for (uint j = 1; j < i - 1; j++)
{
if (i % j == 0)
{
sum += j;
}
}
sumList ~= sum;
}
return sumList;
}
По сути дела, эту процедуру но в несколько урезанном виде мы уже использовали, а алгоритм, я полагаю, сложностей не представляет: два цикла - внешний и внутренний; во внешнем цикле происходит перебор всех чисел диапазона и помещение суммы делителей в массив, а во внутреннем - подсчет суммы делителей для одного числа из заданного диапазона.
Теперь начинаются сложности: массивы в D индексируются, начиная от нуля, когда наш список должен бы индексироваться, начиная с 2. Если бы массив, начинался с индекса 2, то каждый индекс по сути дела обозначал бы число, для которого рассчитана сумма делителей, и именно это послужило бы для однозначного сопоставления "число - сумма".
Эту трудность с индексированием легко преодолеть: достаточно индексировать массив как обычно (начиная с нуля), и ставить в соответствие значению, считанному из массива сумм, индекс, увеличенный на 2.
Исходя из этого предположения, наш алгоритм будет работать примерно так: генерируем список сумм делителей для чисел от 2 до n, выбираем первый попавшийся элемент массива и вычисляем его индекс (в привычной для D манере индексации), после этого во внутреннем цикле начинаем точно такую же процедуру перебора. Во внутреннем цикле организовываем проверку равенства увеличенного на 2 индекса из первого цикла, для элемента, полученного из массива внутреннего цикла, при одновременной проверке равенства увеличенного на 2 индекса из второго цикла, но для элемента, полученного из массива внешнего цикла: если такое объединенное условие проверки окажется верным, то значит, мы нашли пару дружественных чисел. Перед помещением найденной пары в массив-накопитель (который мы задали заранее в описании функции), нужно убедиться, что найденные дружественные числа (роль которых играют индексы внутреннего и внешнего цикла, увеличенные на 2) не равны друг другу - для чего проводим проверку на неравенство индексов.
Но, чтобы не быть неправильно понятым, вот весь код (который гораздо более понятный, чем объяснение механики его работы):
alias uint[2] pair;
pair[] friendNumbers(uint n)
{
pair[] friends;
uint[] ds = divisorsSum(n);
foreach (ind, a; ds)
{
foreach (ind2, b; ds)
{
if ((ind + 2 == b) && (ind2 + 2 == a))
{
if (ind + 2 != ind2 + 2)
{
pair tmp = [ind + 2, ind2 + 2];
friends ~= tmp;
}
}
}
}
return friends;
}
единственный момент, который не был затронут - это конструкция alias перед объявлением самой функции. alias создает псевдоним для структуры, класса, типа и т.п вещам, позволяя писать более удобный и недвусмысленный код, однако, стоит помнить, что эта конструкция не создает новых типов, а создает лишь синоним.
Конструкция alias имеет примерно вот такой синтаксис:
alias <выражение> <псевдоним>;
но все-таки, несмотря на простоту применения, эта штука обладает большой мощностью и способна застраховать от написания весьма трудно читаемого или двусмысленного кода.
На этом небольшая экскурсия в теорию чисел закончена (однако, она по-любому продолжится) и в качестве окончания любопытнейшая цитата из какого-то древнего манускрипта (без шуток, это правда цитата):
Чтобы добиться взаимности и любви, нужно на чем-либо написать числа 220 и 284, меньшее дать объекту любви, а большее съесть самому
Ну, а вдруг? 😀