Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Задачи №21-№40

Задача №21

Задача №21 - Amicable Numbers

Пусть \(d(n)\) определяется как сумма делителей n (числа меньше n, делящие n нацело). Если \(d(a) = b\) и \(d(b) = a\), где \(a \neq b\), то a и b называются дружественной парой, а каждое из чисел a и b - дружественным числом.

Например, делителями числа 220 являются 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, поэтому \(d(220) = 284\). Делители 284 - 1, 2, 4, 71, 142, поэтому \(d(284) = 220\).

Подсчитайте сумму всех дружественных чисел меньше 10000.

Алгоритм:

Следующий код на Scala находит сумму "дружественных" чисел меньше 10000. Числа a и b называются дружественными, если сумма делителей числа a (не считая самого числа) равна b, и сумма делителей числа b равна a.

  1. primeFactorsWithPow(n: Long): Map[Long, Int] - функция, которая находит простые делители числа n и их степени. Описание функции приведено в Problem 5.
  2. sumOfDivisors(number: Long): Long - функция, которая находит сумму делителей числа number. Она использует primeFactorsWithPow для получения простых делителей и их степеней, а затем использует foldLeft для вычисления суммы делителей.
  3. amicableNumbers - выражение, которое находит все "дружественные" числа меньше 10000.

Код:

def primeFactorsWithPow(n: Long): Map[Long, Int] = ... // Из Problem 5

def sumOfDivisors(number: Long): Long =
  val primeDivisors = primeFactorsWithPow(number)
  primeDivisors.foldLeft(1L) { case (mul, (prime, power)) =>
    val num = math.pow(prime, power + 1).toLong - 1
    val den = prime - 1
    mul * (num / den)
  }

val amicableNumbers =
  (2 until 10000).flatMap: a =>
    val b = sumOfDivisors(a) - a
    if b > a && sumOfDivisors(b) - b == a then Some(a + b) else None
  .sum

Задача №22

Задача №22 - Names Scores

Задача:

Используйте names.txt, текстовый файл размером 46 КБ, содержащий более пяти тысяч имен. Начните с сортировки в алфавитном порядке. Затем подсчитайте алфавитные значения каждого имени и умножьте это значение на порядковый номер имени в отсортированном списке для получения количества очков имени.

Например, если список отсортирован по алфавиту, имя COLIN (алфавитное значение которого 3 + 15 + 12 + 9 + 14 = 53) является 938-м в списке. Поэтому, имя COLIN получает \(938 \times 53 = 49714\) очков.

Какова сумма очков имен в файле?

Алгоритм:

Следующий код на Scala используется для вычисления алфавитной стоимости имен, хранящихся в файле "p022_names.txt".

  1. Определение функции alphabeticalValue, которая принимает символ char и возвращает его алфавитную стоимость. Алфавитная стоимость определяется как позиция символа в алфавите, если символ является буквой, иначе стоимость равна 0.
  2. Чтение имен из файла "p022_names.txt" и сохранение их в переменной names. Имена считываются из файла, разделены запятыми, отсортированы и сохранены в виде массива строк.
  3. Вычисление алфавитной стоимости каждого имени в отсортированном списке имен. Для каждого имени вычисляется сумма алфавитных значений его букв, умноженная на порядковый номер имени в отсортированном списке (индекс + 1).

Код:

def alphabeticalValue(char: Char): Int =
  if char.isLetter then char.toUpper.toInt - 'A' + 1 else 0

val names = Source
  .fromResource("p022_names.txt")
  .getLines
  .toSeq
  .mkString
  .split(",")
  .sorted
val count = names.indices.map: i =>
  (i + 1L) * names(i).map(alphabeticalValue).sum
.sum

Задача №23

Задача №23 - Non-Abundant Sums

Совершенным числом называется число, у которого сумма его делителей равна самому числу. Например, сумма делителей числа 28 равна 1 + 2 + 4 + 7 + 14 = 28, что означает, что число 28 является совершенным числом.

Число n называется недостаточным, если сумма его делителей меньше n, и называется избыточным, если сумма его делителей больше n.

Так как число 12 является наименьшим избыточным числом (1 + 2 + 3 + 4 + 6 = 16), наименьшее число, которое может быть записано как сумма двух избыточных чисел, равно 24. Используя математический анализ, можно показать, что все целые числа больше 28123 могут быть записаны как сумма двух избыточных чисел. Эта граница не может быть уменьшена дальнейшим анализом, даже несмотря на то, что наибольшее число, которое не может быть записано как сумма двух избыточных чисел, меньше этой границы.

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

