Задачи №61-№80

Задача №61

Задача №61 - Cyclical Figurate Numbers

К фигурным (многоугольным) числам относятся треугольные, квадратные, пятиугольные, шестиугольные, семиугольные и восьмиугольные числа, которые расчитываются по следующим формулам:

Треугольные: \(P_{3,n}=n(n+1)/2 \rightarrow 1, 3, 6, 10, 15, \dots \)

Квадратные: \(P_{4,n}=n^{2} \rightarrow 1, 4, 9, 16, 25, \dots \)

Пятиугольные: \(P_{5,n}=n(3n-1)/2 \rightarrow 1, 5, 12, 22, 35, \dots \)

Шестиугольные: \(P_{6,n}=n(2n-1) \rightarrow 1, 6, 15, 28, 45, \dots \)

Семиугольные: \(P_{7,n}=n(5n-3)/2 \rightarrow 1, 7, 18, 34, 55, \dots \)

Восьмиугольные: \(P_{8,n}=n(3n-2) \rightarrow 1, 8, 21, 40, 65, \dots \)

Упорядоченное множество из трех четырехзначных чисел: 8128, 2882, 8281, обладает тремя интересными свойствами

• Множество является цикличным: последние две цифры каждого числа являются первыми двумя цифрами следующего (включая последнее и первое числа).
• Каждый тип многоугольника — треугольник (P3,127=8128), квадрат (P4,91=8281) и пятиугольник (P5,44=2882) — представлены различными числами данного множества.
• Это — единственное множество четырехзначных чисел, обладающее указанными свойствами.

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

Алгоритм:

• В первую очередь сформируем списки всех четырехзначных циклических чисел.

Код:

def triangleNumber(n: Int): Int = n * (n + 1) / 2

lazy val triangle = LazyList
  .from(1)
  .map(triangleNumber)
  .takeWhile(_ < 10000)
  .filter(_ >= 1000)
  .toList

def squareNumber(n: Int): Int = n * n
lazy val square = ... // аналогично triangle

def pentagonalNumber(n: Int): Int = n * (3 * n - 1) / 2
lazy val pentagonal =  ... // аналогично triangle

def hexagonalNumber(n: Int): Int = n * (2 * n - 1)
lazy val hexagonal =  ... // аналогично triangle

def heptagonalNumber(n: Int): Int = n * (5 * n - 3) / 2
lazy val heptagonal =  ... // аналогично triangle

def octagonalNumber(n: Int): Int = n * (3 * n - 2)
lazy val octagonal = ... // аналогично triangle

• Затем определим функцию, которая по заданным шести спискам чисел находит все циклические цепочки чисел.

Код:

def getChain(
    list1: List[Int],
    list2: List[Int],
    list3: List[Int],
    list4: List[Int],
    list5: List[Int],
    list6: List[Int]
): List[List[Int]] =
  for
    first  <- list1
    second <- list2
    if first % 100 == second / 100
    third <- list3
    if second % 100 == third / 100
    fourth <- list4
    if third % 100 == fourth / 100
    fifth <- list5
    if fourth % 100 == fifth / 100
    sixth = (fifth % 100) * 100 + first / 100
    if list6.contains(sixth)
  yield List(first, second, third, fourth, fifth, sixth)

• Т.к. исходный набор циклический, то мы можем выбрать, с каких чисел начинать цикл. Т.о. можно начать с чисел octagonal
  , т.к. этот набор самый маленький. Остальные пять наборов могут располагаться в любом порядке. Используем генератор всевозможных перестановок 5 элементов.

Код:

def xvariations[A](l: List[A], n: Int): List[List[A]] =
  def mixmany(x: A, ll: List[List[A]]): List[List[A]] =
    ll match
      case hd :: tl => foldone(x, hd) ::: mixmany(x, tl)
      case _        => Nil

  def foldone(x: A, ll: List[A]): List[List[A]] =
    (1 to ll.length).foldLeft(List(x :: ll))((a, i) =>
      mixone(i, x, ll) :: a
    )

  def mixone(i: Int, x: A, ll: List[A]): List[A] =
    ll.slice(0, i) ::: (x :: ll.slice(i, ll.length))

  if n > l.size then Nil
  else
    l match
      case _ :: _ if n == 1 => l.map(List(_))
      case hd :: tl =>
        mixmany(hd, xvariations(tl, n - 1)) ::: xvariations(tl, n)
      case _ => Nil
end xvariations

val permutations = xvariations(List(triangle, square, pentagonal, hexagonal, heptagonal), 5)

• Осталось перебрать все варианты.

Код:

val chains =
  permutations.flatMap:
    case List(list1, list2, list3, list4, list5) =>
      getChain(octagonal, list1, list2, list3, list4, list5)
    case _ => List.empty

// List(List(1281, 8128, 2882, 8256, 5625, 2512))

Задача №62

Задача №62 - Cubic Permutations

Можно найти перестановки куба \(41063625 (345^{3})\), чтобы получить еще два куба: \(56623104 (384^{3})\) и \(66430125 (405^{3})\). К слову, 41063625 является наименьшим кубом, для которого ровно три перестановки также являются кубами.

Найдите наименьший куб, для которого ровно пять перестановок также являются кубами.

Алгоритм:

Простой перебор дает решение примерно за 50 секунд.

Код:

val allCubes = (1L to 10000L).map(i => i * i * i)
val n        = allCubes.length

def isPermutation(a: Long, b: Long): Boolean =
  a.toString.sorted == b.toString.sorted

val count =
  allCubes.indices.find: i =>
    (i + 1 until n).count(j => isPermutation(allCubes(i), allCubes(j))) == 4

Задача №63

Задача №63 - Powerful Digit Counts

Пятизначное число \(16807=7^5\) является также пятой степенью натурального числа. Аналогично, девятизначное число \(134217728=8^9\) является девятой степенью.

Сколько существует n-значных натуральных чисел, являющихся также и n-ми степенями натуральных чисел?

Алгоритм:

• Тривиальный случай: \(a^1 = 1\), где \(1 \leq a \leq 9\)
• Основанием n-й степени может быть только цифра от 2 до 9 (за исключением тривиального случая), т.к. при \(a \geq 10, a^{n}\) содержит как минимум n + 1 цифр.
• Если \(a^{k}\) состоит из k цифр, и \(a^{k + 1}\) состоит из k цифр, то все последующие \(a^{m}, m > k\) состоят из менее чем m цифр, т.к. a < 10 и не может добавить более 1 цифры при увеличении степени.
• Получается, что необходимо проверить только такие \(a^{k}\), где \(2 \leq a \leq 9\), \(1 \leq k \leq m\), m - первое такое число, что \(a^{m}\) содержит менее m цифр.

Код:

def countGoodNumber(a: Int): Int =
  LazyList
    .from(1)
    .takeWhile { n => BigInt(a).pow(n).toString.length == n }
    .length

val count = 1 + (2 to 9).foldLeft(0)(_ + countGoodNumber(_))

Задача №64

Задача №64 - Odd Period Square Roots

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

\(\sqrt{N} = a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \dots}}}\)

К примеру, рассмотрим \(\sqrt{23}:\)

\(\sqrt{23} = 4 + \sqrt{23} - 4 = 4 + \frac{1}{\frac{1}{\sqrt{23} - 4}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}\)

Продолжив это преобразование, мы получим следующее приближение:

\(\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \dots}}}}\)

Этот процесс можно обобщить в следующем виде:

• \(a_0 = 4, \frac{1}{\sqrt{23} - 4} = \frac {\sqrt{23} + 4}{7} = 1 + \frac {\sqrt{23} - 3}{7}\)
• \(a_1 = 1, \frac{7}{\sqrt{23} - 3} = \frac {7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2}\)
• \(a_2 = 3, \frac{2}{\sqrt{23} - 3} = \frac {2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7}\)
• \(a_3 = 1, \frac{7}{\sqrt{23} - 4} = \frac {7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4\)
• \(a_4 = 8, \frac{1}{\sqrt{23} - 4} = \frac {\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7}\)
• \(a_5 = 1, \frac{7}{\sqrt{23} - 3} = \frac {7 (\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23}-3}{2}\)
• \(a_6 = 3, \frac{2}{\sqrt{23} - 3} = \frac {2(\sqrt{23} + 3)}{14} = 1 + \frac {\sqrt{23}-4}{7}\)
• \(a_7 = 1, \frac{7}{\sqrt{23} - 4} = \frac {7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4\)

Нетрудно заметить, что последовательность является периодической. Для краткости введем обозначение \(\sqrt{23}=[4;(1,3,1,8)]\), чтобы показать что блок (1,3,1,8) бесконечно повторяется.

Первые десять представлений непрерывных дробей (иррациональных) квадратных корней:

• \(\sqrt{2} = [1;(2)]\), период = 1
• \(\sqrt{3} = [1;(1,2)]\), период = 2
• \(\sqrt{5} = [2;(4)]\), период = 1
• \(\sqrt{6} = [2;(2,4)]\), период = 2
• \(\sqrt{7} = [2;(1,1,1,4)]\), период = 4
• \(\sqrt{8} = [2;(1,4)]\), период = 2
• \(\sqrt{10} = [3;(6)]\), период = 1
• \(\sqrt{11} = [3;(3,6)]\), период = 2
• \(\sqrt{12} = [3;(2,6)]\), период = 2
• \(\sqrt{13} = [3;(1,1,1,1,6)]\), период = 5

Период является нечетным у ровно четырех непрерывных дробей при \(N \le 13\).

У скольких непрерывных дробей период является нечетным при \(N \le 10000\)?

Алгоритм:

Определим дробь как \(\frac {irr \times \sqrt{n} + rat}{den}\). Какая будет следующая итерация дроби?

\(\frac {irr \times \sqrt{n} + rat}{den} = whole + \frac {irr \times \sqrt{n} + (rat - whole * den)}{den} = whole + \frac {1}{\frac {den}{irr \times \sqrt{n} + (rat - whole * den)}}\), где whole - целая часть исходной дроби.

Определим \(k = whole * den - rat\). Следующая итерация - это:

\(\frac {den}{irr \times \sqrt{n} - k} = \frac {den (irr \times \sqrt{n} + k)}{irr^2 \times n - k^2} = \frac {den \times irr \times \sqrt{n} + den \times k}{irr^2 \times n - k^2}\)

Определим d как наибольший общий делитель трех чисел: \(den \times irr, den \times k, irr^2 \times n - k^2\). Тогда получим следующую трансформацию дроби:

• \(irr \Rightarrow (den \times irr)/d \)
• \(rat \Rightarrow (den \times k)/d \)
• \(den \Rightarrow (irr^2 \times n - k^2)/d \)

Код:

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

case class Fraction(n: Int, irr: Int, rat: Int, den: Int):
  lazy val nextFraction: Fraction =
    val whole   = ((irr * math.sqrt(n) + rat) / den).toInt
    val k       = whole * den - rat
    val nextIrr = irr * den
    val nextRat = den * k
    val nextDen = n * irr * irr - k * k
    val gcdNum  = gcd(gcd(nextIrr, nextRat), nextDen)
    Fraction(n, nextIrr / gcdNum, nextRat / gcdNum, nextDen / gcdNum)

Fraction(23, 1, 0, 1).nextFraction // (1, 4, 7)
Fraction(23, 1, 4, 7).nextFraction // (1, 3, 2)
Fraction(23, 1, 3, 2).nextFraction // (1, 3, 7)
Fraction(23, 1, 3, 7).nextFraction // (1, 4, 1)
Fraction(23, 1, 4, 1).nextFraction // (1, 4, 7)

Теперь, если n - это не полный квадрат, то запрашиваем следующую итерацию дроби до тех пор, пока следующая итерация не будет найдена среди предыдущих на i-ом месте с конца. Это означает, что цикл замкнулся с длиной i + 1.

Код:

@tailrec
def getCycleCount(memory: List[Fraction]): Int =
  memory match
    case Nil => 0
    case head :: _ =>
      val nextFraction = head.nextFraction
      val index        = memory.indexOf(nextFraction)
      if index != -1 then index + 1
      else getCycleCount(nextFraction :: memory)

def getFraction(n: Int): Int =
  if math.sqrt(n).isWhole then 0
  else getCycleCount(List(Fraction(n, 1, 0, 1)))

getFraction(1) // 0
getFraction(2) // 1
getFraction(3) // 2
getFraction(4) // 0
getFraction(5) // 1
getFraction(6) // 2
getFraction(7) // 4
getFraction(8) // 2
getFraction(9) // 0

val count = (1 to 10000).count(n => getFraction(n) % 2 == 1)

Задача №65

Задача №65 - Convergents of e

Квадратный корень из 2 можно записать в виде бесконечной непрерывной дроби.

\(\sqrt{2} = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + ...}}}}\)

