Задача о периоде цепочки чисел

Такого рода задач можно придумать сколько угодно. Представим, например, что у нас есть целое число n = 10 * a + b, то есть a - это результат целочисленного деления n на 10, а b - остаток от деления на 10. Следующее число цепочки образуется по некоторому правилу, например, n = 2 * a + 3 * b, после чего для него так же вычисляются новые значения a и b.

Для любого числа получаются цепочки значений, которые рано или поздно становятся периодическими, например, для чисел 14 и 28 длина периода равна всего единице, так как 2*1+3*4=14 и 2*2+3*8=28, а для других чисел, например, 1357, имеем период, равный шести: 1357 - 291 - 61 - 15 - 17 - 23 - 13 - 11 - 5 - 15 - ...

Задача состоит в том, чтобы выяснить, какова максимально возможная длина периода.

Можно написать скрипт, который просто выполняет перебор:

<?php
 function periodic ($arr) {
  $len = count($arr);
  if ($len < 2) return 0;
  for ($i = 0; $i < $len - 1; $i++) {
   for ($j = $i + 1; $j < $len; $j++) {
    if ($arr[$i] == $arr[$j]) return $j - $i;
   }
  }
  return 0;
 }

 set_time_limit (0);
 $limit = 1000; //верхняя граница поиска
 ob_implicit_flush();
 for ($num = 0; $num <= $limit; $num++) {
  $c = array ();
  $c[] = $num; echo '<b>'. $num.'</b>: ';
  $n = $num;
  while (($p = periodic($c)) == 0) {
   $a = floor($n/10);
   $b = $n % 10;
   $n = 2 * $a + 3 * $b;
   $c[] = $n; echo $n.' ';
  }
  echo '... period = '.$p.'<br>';
  unset ($c);
  ob_flush(); flush();
  usleep (100000); //пауза 100ms
 }
?>

Но можно поискать и аналитические решения. Например, при 2a+3b > 10a+b или b > 4a и при условиях, что b - натуральное число от 0 до 9, а количество цифр в a может только уменьшаться, имеем при a = b = 9, что предельная длина цепочки равна 4*9+9=45. Перебор чисел от 0 до 1000, выполненный скриптом, вполне эту гипотезу подтверждает, правда, периода повторения больше 6 (и вообще отличного от 1, 2 или 6) и не найдено. :)

22.01.2019, 11:42 [1734 просмотра]