Алгоритм:

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

  1. Определение функции sumOfDivisors, которая вычисляет сумму делителей заданного числа. Описана в Problem 21.
  2. Определение функции isAbundant, которая проверяет, является ли число избыточным.
  3. Определение предела limit и нахождение всех избыточных чисел в диапазоне от 12 до limit - 11.
  4. Создание массива canBeSumOfTwoAbundant размером limit + 1, который будет использоваться для отметки чисел, которые могут быть представлены как сумма двух избыточных чисел.
  5. Для каждого избыточного числа a в диапазоне от 12 до limit - 11, если a меньше или равно половине limit, то для каждого избыточного числа b в диапазоне от i до abundantNumbers.length, если сумма a и b меньше или равна limit, то в массиве canBeSumOfTwoAbundant помечается число s, равное сумме a и b, как то, которое можно представить в виду суммы избыточных чисел.
  6. Нахождение суммы всех чисел от 1 до limit, которые не могут быть представлены как сумма двух избыточных чисел, используя массив canBeSumOfTwoAbundant.

Код:

def sumOfDivisors(number: Long): Long = ... // Из Problem 21

def isAbundant(n: Long): Boolean =
  sumOfDivisors(n) > 2 * n

val limit           = 28123
val abundantNumbers = (12 to (limit - 11)).filter(isAbundant)

val half = limit / 2
val sum =
  val canBeSumOfTwoAbundant = new Array[Boolean](limit + 1)
  for
    i <- abundantNumbers.indices
    a = abundantNumbers(i)
    if a <= half
    j <- i until abundantNumbers.length
    s = a + abundantNumbers(j)
    if s <= limit
  do canBeSumOfTwoAbundant(s) = true

  (1 to limit).filterNot(i => canBeSumOfTwoAbundant(i)).sum

Задача №24

Задача №24 - Lexicographic Permutations

Перестановка - это упорядоченная выборка объектов. К примеру, 3124 является одной из возможных перестановок из цифр 1, 2, 3 и 4. Если все перестановки приведены в порядке возрастания или алфавитном порядке, то такой порядок будем называть словарным. Словарные перестановки из цифр 0, 1 и 2 представлены ниже:

012 021 102 120 201 210

Какова миллионная словарная перестановка из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8 и 9?

Алгоритм:

Следующий код на Scala используется для нахождения i-й перестановки заданного списка чисел.

Алгоритм работает следующим образом:

Код:

def factorial(n: Int): Int = (2 to n).product

@tailrec
def getIPerm(i: Int, rest: List[Int], acc: List[Int]): List[Int] =
  if rest.isEmpty then acc
  else
    val countOfRests = factorial(rest.length - 1)
    val k            = (i - 1) / countOfRests
    if k == 0 then getIPerm(i, rest.tail, rest.head :: acc)
    else
      getIPerm(
        i - k * countOfRests,
        rest.filterNot(_ == rest(k)),
        rest(k) :: acc
      )

def getIPermutation(i: Int, rest: List[Int]): Long =
  getIPerm(i, rest, List.empty[Int]).reverse.mkString.toLong

getIPermutation(1, List(0, 1, 2)) // 12
getIPermutation(2, List(0, 1, 2)) // 21
getIPermutation(3, List(0, 1, 2)) // 102
getIPermutation(4, List(0, 1, 2)) // 120
getIPermutation(5, List(0, 1, 2)) // 201
getIPermutation(6, List(0, 1, 2)) // 210

Задача №25

Задача №25 - 1000-digit Fibonacci Number

Последовательность Фибоначчи определяется рекурсивным правилом: \(F_{n} = F_{n-1} + F_{n-2}\), где \(F_{1} = 1\) и \(F_{2} = 1\).

Таким образом, первые 12 членов последовательности равны: \(F_{1} = 1, F_{2} = 1, F_{3} = 2, F_{4} = 3, F_{5} = 5, F_{6} = 8, F_{7} = 13, F_{8} = 21, F_{9} = 34, F_{10} = 55, F_{11} = 89, F_{12} = 144\)

Двенадцатый член \(F_{12}\) - первый член последовательности, который содержит три цифры.

Каков порядковый номер первого члена последовательности Фибоначчи, содержащего 1000 цифр?

Алгоритм:

Значение числа Фибоначчи можно вычислить по формуле Бине:

\(F_{n} = \frac{(\frac{1+\sqrt{5}}{2})^{n} - (\frac{1-\sqrt{5}}{2})^{n}}{\sqrt{5}} = \frac{(\varphi)^{n} - (-\varphi)^{-n}}{\varphi - (-\varphi)^{-1}} = \frac{(\varphi)^{n} - (-\varphi)^{-n}}{2\varphi - 1}\)

Чтобы найти первое число Фибоначчи, содержащее 1000 цифр, надо найти \(F_{n} \simeq \frac{\varphi^{n}}{2\varphi - 1} \geq 10^{999}\).

Что эквивалентно:

Код:

val phi: Double = (1.0 + math.sqrt(5.0)) / 2.0
val count: Int =
  ((999 + math.log10(2 * phi - 1)) / math.log10(phi)).toInt + 1

Задача №26

Задача №26 - Reciprocal Cycles

