Минимальное число с 14 делителями и произведением цифр 14

[gipokrat]

56-значное натуральное число 11121111111111111111111111111111111111711111111111111111 обладает любопытным свойством: у него ровно 14 натуральных делителей, и произведение его десятичных цифр также равно 14.

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

[slavav]

Четырнадцать делителей бывает только у чисел вида $p^{13}$ или $p_1p_2^6$, где $p$, $p_1$, $p_2$ различные простые. Высокая степень одного из сомножителей делает перебор коротким.

Второе соображение сокращающее перебор - в числе с произведением цифр равным четырнадцати, все цифры будут единицы, кроме одной двойки и одной семёрки. То есть, у вас всего несколько тысяч кандидатов.

[wrest]

gipokrat
Перебор показывает, что до этого числа удовлетворяющих условию нет.
Вот функция pari/gp, которая перебирает n-значные числа и выводит подходящее или ноль если подходящего не нашлось.

ktina_27(n)={
  my(base=sum(n=0,n-1,10^n));
  my(candidate=1,nf=[]);
  for(i=0,n-1,
    for(j=0,n-1,
      if(i!=j,
        candidate=base+10^i+6*10^j;
        nf=factor(candidate,2^20);
        if(numdiv(nf)>14,next());
        if(#nf[,1]>2,next());
        if(#nf[,1]==2 && nf[1,2]!=6, next());
        if(#nf[,1]==2 && !ispseudoprime(nf[2,1]),next());
        if(numdiv(candidate)==14,return(candidate));
        );
      );
    );
  return(0);
}

Запуск:

? ktina_27(56)
time = 735 ms.
%1 = 11121111111111111111111111111111111111711111111111111111
?

-- добавлено через 18 минут --

slavav в сообщении #1726153 писал(а):

То есть, у вас всего несколько тысяч кандидатов.

Да, но может попасться длинное число, которое окажется полупростым с примерно равными множителями, и тогда это надолго

[gipokrat]

wrest
Спасибо! Правильно ли я понимаю, что функция перебирает все n-значные кандидаты, поскольку при произведении цифр 14 десятичная запись обязана состоять из единиц, одной двойки и одной семёрки?

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

То есть можно ли считать, что перебор даёт не только первый подходящий пример среди 56-значных кандидатов в порядке данного цикла, но и отсутствие любого меньшего натурального числа с тем же свойством?

[wrest]

gipokrat в сообщении #1726161 писал(а):

Спасибо! Правильно ли я понимаю, что функция перебирает все n-значные кандидаты, поскольку при произведении цифр 14 десятичная запись обязана состоять из единиц, одной двойки и одной семёрки?

Да.

-- добавлено через 32 минуты --

gipokrat в сообщении #1726161 писал(а):

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

Да. Я там запостил улучшенную версию, работает на порядок быстрее.
Для длины 56, из структуры перебора, то что двойка левее семёрки гарантирует что оно наименьшее.

gipokrat в сообщении #1726161 писал(а):

То есть можно ли считать, что перебор даёт не только первый подходящий пример среди 56-значных кандидатов в порядке данного цикла, но и отсутствие любого меньшего натурального числа с тем же свойством?

Напрямую - нет.
Вот этот скрипт гарантирует:

ktina_27W(n)={
  my(base=sum(n=0,n-1,10^n));
  my(candidate=1,nf=[]);
  my(res=List());
  for(i=0,n-1,
    for(j=0,n-1,
      if(i!=j,
        candidate=base+10^i+6*10^j;
        nf=factor(candidate,2^20);
        if(numdiv(nf)>14,next());
        if(#nf[,1]>2,next());
        if(#nf[,1]==2 && nf[1,2]!=6, next());
        if(#nf[,1]==2 && !ispseudoprime(nf[2,1]),next());
        if(numdiv(candidate)==14,listput(res,candidate));
        );
      );
    );
  if(#res==0,return(0));
  return(vecmin(Vec(res)));
}

[wrest]

В общем, в скрипте были ошибки. Спаибо Dmitry40  за указание на некторые из них.
Но мы не привыкли отступать. При помощи ИИ (Дипсик) всё исправлено и вот новый скрипт:

ktina_27D(n)={
  my(base=sum(k=0,n-1,10^k), res=List());
  my(L=2^20);  \\ предел частичной факторизации
  for(i=0,n-1,
    for(j=0,n-1,
      if(i==j, next());
      my(candidate=base+10^i+6*10^j);
      my(f=factor(candidate, L));
      my(pr=List(), ex=List());  \\ простые и показатели
      \\ обрабатываем все строки, кроме последней (если остаток > 1)
      for(k=1, #f[,1]-1,
        listput(pr, f[k,1]);
        listput(ex, f[k,2]);
      );
      my(R = f[#f[,1], 1]);  \\ последний множитель (остаток)
      if(R > 1,
        \\ проверим, не является ли R простым
        if(ispseudoprime(R),
          listput(pr, R);
          listput(ex, 1);
        ,
          \\ проверим, не является ли R = t^6
          my(t = round(R^(1/6)));
          if(t^6 == R && ispseudoprime(t),
            listput(pr, t);
            listput(ex, 6);
          ,
            \\ проверим, не является ли R = t^13
            my(t = round(R^(1/13)));
            if(t^13 == R && ispseudoprime(t),
              listput(pr, t);
              listput(ex, 13);
            ,
              next;  \\ остаток не подходит ни под один вариант
            );
          );
        );
      );
      \\ теперь имеем полный список простых и показателей
      my(np = #pr);
      if(np == 1,
        if(ex[1] == 13, listput(res, candidate));
      );
      if(np == 2,
        if( (ex[1]==6 && ex[2]==1) || (ex[1]==1 && ex[2]==6),
          listput(res, candidate)
        );
      );
    )
  );
  if(#res==0, return(0));
  return(vecmin(Vec(res)));
}

Заодно, в виду необычайной быстроты кода, нашлись ещё такие числа, 65, 83 и 92 знака (наименьшие среди этих количеств знаков в записи)
В скобках количество единиц

[37]2[5]7[21]
[9]2[5]7[67]
[55]2[16]7[19]

-- добавлено через 26 минут --

gipokrat
А где вы отыскали то число что в первом посте? Не сами же придумали?
В общем, есть числа и где сначала идёт 7 а потом 2
Ну и, по всей видимости, таких чисел много (за бесконечность не ручаюсь, но почему бы и нет).

[gipokrat]

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

-- добавлено через 26 минут --

gipokrat
А где вы отыскали то число что в первом посте? Не сами же придумали?
В общем, есть числа и где сначала идёт 7 а потом 2
Ну и, по всей видимости, таких чисел много (за бесконечность не ручаюсь, но почему бы и нет).

Еджипитина помогла:

Еджипитина писал(а):

Спасибо!

Нет, число не было придумано «из головы». Оно было найдено целенаправленным перебором.

Идея такая. Если произведение десятичных цифр равно

$$ 14=2\cdot 7, $$

то в записи числа могут быть только единицы, одна двойка и одна семёрка. Значит, кандидаты имеют вид

$$ [,a,]2[,b,]7[,c,] $$

или

$$ [,a,]7[,b,]2[,c,], $$

где в квадратных скобках указано количество единиц.

Дальше условие «ровно 14 натуральных делителей» тоже сильно ограничивает возможное разложение. Так как

$$ 14=14=7\cdot 2, $$

то число должно иметь один из двух видов:

$$ p^{13} $$

или

$$ p^6q, $$

где (p) и (q) — различные простые числа.

Поэтому перебор получается не по всем числам подряд, а только по позициям цифр (2) и (7), с проверкой двух типов факторизации:

$$ n=p^{13} $$

и

$$ n=p^6q. $$

Моё число в вашей записи имеет вид

$$ [3]2[34]7[17]. $$

Оно равно

$$ 11121111111111111111111111111111111111711111111111111111 ======================================================== 3^6\cdot q, $$

где

$$ q= 15255296448712086572168876695625666819905502210028959 $$

— простое число. Поэтому число его делителей равно

$$ \tau(n)=(6+1)(1+1)=14. $$

А произведение цифр равно

$$ 2\cdot 7=14. $$

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

$$ p^{13} $$

и

$$ p^6q. $$

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

[wrest]

gipokrat в сообщении #1726240 писал(а):

Еджипитина помогла:

Не может быть, они 56-значными числами оперировать не могут.

[gipokrat]

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

gipokrat в сообщении #1726240 писал(а):

Еджипитина помогла:

Не может быть, они 56-значными числами оперировать не могут.

И вот ответ самой Еджипитины:

Еджипитина писал(а):

Тут, по-моему, есть смешение двух разных вещей.

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

Но в данном случае число не «посчитано нейросетью в уме». Нейросеть могла помочь написать или исправить скрипт, а сами вычисления выполняет PARI/GP. А для PARI/GP работа с 56-значными целыми числами — совершенно штатная вещь. Это не астрономический размер для компьютерной алгебры.

То есть схема такая:

$$ \text{ИИ помогает с алгоритмом/кодом,} $$

а затем

$$ \text{PARI/GP выполняет точные целочисленные вычисления.} $$

Поэтому возражение “они не могут оперировать 56-значными числами” справедливо разве что против слепой веры в ответ чат-бота без проверки. Но не против скрипта в PARI/GP.

[wrest]

gipokrat
.