Бесконечную непрерывную дробь можно записать, воспользовавшись обозначением \(\sqrt{2} = [1; (2)]\), где (2) указывает на то, что 2 повторяется до бесконечности. Подобным образом, \(\sqrt{23} = [4; (1, 3, 1, 8)]\).

Оказывается, что последовательность частичных значений непрерывных дробей предоставляет наилучшую рациональную аппроксимацию квадратного корня. Рассмотрим приближения \(\sqrt{2}\).

\(1 + \frac{1}{2} = \frac{3}{2}\)

\(1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5}\)

\(1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12}\)

\(1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}}} = \frac{41}{29}\)

Таким образом, последовательность первых десяти приближений для \(\sqrt{2}\) имеет вид:

\(1, \frac{3}{2}, \frac{7}{5}, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \frac{239}{169}, \frac{577}{408}, \frac{1393}{985}, \frac{3363}{2378}, ...\)

Самое удивительное, что важная математическая константа

\(e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]\).

Первые десять членов последовательности приближений для e перечислены ниже:

\(2, 3, \frac{8}{3}, \frac{11}{4}, \frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}, \frac{1264}{465}, \frac{1457}{536}, ... \)

Сумма цифр числителя 10-го приближения равна 1 + 4 + 5 + 7 = 17.

Найдите сумму цифр числителя 100-го приближения непрерывной дроби для e.

Алгоритм:

1. getESequence(n: Int): IndexedSeq[Int]
   - функция генерирует последовательность чисел цепных дробей, которая используется для вычисления числа Эйлера.
2. getEFractions(n: Int): (BigInt, BigInt)
   - функция возвращает n-ю цепную дробь (с перевернутыми числителем и знаменателем). Для получения n-й цепной дроби проходим последовательность getESequence(n)
   справа, получая следующую итерацию дроби и переворачиваем её для следующей итерации.

Код:

def getESequence(n: Int): IndexedSeq[Int] =
   if n < 3 then IndexedSeq(2, 1).take(n)
   else
     val chain = (2 to n / 3).flatMap(i => IndexedSeq(1, 1, 2 * i))
     IndexedSeq(2, 1, 2).take(n) ++ chain ++ (1 to n % 3).map(_ => 1)

def getEFractions(n: Int): (BigInt, BigInt) =
  getESequence(n).foldRight((BigInt(0), BigInt(1))) { case (i, (num, den)) =>
    (den, i * den + num)
  }

def getSumOfNum(n: Int): BigInt =
  val (_, num) = getEFractions(n)
  num.toString.map(_.getNumericValue).sum

getSumOfNum(10) // 17

Задача №66

Задача №66 - Diophantine Equation

Рассмотрим квадратные диофантовы уравнения вида: \(x^2 - Dy^2 = 1\)

К примеру, для D = 13, минимальное решение x составляет \(649^2 - 13 \times 180^2 = 1\).

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

Найдя наименьшие значения решений x при D = {2, 3, 5, 6, 7}, мы получили следующее:

• \(3^2 - 2 \times 2^2 = 1\)
• \(2^2 - 3 \times 1^2 = 1\)
• \(9^2 - 5 \times 4^2 = 1\)
• \(5^2 - 6 \times 2^2 = 1\)
• \(8^2 - 7 \times 3^2 = 1\)

Таким образом, рассматривая минимальные решения x при \(D \le 7\), было получено наибольшее значение x при D = 5.

Найдите значение \(D \le 1000\) для минимальных решений x, при котором получено наибольшее значение x.

Алгоритм:

Метод «чакравала» для решения уравнения Пелля.

Рассмотрим переход к следующей итерации согласно методу «чакравала»:

• Итерация задается четверкой (a, b, k, d) такой, что \(a^2 - d \times b^2 = k\)
• Итерация считается успешной, если k равно 1 - решение уравнения Пелля найдено
• Для получения следующей итерации используется подстановка: \(a \leftarrow {\frac {am+db}{|k|}}, b \leftarrow {\frac {a+bm}{|k|}}, k \leftarrow {\frac {m^{2}-d}{k}}\)
• m подбирается следующим образом:
  • m считается корректным, если a + b * m кратно |k|
  • положительное m подбирается таким, чтобы \(m^2 - d\) было минимальным по модулю
  • вначале проверяем все "корректные" m от 1 до \(\sqrt{2d}\)
  • если таких не найдено, то начиная с \(\sqrt{2d} + 1\) ищем первое "корректное" m

final case class Iteration(a: BigInt, b: BigInt, k: BigInt, d: Int):
  lazy val isSuccess: Boolean = k == BigInt(1)

  private lazy val getM: BigInt =
    val last = BigInt(math.sqrt(2.0 * d).toInt)
    val maybeM =
      (BigInt(1) to last)
        .filter(isMCorrect)
        .minByOption(i => (i * i - d).abs)

    @tailrec
    def loop(m: BigInt): BigInt =
      if isMCorrect(m) then m else loop(m + 1)

    maybeM.getOrElse(loop(last + 1))
  end getM

  def getNext: Iteration =
    if isSuccess then this
    else
      val m    = getM
      val newA = (a * m + b * d) / k.abs
      val newB = (a + b * m) / k.abs
      val newK = (m * m - d) / k
      Iteration(newA, newB, newK, d)

  private def isMCorrect(m: BigInt): Boolean =
    (a + b * m) % k.abs == BigInt(0)

end Iteration

Для получения минимального решения уравнения Пелля:

• проверяем, что d - не является полным квадратом
• задаем первую итерацию:
  • а - ближайшее целое к корню из d
  • \(k = a^2 - d\)
  • b = 1
• ищем первую успешную (k = 1) итерацию

Код:

final case class DiophantineEquation(d: Int):

  def minimalEquation: Option[(BigInt, BigInt)] =
    val sd = math.sqrt(d.toDouble)
    if sd.isWhole then None
    else
      val a = BigInt(math.round(sd))
      val k = a.pow(2) - d

      @tailrec
      def loop(iteration: Iteration): Option[(BigInt, BigInt)] =
        if iteration.isSuccess then Some((iteration.a, iteration.b))
        else loop(iteration.getNext)

      loop(Iteration(a, BigInt(1), k, d))

DiophantineEquation(67).minimalEquation
// Some((48842,5967))

Итоговое решение задачи:

Код:

def getDWithLargestX(lim: Int): Int =
  (1 to lim).maxBy: d =>
    DiophantineEquation(d).minimalEquation.map(_._1).getOrElse(BigInt(0))

getDWithLargestX(7) // 5

Задача №67

Задача №67 - Maximum Path Sum II

Алгоритм:

Алгоритм аналогичен решению 18-й задачи.

Задача №68

Задача №68 - Magic 5-gon Ring

Рассмотрим следующее "магическое" треугольное кольцо, заполненное числами от 1 до 6, с суммой на каждой линии равной 9.

Проходя по направлению часовой стрелки, начав с группы с наименьшим внешним узлом (в данном примере: 4,3,2), каждое решение можно описать единственным образом. К примеру, вышеуказанное решение можно описать множеством: 4,3,2; 6,2,1; 5,1,3.

Существует возможность заполнить кольцо с четырьмя различными суммами на линиях: 9, 10, 11 и 12. Всего существует восемь решений.

Сумма	Множество решений
9	4,2,3; 5,3,1; 6,1,2
9	4,3,2; 6,2,1; 5,1,3
10	2,3,5; 4,5,1; 6,1,3
10	2,5,3; 6,3,1; 4,1,5
11	1,4,6; 3,6,2; 5,2,4
11	1,6,4; 5,4,2; 3,2,6
12	1,5,6; 2,6,4; 3,4,5
12	1,6,5; 3,5,4; 2,4,6

Объединяя элементы каждой группы, можно образовать 9-тизначную строку. Максимальное значение такой строки для треугольного кольца составляет 432621513.

Используя числа от 1 до 10, в зависимости от расположения, можно образовать 16-тизначные и 17-тизначные строки. Каково максимальное значение 16-тизначной строки для "магического" пятиугольного кольца?

Алгоритм:

Определим, что "магическое" пятиугольное кольцо задается соотношением \(a \to b \to c \Rightarrow d \to c \to e \Rightarrow f \to e \to g \Rightarrow h \to g \to i \Rightarrow j \to i \to b\), где

• (a, b, c, d, e, f, g, h, i, j) - различные числа от 1 до 10
• a + b + c = d + c + e = f + e + g = h + g + i = j + i + b. Следовательно:
  • e = a + b - d
  • g = d + c - f
  • i = f + e - h
  • h + g == b + j
  • j + i == a + c

Условия нахождения максимального 16-значного кольца говорит о том, что 10 должна находиться на "внешней вершине", иначе она "учитывалась" бы дважды и получилось бы 17-е число. Т.к. решение не зависит от "вращения" кольца, то можно предположить a равным 10, т.е. начать поиск решения с "десятки".

Учитывая предыдущие ограничения перебор может быть таким:

Код:

def solutions: IndexedSeq[Long] =
  val a = 10
  for
    b <- 1 to 9
    c <- 1 to 9
    if c != b
    d <- 1 to 9
    if d != b && d != c
    e = 10 + b - d
    if 1 <= e && e <= 9 && e != b && e != c && e != d
    f <- 1 to 9
    if f != b && f != c && f != d && f != e
    g = d + c - f
    if 1 <= g && g <= 9 && g != b && g != c && g != d && g != e && g != f
    h <- 1 to 9
    if h != b && h != c && h != d && h != e && h != f && h != g
    i = f + e - h
    if 1 <= i && i <= 9 && i != b && i != c && i != d && i != e && i != f && i != g && i != h
    j = 45 - b - c - d - e - f - g - h - i
    if j != b && j != c && j != d && j != e && j != f && j != g && j != h && j != i
    if h + g == b + j && j + i == 10 + c
  yield
    val min = math.min(math.min(d, f), math.min(h, j))
    if min == d then s"$d$c$e$f$e$g$h$g$i$j$i$b$a$b$c".toLong
    else if min == f then s"$f$e$g$h$g$i$j$i$b$a$b$c$d$c$e".toLong
    else if min == h then s"$h$g$i$j$i$b$a$b$c$d$c$e$f$e$g".toLong
    else s"$j$i$b$a$b$c$d$c$e$f$e$g$h$g$i".toLong
  end for

Задача №69

Задача №69 - Totient Maximum

Функция Эйлера, \(\phi(n)\) (иногда ее называют фи-функцией) используется для определения количества чисел, меньших n, которые взаимно просты с n. К примеру, т.к. 1, 2, 4, 5, 7 и 8 меньше девяти и взаимно просты с девятью, \(\phi(9)=6\).

n	Взаимно простые числа	phi(n)	n/phi(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

Нетрудно заметить, что максимум \(n/\phi(n)\) наблюдается при n = 6, для \(n \leq 10\).

Найдите значение \(n \leq 1000000\), при котором значение \(n/\phi(n)\) максимально.

Алгоритм:

Согласно функции Эйлера от натурального числа: \(\varphi (n)=n \prod _{p\mid n} \left( 1 - {\frac {1}{p}}\right), n > 1\).

Это означает, что \(\frac{n }{\varphi (n)} = \prod _{p\mid n} \left({\frac {p}{p - 1}}\right)\).

Получается, что на соотношение \(\frac{n }{\varphi (n)}\) не влияет то, с какой степенью в n входит p. Т.е. для \(m = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k} \) и \(o = p_1 \times p_2 \times ... \times p_k \) выполняется \(\frac{m}{\varphi (m)} = \frac{o}{\varphi (o)}\). Поэтому можно рассматривать только те числа, которые являются произведениями различных простых чисел.

