Найдите 2025-е по счёту замечательное число

[gris]

я тут поднатужился и посчитал число из 2 млн знаков, которое по счёту четырёхсептиллионночетырёхквинтиллионнотриллионное!!!(это знак не факториала, а восхищения PARI[S]). Само число привести не могу по воспетой классиком узости полей

[wrest]

Схема моего вычисления такая.
Вычисляем количество цифр в $n$-ом числе,
$l=\left\lfloor\dfrac{\sqrt{8\sqrt{n - 2} + 1} - 1}{2}\right\rfloor$
Генерируем все замечательные числа длиной $l$ по заветам ув. Dendr
Находим нужное там и печатаем.

Генерация делается так. Имеем 6 шаблонов (которые в сумме дают $l^3$ чисел), это сочетания с повторениями, генерируем их все по-шаблонно и соединям.

Процедура (относительно) быстрая но надо много памяти. Для $10^7$-го числа длиной 79 цифр понадобилось ~6ГБайт памяти, и 2 минуты времении.
Генерация получилась не очень оптимальная. Процедура рекурсивная, видимо поэтому.

В https://oeis.org/A343403 заморачиваться с оптимизацией не стали, у них там всё с вычислением этой последовательности плохо, т.к. не нашлось на них ув. Dendr чтобы наставить на путь истинный.

[mihaild]

А в чем соревнование? Число с номером $10^{25}$ равно $3^{1}5^{1160494}7^{139287}8^{765244}9^{449840}$, состоит из 2514866 разрядов, посчиталось за 10 минут на питоне (в гугл колабе).
Матрица перехода, кому лень набивать, такая

Используется синтаксис Python

{
    '23456789': {
        '2': '56789', '3': '5789', '4': '5789', '5': '56789', '6': '789', '7': '789', '8': '89', '9': '9',
    },
    '56789': {
        '5': '56789', '6': '789', '7': '789', '8': '89', '9': '9',
    },
    '5789': {
        '5': '5789', '7': '789', '8': '89', '9': '9',
    },
    '789': {
        '7': '789', '8': '89', '9': '9',
    },
    '89': {
        '8': '89', '9': '9',
    },
    '9': {
        '9': '9',
    },
}

[wrest]

gris в сообщении #1707028 писал(а):

я тут поднатужился и посчитал число из 2 млн знаков, которое по счёту

Ну ясно, какие-то посчитать элементарно, например $k$-e замечательное число
$k=\dfrac{4+(n+1)^2(n+2)^2}{4}$ состоит из $n$ девяток...

-- 24.10.2025, 21:03 --

mihaild в сообщении #1707059 писал(а):

Матрица перехода,

Что такое матрица перехода?

-- 24.10.2025, 21:06 --

mihaild в сообщении #1707059 писал(а):

на питоне

pari/gp наше всё

[mihaild]

wrest в сообщении #1707060 писал(а):

Что такое матрица перехода?

Задачу можно сформулировать так: у нас есть автомат (принимающий замечательные числа), нужно найти $n$-ю строку, которую он принимает. Строки упорядочены по длине, в пределах длины - лексикографически.
Словарь выше - матрица перехода для автомата, который почти нужный (начальное состояние 23456789, принимающие все) - он принимает пустую строку, зато не принимает 1 и 10.

(Оффтоп)

wrest в сообщении #1707060 писал(а):

pari/gp наше всё

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

[wrest]

mihaild в сообщении #1707064 писал(а):

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

Ну я скажу за себя: мне нужен был калькулятор для чисел произвольной точности, работающий на андроиде. pari/gp вписался идеально. Как раз для загадок Ktina в самый раз. А питон... библиотеки это в целом хорошо, но их зависимость от архитектуры или ОС -- уже не очень хорошо. Ну и сам питон очень уж большой.
У меня кстати была мысль перебирать числа и матчить регулярками -- посмотреть быстрее ли это чем делить, но у pari/gp не очень со строковой обработкой. Но питоном заморачиваться не стал.
Регулярка, кстати, вот: ([34]5*7*8*9*|(2)?5*(6?7*8*9*))

[wrest]