Единичная дробь имеет 1 в числителе. Десятичные представления единичных дробей со знаменателями от 2 до 10 даны ниже:

1/2 = 0.5; 1/3 = 0.(3); 1/4 = 0.25; 1/5 = 0.2; 1/6 = 0.1(6); 1/7 = 0.(142857); 1/8 = 0.125; 1/9 = 0.(1); 1/10 = 0.1

Где 0.1(6) значит 0.166666..., и имеет повторяющуюся последовательность из одной цифры. Заметим, что \(\frac{1}{7}\) имеет повторяющуюся последовательность из 6 цифр.

Найдите значение d < 1000, для которого \(\frac{1}{d}\) в десятичном виде содержит самую длинную повторяющуюся последовательность цифр.

Алгоритм:

Следующий код реализует алгоритм деления с остатком, который находит цикл в последовательности десятичных дробей. Функция getRecurringCycle(d: Int) принимает целочисленный параметр d и возвращает список целых чисел, представляющих цикл в десятичной дроби 1/d. Внутри функции getRecurringCycle(d: Int) определена внутренняя рекурсивная функция loop(a: Int, chain: List[Int], prev: List[Int]). Внутри loop, если a равно 0, функция возвращает пустой список Nil - цикла нет, последовательность "остатков" закончилась. В противном случае, она ищет индекс i числа a в списке prev (предыдущей цепи "остатков"). Если i не равно -1 ("остаток" повторился в prev), то функция возвращает перевернутую часть списка chain от начала до индекса i + 1. Это означает, что мы нашли цикл в десятичной дроби. Если i равно -1 ("остаток" ещё не повторился в prev), то функция вычисляет k и r. k - целая часть от деления a на d (добавляется в список chain), а r - остаток от деления умноженный на 10 (следующее число для аналаза). Затем функция вызывает саму себя с обновленными значениями a, chain и prev.

Код:

Вычислить циклическую часть в дроби можно так:

def getRecurringCycle(d: Int): List[Int] =
  @tailrec
  def loop(a: Int, chain: List[Int], prev: List[Int]): List[Int] =
    if a == 0 then Nil
    else
      val i = prev.indexOf(a)
      if i != -1 then chain.take(i + 1).reverse
      else
        val k = a / d
        val r = (a - k * d) * 10
        loop(r, k :: chain, a :: prev)

  loop(10, Nil, Nil)

getRecurringCycle(2)  // Nil
getRecurringCycle(3)  // List(3)
getRecurringCycle(4)  // Nil
getRecurringCycle(5)  // Nil
getRecurringCycle(6)  // List(6)
getRecurringCycle(7)  // List(1, 4, 2, 8, 5, 7)
getRecurringCycle(8)  // Nil
getRecurringCycle(9)  // List(1)
getRecurringCycle(10) // Nil

Аналогично можно вычислить длину цикла:

def getRecurringCycleLength(d: Int): Int =
  @tailrec
  def loop(a: Int, chain: List[Int], prev: List[Int]): Int =
    if a == 0 then 0
    else
      val i = prev.indexOf(a)
      if i != -1 then i + 1
      else
        val k = a / d
        val r = (a - k * d) * 10
        loop(r, k :: chain, a :: prev)

  loop(10, Nil, Nil)

Задача №27

Задача №27 - Quadratic Primes

Эйлер опубликовал свою замечательную квадратичную формулу: \(n^{2} + n + 41\).

Оказалось, что согласно данной формуле можно получить 40 простых чисел, последовательно подставляя значения \(0 \leq n \leq 39\). Однако, при n=40, \(40^{2} + 40 + 41 = 40(40 + 1) + 41\) делится на 41 без остатка, и, очевидно, при \(n = 41, 41^{2} + 41 + 41\) делится на 41 без остатка.

При помощи компьютеров была найдена невероятная формула \(n^{2} - 79n + 1601\), согласно которой можно получить 80 простых чисел для последовательных значений \(0 \leq n \leq 79\). Произведение коэффициентов −79 и 1601 равно −126479.

Рассмотрим квадратичную формулу вида: \(n^{2} + an + b\), где \(|a| < 1000\) и \(|b| \leq 1000\).

где |n| является модулем (абсолютным значением) n. К примеру, |11|=11 и |−4|=4.

Найдите произведение коэффициентов a и b квадратичного выражения, согласно которому можно получить максимальное количество простых чисел для последовательных значений n, начиная со значения n = 0.

