Мультипликативная стойкость числа по Слоуну

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

Multiplicative persistence (на русский часто неверно переводят как "продолжительность жизни") натурального числа по основателю OEIS тов. Слоуну означает количество итераций, которое нужно сделать, чтобы получить однозначное число перемножением ненулевых цифр предыдущего числа. Процесс повторяется до тех пор, пока не получится однозначное число. Например, 88 это 8*8 = 64, 64 даёт 6*4 = 24, 24 превращается в 2*4 = 8. Таким образом, число 88 имеет "поколение", равное трём, требуется три шага, чтобы добраться до одной цифры. У чисел из одной цифры поколение "нулевое".

Саму последовательность можно увидеть вот тут, в исходном виде она не слишком информативна, интересней, например, вот эта последовательность, n-ый член которой есть наименьшее число с поколением, равным n (числа натуральные и имеют минимум две цифры.) Первый член последовательности равен 10, так как 1*0 = 10 - наименьшее двузначное число с продолжительностью жизни "один". Второй член равен 25, потому что 25 = 2*5 = 10 и это наименьшее число, которое упрощается за два шага.

Любопытно, что первое число 11-го "поколения" равно 277777788888899 (предел счёта для 32-разрядного беззнакового целого равен 4294967295), а найти чисел с персистентностью выше 11 Слоуну не удалось при аналитическом и алгоритмическом анализе значений вплоть до 10²³³. Проверить "напрямую" числа в таком диапазоне он, как понимаете, не мог.

Во избежание ещё более медленной работы при отладке, мы не стали делать в приложенном консольном листинге C# шаблон или отдельный класс для SortedMultiSet.

Одноимённые методы getPersistence позволяют узнать поколение чисел типов uint и System.Numerics.BigInteger.

Вот листинг программки, проверенной в актуальной сборке Visual Studio 2019, и интересные результаты для распределения чисел от 10 до UInt32.MaxValue.

using System;
using System.Collections.Generic;
using System.Numerics;

namespace ConsoleApp1 {

 public class Persistence {
  public static uint getPersistence (uint n, ref uint count) {
   if (n < 10) return count;
   count++;
   uint p = 1, m;
   do {
    m = n % 10;
    if (m != 0) p *= m;
    n /= 10;
   } while (n != 0);
   return getPersistence(p,ref count);
  }
  public static uint getPersistence (BigInteger n, ref uint count) {
   if (n < 10) return count;
   count++;
   BigInteger p = 1, m;
   do {
    m = n % 10;
    if (m != 0) p *= m;
    n /= 10;
   } while (n != 0);
   return getPersistence (p, ref count);
  }
 }

 public class Program {
  static void Main () {
   uint p;
   
   //Проверим все числа от 10 до 4294967295 (для архитектуры x64)
   Dictionary<uint, uint> multiSet = new Dictionary<uint, uint> ();
   for (uint i = 10; i <= UInt32.MaxValue; i++) {
    p = 0;
    Persistence.getPersistence (i,ref p);
    if (multiSet.ContainsKey (p)) multiSet [p]++;
    else multiSet [p] = 1;
    if (i % 1000000 == 0) Console.Write ('.'); //~4300 точек - конец процесса
   }
   Console.WriteLine ();
   foreach (var pair in multiSet) {
    Console.WriteLine ($"{pair.Key}\t{pair.Value}");
   }
   
   //Проверим число 277777788888899 - первое с персистентностью 11
   BigInteger big = 277777788888899;
   p = 0;
   Persistence.getPersistence (big, ref p);
   Console.WriteLine ($"{big}\t{p}");
   
   //Проверим число 2^1000
   big = BigInteger.Pow (2, 1000);
   p = 0;
   Persistence.getPersistence (big, ref p);
   Console.WriteLine ($"{big}\t{p}");

   Console.ReadLine ();
  }
 }
}

Последнее число состоит из 302 цифр и потому разорвано:

1  123894
2  127201791
3  1230011123
4  2026622328
5  682053430
6  135506504
7  70908102
8  19978229
9  2560625
10 1260
277777788888899 11
10715086071862673209484250490600018105614048117055336074437503883703510511249361
22493198378815695858127594672917553146825187145285692314043598457757469857480393
45677748242309854210746050623711418779541821530464749835819412673987675591655439
46077062914571196477686542167660429831652624386837205668069376  9

Для проверки только наименьших чисел с мультипликативной персистентностью n = 1,2,...,11 (A003001) подойдёт следующий вид главной программы:

 public class Program {
  static void Main () {
   uint p;
   BigInteger [] arr = new BigInteger [] 
    { 10, 25, 39, 77, 679, 6788, 68889, 2677889, 26888999, 3778888999, 277777788888899 };
   foreach (var val in arr) {
    p = 0;
    Persistence.getPersistence (val, ref p);
    Console.WriteLine ($"{val}\t{p}");
   }
   Console.ReadLine ();
  }
 }

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

using System;
using System.Collections.Generic;
using System.Numerics;

namespace ConsoleApp1 {
 public class Persistence {
  public static List <BigInteger> Lst = new List <BigInteger> ();
  public static BigInteger getPersistence (BigInteger n, ref BigInteger count) {
   if (count == 0) Lst.Clear ();
   if (n < 10) return count;
   count++;
   BigInteger p = 1, m;
   do {
    m = n % 10;
    if (m != 0) p *= m;
    n /= 10;
   } while (n != 0);
   Lst.Add (p);
   return getPersistence (p, ref count);
  }
 }

 public class Program {
  static void Main () {
   BigInteger p;
   BigInteger [] arr = new BigInteger [] { 
     277777788888899,
     999999999999999,
     0
   };
   String str = 
    "999999999999999999999999999999999999999999999999999999999";
   arr.SetValue(BigInteger.Parse (str),2);
   foreach (var val in arr) {
    p = 0;
    Persistence.getPersistence (val, ref p);
    Console.Write ($"{val}\t{p} (");
    var cnt = Persistence.Lst.Count;
    for (var i = 0; i < cnt; i++) {
     var div = (i < cnt - 1 ? ", " : "");
     var item = Persistence.Lst[i];
     Console.Write ($"{item}{div}");
    }
    Console.WriteLine (")");
   }
   Console.ReadLine ();
  }
 }
}

19.05.2024, 16:15 [177 просмотров]