Учитывая, что \(\frac{p_i}{p_i - 1} > \frac{p_j}{p_j - 1} \) если \(p_i < p_j\), максимальное соотношение \(\frac{n }{\varphi (n)}\) среди всех чисел менее limit будет для такого \(n = p_1 \times p_2 \times ... \times p_k \) меньшего limit, которое является произведением наименьших возможных различных простых чисел (\(p_1 = 2, p_2 = 3, p_3 = 5\) и т.д.), при том, что \(n * p_{k + 1}\) уже становится больше limit.

Т.к. для всех остальных чисел \(m = p_1^{a_1} \times p_2^{a_2} \times ... \times p_q^{a_q}\) меньших limit следует:

• \(q \leq k\), т.к. иначе \(n * p_{k + 1}\) было бы меньше limit
• \(\frac{m}{\varphi (m)} \leq \frac{n}{\varphi (n)}\), т.к. для всех \(1 \leq i \leq q\) выполняется \(\frac{p_i}{p_i - 1} \leq \frac{ithp}{ithp - 1}\), где ithp - i-е наименьшее простое число.

Код:

def isPrime(n: Long): Boolean = ... // Из Problem 27

def nextPrime(n: Long): Long =
  if !isPrime(n) then 2
  else if n == 2 then 3
  else if n == 3 then 5
  else
    var nextPrime = if n % 3 == 1 then n + 4 else n + 2
    while !isPrime(nextPrime) do
      nextPrime = if nextPrime % 3 == 1 then nextPrime + 4 else nextPrime + 2
    nextPrime

def getMax(limit: Long): Long =
  @tailrec
  def loop(acc: Long, p: Long): Long =
    if acc * p > limit then acc
    else loop(acc * p, nextPrime(p))

  loop(1, 2)

getMax(10) // 6

Задача №70

Задача №70 - Totient Permutation

Функция Эйлера, \(\phi(n)\) (иногда ее называют фи-функцией) используется для определения количества чисел, меньших n, которые взаимно просты с n. К примеру, т.к. 1, 2, 4, 5, 7 и 8 меньше девяти и взаимно просты с девятью, \(\phi(9)=6\).

Число 1 считается взаимно простым для любого положительного числа, так что \(\phi(1)=1\).

Интересно, что \(\phi(87109)=79180\), и, как можно заметить, 87109 является перестановкой 79180.

Найдите такое значение n, \(1 \lt n \lt 10^7\), при котором \(\phi(n)\) является перестановкой n, а отношение \(n/\phi(n)\) является минимальным.

Алгоритм:

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

Код:

def totientArray(limit: Int): Array[Long] =
  val phiArray = new Array[Long](limit + 1)
  phiArray(1) = 1

  val primesArray = primesNoMoreThanN(limit)
  for n <- 1 to limit / 2 do
    var i = 0
    while i < primesArray.length && n * primesArray(i) <= limit do
      val p = primesArray(i)
      phiArray(n * p) = phiArray(n) * (if n % p == 0 then p else p - 1)
      i += 1

  phiArray
  
def getMin(limit: Int): Int =
  val totients = totientArray(limit)
  (2 until limit).minBy: n =>
    val phi = totients(n)
    if phi.toString.sorted == n.toString.sorted then n.toDouble / phi
    else Int.MaxValue

Задача №71

Задача №71 - Ordered Fractions

Рассмотрим дробь \(\dfrac n d\), где n и d являются натуральными числами. Если \(n \lt d\) и \(\operatorname{HCF}(n,d)=1\), то речь идет о сокращенной правильной дроби.

Если перечислить множество сокращенных правильных дробей для d ≤ 8 в порядке возрастания их значений, получим:

\(\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \frac 2 5, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8\)

Нетрудно заметить, что дробь \(\dfrac 2 5\) расположена непосредственно слева от дроби \(\dfrac 3 7\).

Перечислив множество сокращенных правильных дробей для \(d \le 1000000\) в порядке возрастания их значений, найдите числитель дроби, расположенной непосредственно слева от дроби \(\dfrac 3 7\).

Алгоритм:

1. Допустим известен знаменатель дроби \(d_1\). Чему равен числитель \(n_1\)? \(\frac{n_1}{d_1} < \frac{3}{7} \Rightarrow n_1 < \frac{3*d_1}{7}\)
2. Остается перебрать все знаменатели от 2 до d.

Код:

def getFractionByD(d: Int): Int =
  val n = 3.0 * d / 7
  if n.isWhole then n.toInt - 1 else n.toInt

def getFraction(d: Int): (Int, Int) =
  (2 to d).foldLeft((0, 1)) { case ((n1, d1), d2) =>
    val n2 = getFractionByD(d2)
    if n1 * d2 <= n2 * d1 then (n2, d2) else (n1, d1)
  }

getFraction(8) // (2, 5)

Задача №72

Задача №72 - Counting Fractions

Рассмотрим дробь \(\dfrac n d\), где n и d являются натуральными числами. Если \(n \lt d\) и \(\operatorname{HCF}(n,d)=1\), то речь идет о сокращенной правильной дроби.

Если перечислить множество сокращенных правильных дробей для d ≤ 8 в порядке возрастания их значений, получим:

\(\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \frac 2 5, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8\)

Нетрудно заметить, что данное множество состоит из 21 элемента.

Из скольки элементов будет состоять множество сокращенных правильных дробей для \(d \le 1000000\)?

Алгоритм:

Достаточно подсчитать функцию Эйлера для каждого числа от 2 до миллиона и сложить все вместе.

Код:

def getCount(d: Int): Long =
  val totients = totientArray(d) // Из Problem 70
  totients.sum - totients(1)

getCount(8) // 21

Задача №73

Задача №73 - Counting Fractions in a Range

Рассмотрим дробь \(\dfrac n d\), где n и d являются натуральными числами. Если \(n \lt d\) и \(\operatorname{HCF}(n,d)=1\), то речь идет о сокращенной правильной дроби.

Если перечислить множество сокращенных правильных дробей для \(d \le 8\) в порядке возрастания их значений, получим:

\(\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \frac 3 8, \frac 2 5, \frac 3 7, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8\)

Нетрудно заметить, между дробями \(\dfrac 1 3\) и \(\dfrac 1 2\) расположены 3 другие дроби.

Сколько дробей расположено между \(\dfrac 1 3\) и \(\dfrac 1 2\) в упорядоченном множестве сокращенных правильных дробей для \(d \le 12000\)?

Алгоритм:

Необходимо найти для всех знаменателей (d) от 5 до лимита, количество числителей (n), взаимно простых с d, таких что \(\frac d 3 < n < \frac d 2\).

Код:

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

def getCountForD(d: Int): Int =
  val start = (d / 3.0).toInt + 1
  val finish0 = d / 2.0
  val finish = if finish0.isWhole then finish0.toInt - 1 else finish0.toInt
  (start to finish).count(n => gcd(n, d) == 1)

def getCount(limit: Int): Long = (5 to limit).map(getCountForD).sum

getCount(8) // 3

Задача №74

Задача №74 - Digit Factorial Chains

Число 145 известно благодаря такому свойству, что сумма факториалов его цифр равна 145: 1! + 4! + 5! = 1 + 24 + 120 = 145

Возможно, менее известно число 169 - оно создает самую длинную цепочку чисел, которая возвращается к 169. Оказывается, существует только три таких замкнутых цепи:

• \(169 \to 363601 \to 1454 \to 169\)
• \(871 \to 45361 \to 871\)
• \(872 \to 45362 \to 872\)

Нетрудно показать, что ЛЮБОЕ начальное число рано или поздно приведет к замыканию цепи. Например,

• \(69 \to 363600 \to 1454 \to 169 \to 363601 (\to 1454)\)
• \(78 \to 45360 \to 871 \to 45361 (\to 871)\)
• \(540 \to 145 (\to 145)\)

Начав с 69, мы получим цепь из пяти неповторяющхися членов, но самая длинная цепь, начинающаяся с числа меньше миллиона, имеет шестьдесят неповторяющихся членов.

Сколько существует цепей, начинающихся с числа меньше миллиона, содержащих ровно шестьдесят неповторяющихся членов?

Алгоритм:

Подсчет "цепочки" для одного числа большой проблемы не доставляет. Но в случае миллиона чисел грубый подсчет не подойдет, т.к. он многократно увеличивает необходимость считать "цепочку" для одного и того же числа. Например, для чисел 69, 363600 и 1454 придется три раза вычислять цепочку для 1454. Поэтому необходимо сохранять в памяти подсчитанные значения для последующего переиспользования.

Это можно сделать с помощью Функционального состояния.

Для начала определим функцию, подсчитывающую сумму факториалов цифр заданного числа:

• запомним факториалы всех цифр в коллекции factorials

Код:

val factorials = (0 to 9).map(i => (2 to i).product)
@tailrec
def getDigitFactorials(n: Int, acc: Int = 0): Int =
  val newAcc = acc + factorials(n % 10)
  if n < 10 then newAcc
  else getDigitFactorials(n / 10, newAcc)
  
getDigitFactorials(145) // 145  

Определим тип Memory

для хранения значений длины "цепочки" для заданных чисел. И MemoryState

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

opaque type Memory = Map[Int, Int]
private val initialMemory: Memory = Map.empty[Int, Int]

opaque type MemoryState = Memory => (Int, Memory)

Опередим саму "цепочку" Chain

как цепочку чисел, имеющих начальное значение, текущее, а также всю цепочку. Например, цепочка (145)

будет задаваться как Chain(145, 145, List(145))

- цепочка длины 1 с начальным и конечным значением равным 145. При этом конструктор сделаем приватным, чтобы цепочку можно было создавать только по начальному значению. Это гарантирует, что цепочка в любой момент времени не пустая, т.к. создать её можно только по начальному значению и изменять её можно только добавляя звенья цепи.

final case class Chain private (initial: Int, current: Int, links: List[Int]):
  def add(number: Int): Chain =
    Chain(initial, number, number :: links)

object Chain:
  def apply(initial: Int): Chain =
    Chain(initial, initial, List(initial))

Определим метод getChainLoop

, который для заданной цепочки обновляет состояние памяти:

Если для текущего звена цепи в памяти уже сохранено значение, например, для цепи \(69 \to 363600 \to 1454\) в памяти нашлось значение для 1454, то значит, мы наткнулись на ранее подсчитанный цикл, в который не входит "хвост" цепи (69 и 363600) (иначе значения из хвоста были бы внутри цикла и тоже были бы сохранены в памяти). Это означает, что необходимо добавить "хвост" цепи в память: для каждого следующего числа из хвоста значение длины цепи будет на 1 больше предыдущего значения. Обновленную память и значение для первого звена цепи возвращаем в качестве обновленного состояния.

final case class Chain private (initial: Int, current: Int, links: List[Int]):
  ...

  def addTailToMemory(count: Int): MemoryState = memory =>
    val updatedMemory =
      links.zipWithIndex.tail.foldLeft(memory) {
        case (acc, (item, index)) =>
          acc + (item -> (count + index))
      }
    (updatedMemory(initial), updatedMemory)
end Chain   

def getChainLoop(chain: Chain): MemoryState = memory =>
  if memory.contains(chain.current) then
    val count = memory(chain.current)
    chain.addTailToMemory(count)(memory)
  else
    ???

Если значения длины цепочки для текущего звена не найдено, то вычисляем следующее звено цепи - next

. Если next

- новое звено цепи и его нет в текущей цепочке, то значит, до цикла мы ещё не добрались, поэтому вызываем getChainLoop

для новой цепочки с добавленным звеном next

.

def getChainLoop(chain: Chain): MemoryState = memory =>
  if memory.contains(chain.current) then
    ...
  else
    val next = getDigitFactorials(chain.current)
    val idx = chain.links.indexOf(next)
    if idx == -1 then getChainLoop(chain.add(next))(memory)
    else ???

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

Например, цепочка \(69 \to 363600 \to 1454 \to 169 \to 363601\) приводит к следующему элементу 1454, который уже есть в цепи.

• Если следующий элемент найден по индексу idx
  , то это означает, что первые idx + 1
  звеньев цепи составляют цикл, а последующий звенья цепи лишь приводят к этому циклу.
• Для звеньев цепи из цикла длина "цепи" равна длине цикла, т.е. idx + 1
  .
• Для последующих звеньев - на 1 больше, чем длина цепи предыдущего звена.

final case class Chain private (initial: Int, current: Int, links: List[Int]):
  ...

  def addAllChainToMemory(cycleIndex: Int): MemoryState = memory =>
    val updatedMemory =
      links.zipWithIndex.foldLeft(memory) {
        case (acc, (item, index)) =>
          val count = math.max(cycleIndex, index)
          acc + (item -> (count + 1))
      }

    (updatedMemory(initial), updatedMemory)
end Chain

Итого, getChainLoop

примет вид:

def getChainLoop(chain: Chain): MemoryState = memory =>
  if memory.contains(chain.current) then
    val count = memory(chain.current)
    chain.addTailToMemory(count)(memory)
  else
    val next = getDigitFactorials(chain.current)
    val idx  = chain.links.indexOf(next)
    if idx == -1 then getChainLoop(chain.add(next))(memory)
    else chain.addAllChainToMemory(idx)(memory)

Для отдельно заданного значения длину цепи можно подсчитать так:

def getChain(n: Int): Int =
  getChainLoop(Chain(n))(initialMemory)._1

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

Создадим метод getMemoryState

для получения MemoryState

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

opaque type MemoryState = Memory => (Int, Memory)

object MemoryState:
  extension (underlying: MemoryState)
    def run(s: Memory): (Int, Memory) = underlying(s)
    
def getMemoryState(n: Int): MemoryState =
  getChainLoop(Chain(n))  
  
val (count, memory) = getMemoryState(169).run(initialMemory)
// (3, Map(1454 -> 3, 363601 -> 3, 169 -> 3))  

val (count1, memory1) = getMemoryState(363600).run(memory)
// (3, Map(1454 -> 3, 363601 -> 3, 169 -> 3, 363600 -> 4))   

В результате подсчет количества чисел, для которых длина цепочки равна 60, с использованием памяти для сохранения уже посчитанных значений и с использованием методов функционального программирования выглядит так:

val limit = 1_000_000
val (_, result) =
  (1 until limit)
    .foldLeft((initialMemory, 0)) { case ((memory, acc), i) =>
      val (count, newMemory) = getMemoryState(i).run(memory)
      val newAcc             = if count == 60 then acc + 1 else acc
      (newMemory, newAcc)
    }
    
result // Ответ по задаче

Подсчет для миллиона чисел выполняется за 2 секунды.

Задача №75

Задача №75 - Singular Integer Right Triangles

Оказывается, что \(12 cm\) - наименьшая длина проволоки, сгибая которую, можно получить прямоугольный треугольник с целыми сторонами, притом лишь единственным способом. Есть и другие примеры.

• \(12 cm\): \((3,4,5)\)
• \(24 cm\): \((6,8,10)\)
• \(30 cm\): \((5,12,13)\)
• \(36 cm\): \((9,12,15)\)
• \(40 cm\): \((8,15,17)\)
• \(48 cm\): \((12,16,20)\)

В противоположность этим примерам, существуют такие длины проволоки (к примеру, \(20 cm\)), из которых нельзя получить прямоугольный треугольник с целыми сторонами. Другие же длины позволяют найти несколько возможных решений: к примеру, сгибая проволоку длинной \(120 cm\), можно получить ровно три различных прямоугольных треугольника с целыми сторонами. \(120 cm\): \((30,40,50)\), \((20,48,52)\), \((24,45,51)\)

Известно, что длина проволоки составляет L. Для скольких значений \(L \le 1500000\), сгибая проволоку, можно получить ровно один прямоугольный треугольник с целыми сторонами?

Алгоритм:

Нахождение пифагоровых троек с заданной суммой описано в соответствующем разделе.

Код:

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

def isExactlyOneWay(sum: Long): Boolean =
  val s2     = sum / 2
  val sqrt   = math.sqrt(s2.toDouble).toLong
  val mLimit = if sqrt * sqrt == s2 then sqrt - 1 else sqrt

  @tailrec
  def loop(m: Long, count: Int): Int =
    if m > mLimit || count > 1 then count
    else if s2 % m == 0 then
      var sm = s2 / m
      while sm % 2 == 0 do sm /= 2
      val startK = if m % 2 == 1 then m + 2 else m + 1
      val endK   = math.min(2 * m, sm + 1)
      val ncount =
        (startK until endK by 2).count(k => sm % k == 0 && gcd(k, m) == 1)
      loop(m + 1, count + ncount)
    else loop(m + 1, count)

  loop(m = 2L, count = 0) == 1

end isExactlyOneWay

val count = (2 to 1500000 by 2).count(l => isExactlyOneWay(l))

Задача №76

Задача №76 - Counting Summations

Число 5 можно записать в виде суммы ровно шестью различными способами:

• 4 + 1
• 3 + 2
• 3 + 1 + 1
• 2 + 2 + 1
• 2 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1

Сколькими различными способами можно записать число 100 в виде суммы по крайней мере двух натуральных чисел?

Алгоритм:

Это классическая задача о нахождении количества партиций - количество способов записи n в виде суммы натуральных чисел. Единственное изменение - не подходит случай записи числа в виде суммы из одного элемента - себя самого. Поэтому итоговый ответ - число партиций минус 1.

Код:

def partition(number: Int): BigInt =
  val array = new Array[BigInt](number + 1)
  array(0) = BigInt(1)
  if number >= 1 then array(1) = BigInt(1)
  if number >= 2 then array(2) = BigInt(2)

  def partitionPart(s: Int, n: Int, pS: BigInt): BigInt =
    var k  = s
    var op = k * (3 * k - 1) / 2
    var p  = pS
    while op <= n do
      if (k + 1) % 2 == 0 then
        p += array(n - op)
      else
        p -= array(n - op)
      k += s
      op = k * (3 * k - 1) / 2
    p

  for n <- 3 to number do
    val p = partitionPart(1, n, BigInt(0))
    array(n) = partitionPart(-1, n, p)
  array(number)
end partition

def optionsToGetSumAsASumOfAtLeastTwoPositiveNumbers(sum: Int): BigInt =
  partition(sum) - 1

optionsToGetSumAsASumOfAtLeastTwoPositiveNumbers(5) // 6

Задача №77

Задача №77 - Prime Summations

Число 10 можно записать в виде суммы простых чисел ровно пятью различными способами:

• 7 + 3
• 5 + 5
• 5 + 3 + 2
• 3 + 3 + 2 + 2
• 2 + 2 + 2 + 2 + 2

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

Алгоритм:

• Составим "достаточно большой" список простых чисел (достаточно взять все простые числа меньше 100)
• Дальше - классическая задачка о том, сколькими способами можно собрать заданную сумму исходя из заданного набор монет - эта задача обсуждается в Problem 31
• Найти первое число, которое можно собрать более чем 5000 способами

Код:

def primesNoMoreThanN(n: Int): Array[Int] = ... // Из Problem 27

lazy val primes = primesNoMoreThanN(100)

def countWays(coins: Array[Int], sum: Int): Long = ... // Из Problem 31

countWays(primes, 10) // 5

val count = LazyList
  .from(1)
  .find(i => countWays(primes, i) >= 5000)
  .getOrElse(-1)

Задача №78

Задача №78 - Coin Partitions

Пусть p(n) представляет собой число различных способов, которыми можно разделить монеты на несколько столбиков. К примеру, пять монет можно разделить на несколько столбиков ровно семью различными способами, таким образом p(5) = 7.

• OOOOO
• OOOO O
• OOO OO
• OOO O O
• OO OO O
• OO O O O
• O O O O O

Найдите наименьшее значение n, для которого p(n) делится на один миллион без остатка.

Алгоритм:

Как и в Problem 76 - это классическая задача о нахождении количества партиций - количество способов записи n в виде суммы натуральных чисел.

В данном случае необходимо составить "достаточно большой" массив значений партиций (100000 достаточно). А затем найти в массиве первый индекс, значение по которому делится на миллион.

Код:

def partitionArray(number: Int): Array[BigInt] =
  val array = new Array[BigInt](number + 1)
  array(0) = BigInt(1)
  array(1) = BigInt(1)
  array(2) = BigInt(2)

  def partitionPart(s: Int, n: Int, pS: BigInt): BigInt =
    var k  = s
    var op = k * (3 * k - 1) / 2
    var p  = pS
    while op <= n do
      if (k + 1) % 2 == 0 then
        p += array(n - op)
      else
        p -= array(n - op)
      k += s
      op = k * (3 * k - 1) / 2
    p

  for n <- 3 to number do
    val p = partitionPart(1, n, BigInt(0))
    array(n) = partitionPart(-1, n, p)
  array
end partitionArray

def findFirst(n: Int): Option[Int] =
  val arr = partitionArray(n)
  arr.indices.find(i => arr(i) % 1000000 == 0)

Задача №79

Задача №79 - Passcode Derivation

Для проведения операций с банковскими счетами онлайн распространен метод безопасности, заключающийся в том, что пользователя просят указать три случайные символа его кода доступа. К примеру, если код доступа пользователя 531278, у него могут попросить ввести 2-й, 3-й и 5-й символы, и ожидаемым ответом будет 317.

В текстовом файле keylog.txt содержится 50 удачных попыток авторизации.

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

Алгоритм:

1. getRestNumbers

   - функция, принимающая на вход последовательность строк numbers
   и символ digit
   . Возвращает новую последовательность строк, в которой каждая строка начинается с символа digit
   , если она уже начинается с этого символа, иначе она остается неизменной. Затем фильтрует эту последовательность, удаляя пустые строки и строки, которые являются подстроками других строк в последовательности.

2. getMinCode

   - функция, реализующая алгоритм для нахождения минимальной последовательности цифр, в которую "входит" каждое число из numbers
   ("входит" означает, что присутствуют все цифры из числа в том же порядке, но, возможно, со вставками других чисел: например, 680 входит в 61890 (цифры на 1, 3, 5 местах)). Если длина последовательности меньше или равна 1, то возвращается первый элемент последовательности или пустая строка, если последовательность пуста. Если во всех числах цифры разные, то возвращается объединение чисел - не имеет значения, в каком порядке объединять, т.к. более короткий вариант получить не удастся - решение должно содержать все цифры. Если все символы в кандидате уникальны, то он и является минимальным кодом. В противном случае функция находит все уникальные первые символы в строках и для каждого из них формирует "оставшиеся" числа (getRestNumbers
   ), и рекурсивно вызывает getMinCode
   для этих чисел. Результаты этих вызовов объединяются с первым символом, и функция возвращает строку с минимальной длиной.

Код:

def getRestNumbers(numbers: Seq[String], digit: Char): Seq[String] =
  val restNumbers = numbers.map: number =>
    if number.head == digit then number.tail else number

  restNumbers.filterNot: number =>
    number.isEmpty ||
      restNumbers.exists: restNumber =>
        restNumber != number && restNumber.contains(number)
  .distinct

def getMinCode(numbers: Seq[String]): String =
  if numbers.length <= 1 then
    numbers.headOption.getOrElse("")
  else
    val candidate = numbers.mkString
    if candidate.distinct.length == candidate.length then candidate
    else
      val firstDigits = numbers.map(_(0)).distinct
      firstDigits
        .map: digit =>
          val restNumbers = getRestNumbers(numbers, digit)
          s"$digit${getMinCode(restNumbers)}"
        .minBy(_.length)

getMinCode(Seq("680", "180", "690")) 
// "61890"

getMinCode(Seq("319", "680", "180", "690", "129", "620", "762")) 
// "31768290"

Задача №80

Задача №80 - Square Root Digital Expansion

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

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

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

Алгоритм:

Алгоритм вычисления квадратного корня методом Ньютона описан в соответствующем разделе.

Код:

def sqrt(n: BigInt): BigInt =
  var a = BigInt(1)
  var b = (n >> 5) + BigInt(8)
  while b >= a
  do
    val mid = (a + b) >> 1
    if mid * mid > n then b = mid - 1 else a = mid + 1
  a - 1

def getFirst100Sum(n: Int): Int =
  val s = math.sqrt(n)
  if s.isWhole then 0
  else
    val sbi = sqrt(BigInt(n) * BigInt(10).pow(10000))
    sbi.toString.take(100).map(_.getNumericValue).sum

getFirst100Sum(2) // 475

---

Ссылки:

• Project Euler site
• Project Euler chat
• Проект Эйлера на русском