Алгоритм:

  1. isPrime(n: Long): Boolean - функция, которая проверяет, является ли число простым.
  2. getCountOfPrimes(a: Int, b: Int): Int - функция, возвращающая количество простых чисел, которые равны \(n^{2} + an + b\) для заданных a и b, где n пробегает значения от 0 до такого первого значения k, при котором результат применения формулы - составное число. При этом k <= b, т.к. при k = b имеем: \(b^{2} + ab + b\) делится на b.
  3. sieveOfEratosthenes(n: Int): Array[Boolean] - функция, которая реализует алгоритм "Решето Эратосфена" для поиска всех простых чисел до n. Функция описана в разделе Problem 10.
  4. primesNoMoreThanN(n: Int): Array[Int] - функция, которая возвращает массив всех простых чисел, не превышающих n.
  5. abWithMaxCountOfPrimes: (Int, Int) - функция, которая ищет пару (a, b), для которой количество простых чисел, получаемых при подстановке в квадратичную формулу \(n^{2} + an + b\), является максимальным. Заметим, что b - простое число, т.к. при n = 0 результат формулы должен быть простым числом. При n = 1 получим, что \(1 + a + b\) тоже простое число, а значит, \(1 + a + b \geq 2 \Rightarrow a \geq 1 - b\).

Код:

def isPrime(n: Long): Boolean =
  if n < 2 then false
  else if n < 4 then true // 2 и 3 - простые
  else if n % 2 == 0 then false
  else if n < 9 then true // мы уже исключили 4,6 и 8
  else if n % 3 == 0 then false
  else
    val limit = math.ceil(math.sqrt(n.toDouble)).toLong

    @annotation.tailrec
    def loop(f: Long): Boolean =
      if f > limit then true
      else if n % f == 0 || n % (f + 2) == 0 then false
      else loop(f + 6)

    loop(5)

def getCountOfPrimes(a: Int, b: Int): Int =
  @tailrec
  def loop(n: Int, count: Int): Int =
    lazy val m = n * n + a * n + b
    if n < b && isPrime(m) then loop(n + 1, count + 1)
    else count

  loop(0, 0)

getCountOfPrimes(1, 41)     // 40
getCountOfPrimes(-79, 1601) // 80

def sieveOfEratosthenes(n: Int): Array[Boolean] = ... // аналогично методу из Problem 10

def primesNoMoreThanN(n: Int): Array[Int] =
  sieveOfEratosthenes(n).zipWithIndex.collect { case (true, prime) => prime }

def abWithMaxCountOfPrimes: (Int, Int) =
  val pairs =
    for
      b <- primesNoMoreThanN(1000)
      a <- 1 - b to 999
      if isPrime(1 + a + b)
    yield (a, b)

  pairs.maxBy(getCountOfPrimes)

Задача №28

Задача №28 - Number Spiral Diagonals

Начиная с числа 1 и двигаясь дальше вправо по часовой стрелке, образуется следующая спираль 5 на 5:

21 22 23 24 25

20 7 8 9 10

19 6 1 2 11

18 5 4 3 12

17 16 15 14 13

Можно убедиться, что сумма чисел в диагоналях равна 101.

Какова сумма чисел в диагоналях спирали 1001 на 1001, образованной таким же способом?

Алгоритм:

Определим \(S_{k}\) как искомую сумму чисел по диагонали спирали размера \((2k + 1) \times (2k + 1)\). Тогда \(S_{0} = 1, S_{1} = 25, S_{2} = 101\).

Заметим, что \(S_{k} = S_{k - 1} + d_{1} + d_{2} + d_{3} + d_{4}\), где \(d_{i}\) - числа по диагонали. При этом \(d_{i} = size_{k - 1} + i*(row_{k} - 1)\), где \(row_{k} = 2k + 1\) - размер стороны k-й спирали, а \(size_{k} = row_{k}^{2}\) - максимальное число (или, что тоже самое, размер квадрата) k-й спирали.

Получим:

Искомая по задаче сумма - это \(S_{500}\) (т.к. 1001 = 2k + 1).

Код:

def sumOfSquaresTo(n: Long): Long = n * (n + 1) * (2 * n + 1) / 6

def sumToGiven(n: Long): Long = n * (n + 1) / 2

def getCount(n: Int): Long =
  16 * sumOfSquaresTo(n - 1) + 36 * sumToGiven(n - 1) + 24 * n + 1

getCount(0) // 1
getCount(1) // 25
getCount(2) // 101

Задача №29

Задача №29 - Distinct Powers

Рассмотрим все целочисленные комбинации \(a^{b}\) для \(2 \leq a \leq 5\) и \(2 \leq a \leq 5\).

\(2^2=4, 2^3=8, 2^4=16, 2^5=32\)

\(3^2=9, 3^3=27, 3^4=81, 3^5=243\)

\(4^2=16, 4^3=64, 4^4=256, 4^5=1024\)

\(5^2=25, 5^3=125, 5^4=625, 5^5=3125\)

Если их расположить в порядке возрастания, исключив повторения, мы получим следующую последовательность из 15 различных членов:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125.

Сколько различных членов имеет последовательность \(a^{b}\) для \(2 \leq a \leq 100\) и \(2 \leq a \leq 100\)?

Алгоритм:

Следующий код демонстрирует несколько функций:

  1. primeFactorsWithPow(n: Long): Map[Long, Int] - функция находит простые множители числа n и возвращает их в виде Map, где ключ - простой множитель, а значение - степень, в которой он встречается в разложении числа n.
  2. getAView(a: Int): IndexedSeq[String] - функция принимает целое число a и возвращает последовательность строк, представляющих различные представления числа a в виде произведения простых множителей с указанными степенями.
  3. val count = (2 to 100).flatMap(getAView).distinct.length - код создает последовательность всех представлений чисел от 2 до 100, удаляет дубликаты и считает количество уникальных представлений.

Код:

def primeFactorsWithPow(n: Long): Map[Long, Int] = ... // Из Problem 5

def getAView(a: Int): IndexedSeq[String] =
  val number = primeFactorsWithPow(a)
  (2 to 100).map: b =>
    number
      .map { case (key, power) => s"$key-${power * b}" }
      .toSeq
      .sorted
      .mkString("--")

val count = (2 to 100).flatMap(getAView).distinct.length

Задача №30

Задача №30 - Digit Fifth Powers

Удивительно, но существует только три числа, которые могут быть записаны в виде суммы четвертых степеней их цифр:

\(1634 = 1^{4} + 6^{4} + 3^{4} + 4^{4}, 8208 = 8^{4} + 2^{4} + 0^{4} + 8^{4}, 9474 = 9^{4} + 4^{4} + 7^{4} + 4^{4}\)

\(1 = 1^{4}\) не считается, так как это - не сумма.

Сумма этих чисел равна 1634 + 8208 + 9474 = 19316.

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

Алгоритм:

Следующий метод находит все числа, которые можно представить в виде суммы p-х степеней их цифр, когда эти числа состоят из четырех цифр. Для начала, метод использует генератор for для создания всех возможных комбинаций четырех цифр. Каждая цифра a, b, c, d входит в диапазон от 0 до 9. Затем для каждой комбинации вычисляется p-я степень каждой цифры и проверяется, что сумма этих степеней не превышает число, составленное из этих цифр - для того, чтобы избежать перебора несуществующих чисел. Наконец, если сумма p-х степеней цифр равна числу, составленному из этих цифр, то это число добавляется в результирующую последовательность.

Аналогично можно создать методы для чисел, состоящих от 2-х до 6-ти цифр. Число из одной цифры суммой не является, а число из более чем 6 цифр не может равняться сумме пятых степеней своих цифр, т.к. \(k*9^{5} = k*59049 \leq 10^{k}\) для всех k больше 6.

Код:

def getSumOfPPowersWith4Digits(p: Int): IndexedSeq[Int] =
  for
    a <- 1 to 9
    ap = math.pow(a, p).toInt
    if ap < 1000 * (a + 1)
    b <- 0 to 9
    bp = math.pow(b, p).toInt
    if ap + bp < (1000 * a + 100 * (b + 1))
    c <- 0 to 9
    cp = math.pow(c, p).toInt
    if ap + bp + cp < (1000 * a + 100 * b + 10 * (c + 1))
    d <- 0 to 9
    dp = math.pow(d, p).toInt
    if ap + bp + cp + dp == 1000 * a + 100 * b + 10 * c + d
  yield 1000 * a + 100 * b + 10 * c + d

getSumOfFifthPowersWith4Digits(4) 
// IndexedSeq(1634, 8208, 9474)

Задача №31

Задача №31 - Coin Sums

В Англии валютой являются фунты стерлингов £ и пенсы p, и в обращении есть восемь монет: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) и £2 (200p).

£2 возможно составить следующим образом: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

Сколькими разными способами можно составить £2, используя любое количество монет?

Алгоритм:

Следующий код на Scala решает задачу о размене монет. Он определяет функцию countWays, которая принимает два параметра: coins - массив доступных монет, и sum - сумма, которую нужно разменять.

Внутри функции создается массив ways, который используется для хранения количества способов размена для каждой суммы от 0 до sum. Изначально все элементы массива инициализируются нулями. Затем ways(0) устанавливается равным 1, так как существует ровно один способ размена нулевой суммы - пустой набор монет.

Далее для каждой монеты из массива coins выполняется следующее:

В конце функция возвращает ways(sum) - количество способов размена суммы sum.

Код:

def countWays(coins: Array[Int], sum: Int): Long =
  val ways = Array.fill(sum + 1)(0L)
  ways(0) = 1
  coins.foreach: coin =>
    (coin to sum).foreach: i =>
      ways(i) += ways(i - coin)
  ways(sum)

countWays(Array(1, 2, 5, 10, 20, 50, 100, 200), 200)

Задача №32

Задача №32 - Pandigital Products

Каждое n-значное число, которое содержит каждую цифру от 1 до n ровно один раз, будем считать пан-цифровым; к примеру, 5-значное число 15234 является пан-цифровым, т.к. содержит цифры от 1 до 5.