mihaild в сообщении #1707059 писал(а):

А в чем соревнование? Число с номером $10^{25}$ равно $3^{1}5^{1160494}7^{139287}8^{765244}9^{449840}$,

Впечатляет
Ну вот от ближайшего слева замечательного числа предыдущей длины (которое из всех девяток) около $10^{19}$ замечательных чисел этой же размерности (количества цифр). 10 минут ушло на пересчёт этих $10^{19}$ ?
Мне кажется, что должен быть путь околомгновенного вычисления, то есть генерации сочетания с повторениями по его номеру. Но я не уверен, науерное Кнута надо читать. Или у ИИ спрашивать.

[mihaild]

wrest в сообщении #1707098 писал(а):

Ну вот от ближайшего слева замечательного числа предыдущей длины (которое из всех девяток) около $10^{19}$ замечательных чисел этой же размерности (количества цифр). 10 минут ушло на пересчёт этих $10^{19}$ ?

Нет конечно.

Используется синтаксис Python

State: TypeAlias = int

class DFA:
  def __init__(self, start: str, final: list[str], transitions: dict[str, dict[str, str]]):
    self._states = sorted(({start}).union(final).union(transitions))
    self._states_order = {s: i for i, s in enumerate(self._states)}

    self._transitions = [[] for i in range(len(self._states))]
    for state_from, edges in  transitions.items():
      for c, s in sorted(edges.items()):
        self._transitions[self._states_order[state_from]].append((c, self._states_order[s]))

    self._start = self._states_order[start]
    self._final = {self._states_order[f] for f in final}

    self.transition_matrix = [[0] * len(self._states) for i in range(len(dfa._states))]
    for _start, edges in enumerate(self._transitions):
      for _, target in edges:
        #self.transition_matrix[_start][target] += 1
        self.transition_matrix[target][_start] += 1
    self._matrix_cum_sums = []
    self._last_matrix = mat_pow(self.transition_matrix, 0)

  def _add_len_matrix(self):
    x = []
    for line in self._last_matrix:
      r = [line[0]]
      for y in line[1:]:
        r.append(r[-1] + y)
      x.append(r)
    self._matrix_cum_sums.append(x)
    self._last_matrix = mat_mul(self._last_matrix, self.transition_matrix)

  def num_words_with_length(self, n: int, state: State | None = None) -> int:
    if state is None:
      state = self._start
    while len(self._matrix_cum_sums) <= n:
      self._add_len_matrix()
    return self._matrix_cum_sums[n][state][-1]

  def nth_word_with_length(self, n: int, l: int, state: State) -> str:
    if n < 0 or l < 0:
      raise ValueError(f"n and l must be non-negative, got {n} and {l}")
    # print(n, l, state)
    if n == 0 and l == 0 and state in self._final:
      return ''
    _n = n
    for c, next_state in self._transitions[state]:
      x = self.num_words_with_length(l - 1, next_state)
      if x > n:
        return self.nth_word_with_length(n, l - 1, next_state) + c
      n -= x
    raise ValueError(f"State {state!r} has only {_n} words of length {l} ({n} requested)")

  def nth_word(self, n: int) -> str:
    l = 0
    while True:
      x = self.num_words_with_length(l)
      if x > n:
        return self.nth_word_with_length(n, l, self._start)[::-1]
      n -= x
      l += 1
 

Как Вы уже поняли, достаточно научиться находить $n$-е слово среди слов длины $l$, принимаемых автоматом. Для этого надо уметь находить общее число слов данной длины, принимаемых автоматом из данного состояния. А дальше берем текущее состояние, минимальное состояние, в которое из него можно перейти, и смотрим - достаточно ли слов из него. Если да, то переходим в него, если нет, то пропускаем, учитываем, что часть слов пропустили, и смотрим следующее состояние.
Я не смотрел на профайл, но вроде бы основное время занимает просто вычисление всех степеней матрицы (у нас там в конце нетривиальное количество длинной (хотя и не очень) арифметики).

[wrest]

wrest в сообщении #1707098 писал(а):

Или у ИИ спрашивать.