Произведение 7254 является необычным, поскольку равенство 39 × 186 = 7254, состоящее из множимого, множителя и произведения является пан-цифровым, т.е. содержит цифры от 1 до 9.

Найдите сумму всех пан-цифровых произведений, для которых равенство "множимое × множитель = произведение" можно записать цифрами от 1 до 9, используя каждую цифру только один раз.

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

Алгоритм:

  1. Определяем функцию isProductCorrect, которая проверяет, является ли произведение product корректным. Произведение считается корректным, если оно состоит из 4 уникальных цифр (не включая 0) и не содержит цифр, которые входят в состав множителей multiplicand и multiplier.
  2. Определяет функцию getAllPandigital, генерирующую все возможные комбинации множителей и произведений, которые могут быть получены путем умножения множителей (двухзначного и трехзначного, либо однозначного и четырехзначного).
  3. Внутри getAllPandigital также определяется вектор candidates, который содержит пару множителей и их произведение, отфильтрованный с помощью isProductCorrect.
  4. Функция getDistinctProductSum использует getAllPandigital для получения всех возможных комбинаций, извлекает уникальные произведения, суммирует их и возвращает результат.

Код:

def isProductCorrect(
    multiplicand: String,
    multiplier: String,
    product: String
): Boolean =
  product.length == 4 &&
    product.distinct.length == 4 &&
    !product.contains('0') &&
    (multiplicand + multiplier).forall(ch => !product.contains(ch))

def getAllPandigital: IndexedSeq[IndexedSeq[(String, String, String)]] =
  for
    a <- 1 to 9
    b <- 1 to 9
    if b != a
    c <- 1 to 9
    if c != a && c != b
    d <- 1 to 9
    if d != a && d != b && d != c
    e <- 1 to 9
    if e != a && e != b && e != c && e != d
  yield
    val multiplicand1 = 10 * a + b
    val multiplier1   = 100 * c + 10 * d + e
    val product1      = (multiplicand1 * multiplier1).toString

    val multiplicand2 = a
    val multiplier2   = 1000 * b + multiplier1
    val product2      = (multiplicand2 * multiplier2).toString

    val candidates: Vector[(String, String, String)] =
      Vector(
        (multiplicand1.toString, multiplier1.toString, product1),
        (multiplicand2.toString, multiplier2.toString, product2)
      )
    candidates.filter(isProductCorrect)

def getDistinctProductSum: Int =
  getAllPandigital.flatten.map(_._3.toInt).distinct.sum

Задача №33

Задача №33 - Digit Cancelling Fractions

Дробь 49/98 является любопытной, поскольку неопытный математик, пытаясь сократить ее, будет ошибочно полагать, что 49/98 = 4/8, являющееся истиной, получено вычеркиванием девяток.

Дроби вида 30/50 = 3/5 будем считать тривиальными примерами.

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

Пусть произведение этих четырех дробей дано в виде несократимой дроби (числитель и знаменатель дроби не имеют общих сомножителей). Найдите знаменатель этой дроби.

Алгоритм:

Из условия задачи следует:

Код:

def getAllFractions: IndexedSeq[(Int, Int)] =
  (
    for
      a <- 1 to 7
      b <- a + 1 to 8
      c <- b + 1 to 9
    yield
      val ac = a * 10 + c
      val cb = c * 10 + b
      val ab = a * 10 + b
      val ca = c * 10 + a
      if ac * b == a * cb then Some((ac, cb))
      else if ab * c == b * ca then Some((ab, ca))
      else None
  ).flatten

@tailrec
def gcd(a: Long, b: Long): Long =
  if b == 0 then a else gcd(b, a % b)

def getFractionDenominator: Long =
  val (n, d) = getAllFractions.foldLeft((1L, 1L)) { case ((n, d), (fn, fd)) =>
    (n * fn, d * fd)
  }
  d / gcd(n, d)

Задача №34

Задача №34 - Digit Factorials

145 является любопытным числом, поскольку 1! + 4! + 5! = 1 + 24 + 120 = 145.

Найдите сумму всех чисел, каждое из которых равно сумме факториалов своих цифр.

Замечание: поскольку 1! = 1 и 2! = 2 не являются суммами, учитывать их не следует.

Алгоритм:

Заметим, что достаточно рассмотреть только k-значные числа, где 2 < k < 7, т.к. \(9!*k < 10^{k}\) для всех k > 7. Остальные варианты можно перебрать.

Код:

Для трехзначного числа перебор может быть таким, предварительно вычислив все факториалы от 0 до 9, чтобы не вычислять их более одного раза:

def factorial(n: Int): BigInt =
  (2 to n).foldLeft(BigInt(1))(_ * _)

val factorials = (0 to 9).map(factorial)

def getLuckyNumberWithThreeDigits: IndexedSeq[Int] =
  for
    a <- 1 to 9
    limit = (a + 1) * 100
    if factorials(a) < limit
    b <- 0 to 9
    if factorials(a) + factorials(b) < limit
    c <- 0 to 9
    if factorials(a) + factorials(b) + factorials(c) < limit
    abc = a * 100 + b * 10 + c
    if abc == factorials(a) + factorials(b) + factorials(c)
  yield abc

Задача №35

Задача №35 - Circular Primes

Число 197 называется круговым простым числом, потому что все перестановки его цифр с конца в начало являются простыми числами: 197, 719 и 971.

Существует тринадцать таких простых чисел меньше 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79 и 97.

Сколько существует круговых простых чисел меньше миллиона?

Алгоритм:

Код:

def getCircularRotation(n: Int): IndexedSeq[Int] =
  if n < 10 then IndexedSeq(n)
  else
    val m = n.toString
    m.indices.map: i =>
      (m.drop(i) + m.take(i)).toInt

def sieveOfEratosthenes(n: Int): Array[Boolean] = ... // из Problem 10

def countPrimes(limit: Int): Int =
  val isPrimeArr = sieveOfEratosthenes(limit)
  isPrimeArr.indices.count: i =>
    isPrimeArr(i) && getCircularRotation(i).forall(isPrimeArr)

getCircularRotation(197) // Vector(197, 971, 719)
countPrimes(100)         // 13

Задача №36

Задача №36 - Double-base Palindromes

Десятичное число \(585 = 1001001001_{2}\) (в двоичной системе), является палиндромом по обоим основаниям.

Найдите сумму всех чисел меньше миллиона, являющихся палиндромами по основаниям 10 и 2.

Замечание: Пожалуйста, обратите внимание на то, что палиндромы не могут начинаться с нуля ни в одном из оснований.

Алгоритм:

Заметим, что палиндром не может заканчиваться на четную цифру, т.к. в этом случае в двоичном представлении перевернутое число будет начинаться с 0, что противоречит условию задачи.

  1. isPalindrome(number: Long, base: Int): Boolean - функция проверяет, является ли число number палиндромом в системе счисления с основанием base.
  2. getAllPalindromes - функция использует функцию isPalindrome для фильтрации всех нечетных чисел от 1 до 999999. Она проверяет, являются ли числа палиндромами в десятичной и двоичной системах счисления. Функция возвращает список всех чисел, которые являются палиндромами в обеих системах счисления.

Код:

def isPalindrome(number: Long, base: Int): Boolean =
  var revertedNumber = 0L
  var k              = number
  while k > revertedNumber
  do
    revertedNumber = revertedNumber * base + k % base
    k /= base
  k == revertedNumber || k == revertedNumber / base

def getAllPalindromes =
  (1 until 1000000 by 2).filter: i =>
    isPalindrome(i, 10) && isPalindrome(i, 2)

Задача №37

Задача №37 - Truncatable Primes

Число 3797 обладает интересным свойством. Будучи само по себе простым числом, из него можно последовательно выбрасывать цифры слева направо, число же при этом остается простым на каждом этапе: 3797, 797, 97, 7. Точно таким же способом можно выбрасывать цифры справа налево: 3797, 379, 37, 3.

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

Замечание: числа 2, 3, 5 и 7 таковыми не считаются.

Алгоритм:

Следующий код реализует алгоритм для нахождения всех «целочисленных чисел, которые можно обрезать слева или справа и оставить простыми». Код находит все 11 чисел, но не гарантирует, что "других нет".

Ссылка на объяснение, почему таких чисел только 11.

Код:

def sieveOfEratosthenes(n: Int): Array[Boolean] = ... // Из Problem 10

def allTruncatableNumbers: Seq[Int] =
  val isPrimes = sieveOfEratosthenes(1000000)

  @tailrec
  def isRightTruncatable(n: Int): Boolean =
    isPrimes(n) && (n < 10 || isRightTruncatable(n / 10))

  @tailrec
  def isLeftTruncatable(n: Int): Boolean =
    isPrimes(n) && (n < 10 || isLeftTruncatable(n.toString.tail.toInt))

  (10 until 1000000).filter: n =>
    isPrimes(n) && isRightTruncatable(n) && isLeftTruncatable(n)

allTruncatableNumbers
// Vector(23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397)

Задача №38

Задача №38 - Pandigital Multiples

Возьмем число 192 и умножим его по очереди на 1, 2 и 3: \(192 \times 1 = 192, 192 \times 2 = 384, 192 \times 3 = 576\).

Объединяя все три произведения, получим девятизначное число 192384576 из цифр от 1 до 9 (пан-цифровое число). Будем называть число 192384576 объединенным произведением 192 и (1,2,3)

Таким же образом можно начать с числа 9 и по очереди умножать его на 1, 2, 3, 4 и 5, что в итоге дает пан-цифровое число 918273645, являющееся объединенным произведением 9 и (1,2,3,4,5).