Ахахах, ну ИИ прям-таки наше всё. Научился генерировать сочетание по его номеру. $10^7$-разрядное сочетание (из 4-х типов элементов) генерится 30 секунд.
Осталось вычислить к какому шаблону (из перечисленных тут post1706757.html#p1706757) принадлежит число и какое оно по порядку в этом шаблоне.

[wrest]

В общем, из-за того что шестёрка портит всю малину, подряд идут только числа вида 3(5)(7)(8)(9) и 4(5)(7)(8)(9) и там можно очень быстро вычислить сочетание по его номеру. Кстати $10^{25}$-е число как раз оказалось вида 3(5)(7)(8)(9).

-- 25.10.2025, 12:46 --

mihaild в сообщении #1707103 писал(а):

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

Да, смутно мне это понятно, но кажется что из-за непослушной шестёрки тут много перебора.

[mihaild]

wrest в сообщении #1707110 писал(а):

Да, смутно мне это понятно, но кажется что из-за непослушной шестёрки тут много перебора

Это работает одинаково для любого детерменированного автомата.
$n$-е принимаемое слово длины $l$ находится за $O(l \cdot (|A| + |Q|^3))$ арифметических операций.

[wrest]

Кажется, замаячил свет в окошке.
Буду разматывать постепенно.
Цель прежняя - быстро вычислить n-е замечательное число.

Мы знаем от ув. Dendr, что замечательные числа делятся на следующие типы
Тип 1: 2(5)(7)(8)(9)
Тип 2: 2(5)6(7)(8)(9)
Тип 3: 3(5)(7)(8)(9)
Тип 4: 4(5)(7)(8)(9)
Тип 5: (5)(7)(8)(9)
Тип 6: (5)6(7)(8)(9)

А как же они расположена в ряду?

Возьмём замечательные числа конкретной длины $l$
Напомним, что для $n$-го замечательного числа его длина (количество цифр в десятичной записи)
$l(n)=\left\lfloor\dfrac{\sqrt{8\sqrt{n - 2} + 1} - 1}{2}\right\rfloor$
Тут же заметим, на будущее, что числа длины $l$ начинаются с числа
$s(l)=2+\frac14l^2(l+1)^2$
И соответсвенно, наше $n$-ое замечательное число является $k$-ым по порядку в ряду чисел длины $l$
$k(n)=n-s(l)+1$
Тогда
Тип 1 и 2 идут "вперемешку", и количество их (опять же как учит нас ув.Dendr) равно (запись через многочлены представляется тут удобней чем через факториалы)
$F_1(l)=\frac16l(l+1)(l+2)$
$F_2(l)=\frac16l(l-1)(l+1)$
$F_1(l)+F_2(l)=\frac16l(l+1)(2l+1)$ -- это общее количество чисел типов 1 и 2
После "перемешки" чисел типов 1 и 2 последовательно идут числа типов 3 и за ними типов 4
$F_3(l)=F_4(l)=\frac16l(l+1)(l+2)$
Завершает ряд замечательных чисел "перемешка" чисел типов 5 и 6
$F_5(l)=\frac16(l+1)(l+2)(l+3)$
$F_6(l)=\frac16l(l+1)(l+2)$
$F_5(l)+F_6(l)=\frac16(l+1)(l+2)(2l+3)$ -- это общее количество чисел типов 5 и 6

Дальше займемся вычислением в какой тип попало наше замечательное число.

Как именно организована "перемешка"?
Ниже сначала тип, потом через тире - количество. Это для чисел из 6 цифр:
1-1,2-1,1-3,2-3,1-6,2-6,1-10,2-10,1-15,2-15,1-21,3-56,4-56,5-1,6-1,5-3,6-3,5-6,6-6,5-10,6-10,5-15,6-15,5-21,6-21,5-28

[wrest]

Ок, разберемся для начала с Типами 3 и 4.

Функция ниже получает на вход порядковй номер замечательного числа, а возвращает длину числа, номер типа (1-6) и положение числа внутри этого типа.
Пока что я не научился разделять типы 1 и 2, а так же 5 и 6, поэтому для них программа возвращает номер типа 12 и 56 соответственно.

(Оффтоп)

get_pos(n)={
/* функция возвращает вектор: [длина сочетания,тип сочетания,порядковый номер сочетания] */
my(len=floor((sqrt(8*sqrt(n-2)+1)-1)/2)); /* вычисляем длину числа */
my(npos=n-len^2*(len+1)^2/4-1); /* вычисляем позицию числа где единица -- начало ряда чисел нашей длины */
my(small_range=len*(len-1)*(len+1)/6); /* маленький диапазон - 2 фиксированные цифры */
my(medium_range=len*(len+1)*(len+2)/6); /* средний диапазон - одна фиксированная цифра */
my(big_range=(len+1)*(len+2)*(len+3)/6); /* большой диапазон - нет фиксированных цифр */
my(type12_start=1,type12_finish=small_range+medium_range); /* начало и конец типа 12 */
my(type3_start=type12_finish+1,type3_finish=type3_start+medium_range-1); /* начало и конец типа 3 */
my(type4_start=type3_finish+1,type4_finish=type4_start+medium_range-1); /* начало и конец типа 4 */
my(type56_start=type4_finish+1,type56_finish=(len+1)^3); /* начало и конец типа 56 */
if(npos<type12_start,print("get_type_pos: npos too small");return(0));
if(npos<=type12_finish,return([len,12,npos-type12_start+1])); /* число попало в тип 12 */
if(npos<=type3_finish,return([len-1,3,npos-type3_start+1])); /* число попало в тип 3 */
if(npos<=type4_finish,return([len-1,4,npos-type4_start+1])); /* число попало в тип 4 */
if(npos<=type56_finish,return([len,56,npos-type56_start+1])); /* число попало в тип 56 */
print("get_type_npos: npos too big");return(0);
}

Хардкорно запускаем на примере mihaild

? get_pos(10^25)
%147 = [2514865, 3, 414060139352609657]
? ##
***   last result computed in 0 ms.
?

То есть:
Длина сочетания, без учета фиксированных цифр (тройки) будет равна 2514865 цифр -- это сочетание надо будет вычислять потом.
Шаблон 3, т.е. фиксированная цифра 3 (перед сочетанием)
Номер сочетания в ряде сочетаний из 4 элементов длины 2514865 отсортированном в лексикографическом порядке, равен 414060139352609657

Теперь вычисляем собсно сочетание.
Функция вчерне готова (спасибо за помощь chatGPT),

(Оффтоп)

gcr(n, k, r, base=1) =
{
  if (n < 1 || k < 0, error("n must be >=1 and k must be >=0"));

  my(m = n + k - 1, t = n - 1, total = binomial(m, t));

  /* привести r к 0-based */
  if (base == 1, r = r - 1);

  if (r < 0 || r >= total, error("r out of range (0..", total-1, ") after base adjust"));

  /* --- ВЕРТИКАЛЬ: инвертируем ранг, чтобы порядок стал лексикографическим по неубыванию --- */
  r = total - 1 - r;

  /* тривиальные случаи */
  if (t == 0, return([k]));    /* n==1 */

  /* выбираем позиции перегородок (1..m) */
  my(seps = vector(t), prev = 0, cnt, s);
  for (j = 1, t,
    for (s = prev + 1, m - (t - j),
      cnt = binomial(m - s, t - j);
      if (r >= cnt,
        r -= cnt;
        next;
      ,
        seps[j] = s;
        prev = s;
        break;
      );
    );
  );

  /* переводим позиции перегородок в кратности (число звёзд между ними) */
  my(x = vector(n));
  x[1] = seps[1] - 1;
  for (j = 2, t, x[j] = seps[j] - seps[j-1] - 1);
  x[n] = m - seps[t];

  return(x);
}

Запускаем:

? gcr(4,get_pos(10^25)[1],get_pos(10^25)[3])
time = 1,675 ms.
%148 = [1160494, 139287, 765244, 449840]
?

Получаем вектор кратностей элементов [5,7,8,9] в нужном нам сочетании и смотрим на то, что получилось у mihaild

mihaild в сообщении #1707059 писал(а):

Число с номером $10^{25}$ равно $3^{1}5^{1160494}7^{139287}8^{765244}9^{449840}$, состоит из 2514866 разрядов, посчиталось за 10 минут на питоне (в гугл колабе).

Вроде всё норм.
Полторы секунды. Но ещё не готова "перемешка". Там немного муторно писать, но считаться будет так же быстро.

P.S. Следующая высота, которую предлагается взять -- число $20^{25}$
P.P.S. Высота продержалась две минуты
Кратности цифр замечательного числа под номером $20^{25}$:
3:1; 5:1420700; 7:16335714; 8:136434330; 9:37213898

-- 26.10.2025, 00:20 --

gris в сообщении #1707028 писал(а):

я тут поднатужился и посчитал число из 2 млн знаков, которое по счёту четырёхсептиллионночетырёхквинтиллионнотриллионное!!!

А по порядку $20^{2^5}$-е можете посчитать?

[wrest]

В общем, дописал я функцию.
Немного длинно получилось, правда.
Основной цикл работает весьма быстро.
На вход даём номер замечательного числа, на выходе получаем вектор кратности цифр в виде [цифра1,количество],...

1. comb(n)={ 
2. /* функция возвращает вектор кратностей цифр n-го замечательного числа */ 
3. /* входной контроль */ 
4. if(n<1,error("n must be positive, got n=",n)); 
5. /* нерегулярные случаи */ 
6. if(n<10,return([[n,1]])); 
7. if(n==10,return([[1,1],[0,0]])); /* тут по неубыванию не выходит */ 
8.  
9. /* начало основного вычисления */ 
10. my(len=floor((sqrt(8*sqrt(n-2)+1)-1)/2)); /* вычисляем длину числа -- количество цифр в нём */ 
11. my(npos=n-len^2*(len+1)^2/4-1); /* вычисляем относительную позицию числа где единица -- начало ряда чисел нашей длины */ 
12.  
13.      /* Определяем фиксированные цифры */ 
14.     my(fixed_digits = vector(7)); 
15.     fixed_digits[1] = [[2, 1]];      /* тип 1 */ 
16.     fixed_digits[2] = [[2, 1], [6, 1]];  /* тип 2 */ 
17.     fixed_digits[3] = [[3, 1]];      /* тип 3 */ 
18.     fixed_digits[4] = [[4, 1]];      /* тип 4 */ 
19.     fixed_digits[5] = [];            /* тип 5 */ 
20.     fixed_digits[6] = [[6, 1]];      /* тип 6 */ 
21.      
22.     /* Вычисляем размеры диапазонов для каждого из 6 типов*/ 
23.     my(type_len=vector(6,i,len-#fixed_digits[i])); /* длина сочетания равна длине числа минус количество фиксированных цифр */ 
24.     my(type_range=vector(6,i,(type_len[i]+1)*(type_len[i]+2)*(type_len[i]+3)/6)); /* тетраэдральные числа */ 
25.     my(type_finish=vector(6,i,sum(j=1,i,type_range[j]))); /* концы диапазонов шаблонов */ 
26.  
27.   /* Определяем тип числа */ 
28.     my(type_num, type_pos); 
29.     if(npos <= type_finish[2], 
30.         type_num = 2; type_pos = npos; 
31.     , npos <= type_finish[3], 
32.         type_num = 3; type_pos = npos - type_finish[2]; 
33.     , npos <= type_finish[4], 
34.         type_num = 4; type_pos = npos - type_finish[3]; 
35.     , npos <= type_finish[6], 
36.         type_num = 6; type_pos = npos - type_finish[4]; 
37.     , 
38.         error("npos too big: ", npos) 
39.     ); 
40.  
41.  /* Обрабатываем составные типы 12 и 56, которые идут вперемешку */ 
42.   
43.     if(type_num == 2 || type_num == 6,  
44.         my(m = floor((3*type_pos)^(1/3))); /* примерно куб, иначе пришлось бы по формуле Кардано */ 
45.         if(m*(m+1)*(m+2)/3 >= type_pos, m--); /* если не попали, корректируемся */ 
46.          
47.         my(Sm = m*(m+1)*(m+2)/6); 
48.         my(offset = type_pos - 2*Sm); 
49.         my(L = (m+1)*(m+2)/2); 
50.          
51.         my(subtype = if(offset <= L, 1, 0)); 
52.         type_pos = Sm + if(subtype == 1, offset, offset - L); 
53.          
54.         /* Преобразуем в окончательный тип 1 2 или 5 6*/ 
55.         type_num=type_num-subtype; 
56. ); 
57.  
58.     /* начинаем вычислять кратности цифр 5789 */ 
59.    my(elts=[5,7,8,9]); /* вектор элементов для генерации их сочетания */     
60.    my(v_mult=vector(#elts,i,vector(2))); /* заготавливаем вектор кратностей цифр 5789 */ 
61.      
62.     /*  
63.    Вычисляем вектор кратностей для сочетания с повторениями 
64.    номер type_pos, из #elts элементов по type_len[type_num], в лексикографическом порядке  
65.    по неубывающим  последовательностям (т.е. сначала все минимальные элементы). 
66. */ 
67.   my(n=#elts); 
68.   my(m = n + type_len[type_num] - 1, t = n - 1, total = binomial(m, t)); 
69.  
70.   /* приводим type_pos к 0-based */ 
71.   type_pos = type_pos - 1; 
72.  
73.   /* инвертируем позицию, чтобы порядок стал лексикографическим по неубыванию --- */ 
74.   type_pos = total - 1 - type_pos; 
75.  
76.   /* выбираем позиции перегородок (1..m) */ 
77.   my(seps = vector(t), prev = 0, cnt, s); 
78.   /* основной цикл, хорошо работает до длин 10^8 */ 
79.   for (j = 1, t, 
80.     for (s = prev + 1, m - (t - j), 
81.       cnt = binomial(m - s, t - j); 
82.       if (type_pos >= cnt, 
83.         type_pos = type_pos-cnt; 
84.         next; 
85.       , 
86.         seps[j] = s; 
87.         prev = s; 
88.         break; 
89.       ); 
90.     ); 
91.   ); 
92.  
93.   /* переводим позиции перегородок в кратности (число звёзд между ними) */ 
94.    
95.   for(i=1,n,v_mult[i][1]=elts[i]); 
96.   v_mult[1][2] = seps[1] - 1; 
97.   for (j = 2, t, v_mult[j][2] = seps[j] - seps[j-1] - 1); 
98.   v_mult[n][2] = m - seps[t]; 
99.   /* добавляем фиксированные цифры и сортируем результат по неубыванию */ 
100.    v_mult = vecsort(concat(v_mult, fixed_digits[type_num])); /* в принципе, готовои ещё чуть: */ 
101.   
102.      /* удаляем нулевые кратности */ 
103.      my(res=[]); 
104.      for(i=1,#v_mult,if(v_mult[i][2]>0,res=concat(res,[v_mult[i]]))); 
105.  
106.      return(res); 
107. } 

Запускаем:

? comb(2025)
%2 = [[8, 1], [9, 7]]
? comb(10^10)
time = 2 ms.
%3 = [[5, 213], [6, 1], [7, 81], [8, 122], [9, 29]]
? comb(10^20)
time = 78 ms.
%4 = [[5, 24252], [7, 30922], [8, 45059], [9, 41187]]
? comb(10^25)
time = 1,248 ms.
%5 = [[3, 1], [5, 1160494], [7, 139287], [8, 765244], [9, 449840]]
? comb(20^25)
time = 1min, 48,938 ms.
%6 = [[3, 1], [5, 1420700], [7, 16335714], [8, 136434330], [9, 37213898]]
?

2 миллисекунды на вычисление замечательного числа номер $10^{10}$

[wrest]

Дополнил генератор вектора кратности конвертором в число

convert_comb(v_mult)={
if(v_mult==[[1, 1], [0, 0]], return(10));
my(v=[]);
for(i=1,#v_mult,
   for(j=1,v_mult[i][2],
       v=concat(v,v_mult[i][1])));
return(fromdigits(vecsort(v)))}

Запуск:

? convert_comb(comb(2025))
time = 1 ms.
%40 = 89999999
?