Какое самое большое девятизначное пан-цифровое число можно образовать как объединенное произведение целого числа и (1,2, ... , n), где n > 1?

Алгоритм:

Следующий код реализует функции для поиска наибольшего панцифрового числа, которое можно получить путем объединения произведений целого числа x с последовательными целыми числами от 1 до n.

  1. isPandigital(number: String): Boolean - функция, которая проверяет, является ли строка number панцифровой. Панцифровое число - это число, содержащее каждую цифру от 1 до 9 ровно один раз.
  2. getProduct(n: Int, i: Int, product: String): Option[Long] - рекурсивная функция, которая вычисляет произведение n на i, добавляет его к строке product и вызывает саму себя с увеличенным i, пока длина строки product не станет равной или более 9. Если строка product является панцифровой, функция возвращает ее в виде числа Long. В противном случае возвращает None.
  3. getAllNumbers: Long - функция, которая использует функцию getProduct для каждого числа от 2 до 9999 и возвращает наибольшее панцифровое число, которое можно получить.
  4. Числа более 9999 не подходят, т.к. уже для i = 2 превышают 9 знаков.

Код:

def isPandigital(number: String): Boolean =
  number.length == 9 && !number.contains("0") &&
    number.toSeq.distinct.length == 9

@tailrec
def getProduct(n: Int, i: Int, product: String): Option[Long] =
  val newProduct = product + (n * i).toString
  if newProduct.length < 9 then getProduct(n, i + 1, newProduct)
  else if newProduct.length == 9 && isPandigital(newProduct) then
    Some(newProduct.toLong)
  else None

def getAllNumbers: Long =
  (2 until 10000).flatMap: n =>
    getProduct(n, i = 2, product = n.toString)
  .max

Задача №39

Задача №39 - Integer Right Triangles

Если p - периметр прямоугольного треугольника с целочисленными длинами сторон {a, b, c}, то существует ровно три решения для p = 120:

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}

Какое значение p ≤ 1000 дает максимальное число решений?

Алгоритм:

Как вычислить Пифагорову тройку с заданной суммой объясняется в соответствующем разделе.

Код:

@tailrec
def gcd(a: Long, b: Long): Long =
  if b == 0 then a else gcd(b, a % b)

def pythagoreanTripletsWithGivenSum(sum: Long): Int =
  if sum % 2 == 1 then 0
  else
    var count = 0
    val s2          = sum / 2
    val sqrt        = math.sqrt(s2.toDouble).toLong
    val mLimit      = if sqrt * sqrt == s2 then sqrt - 1 else sqrt

    for m <- 2L to mLimit do
      if s2 % m == 0 then
        var sm = s2 / m
        // сократим пространство поиска, удалив все делители 2
        while sm % 2 == 0 do sm /= 2
        var k = if m % 2 == 1 then m + 2 else m + 1
        while k < 2 * m && k <= sm
        do
          if sm % k == 0 && gcd(k, m) == 1 then
            val d = s2 / (k * m)
            val n = k - m
            val a = d * (m * m - n * n)
            val b = 2 * d * m * n
            val c = d * (m * m + n * n)
            count += 1
          k += 2

    count

val count = (1 to 1000).maxBy: i =>
  pythagoreanTripletsWithGivenSum(i)

Задача №40

Задача №40 - Champernowne's Constant

Дана иррациональная десятичная дробь, образованная объединением натуральных чисел: 0.123456789101112131415161718192021...

Видно, что 12-я цифра дробной части - 1.

Также дано, что \(d_{n}\) представляет собой n-ю цифру дробной части. Найдите значение следующего выражения:

\(d_{1} \times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000}\)

Алгоритм:

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

  1. getCountOfDigits(d: Int): Long - функция, которая вычисляет количество цифр в числах, состоящих из d и меньше цифр.
  2. getD(d: Int): Int - функция, которая находит цифру в числе, состоящем из d цифр. Она находит число, в котором находится d-ая цифра, и определяет, какая цифра находится в этом числе на позиции d.
  3. В конце кода определяется значение count, которое является произведением цифр, находящихся на позициях 1, 10, 100, 1000, 10000, 100000 и 1000000 в последовательности чисел.

Код:

def getCountOfDigits(d: Int): Long =
  val p = math.pow(10, d).toLong
  d * p - (p - 1) / 9

def getD(d: Int): Int =
  val digits      = (1 to 10000).find(i => getCountOfDigits(i) >= d).getOrElse(0)
  val rest        = d - getCountOfDigits(digits - 1) - 1
  val i           = rest / digits
  val j           = (rest % digits).toInt
  val number      = (math.pow(10, digits - 1).toLong + i).toString
  val resultDigit = number(j).getNumericValue
  resultDigit

val count =
  getD(1) * getD(10) * getD(100) * getD(1000) * getD(10000) *
    getD(100000) * getD(1000000)

Ссылки: