Гипотеза о факториале из нефакториальных цифр

[Ktina]

Назовём десятичную цифру факториальной, если число, обозначаемое ею, является факториалом натурального числа (речь идёт о цифрах 1, 2 и 6, и только о них), и нефакториальной в противном случае.

5040 - единственный (ли?) факториал, все цифры которого нефакториальны.

Гипотеза:
Число 5040 является единственным факториалом натурального числа, состоящим только из нефакториальных десятичных цифр (то есть, цифр, не являющихся цифрами 1, 2 и 6).

А вот верна ли она?

[gris]

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

[Legioner93]

Чисто статистически должна быть верна. Похоже, начиная с 42! факториалы содержат все десятичные цифры

[Pphantom]

Численный эксперимент - наше все. До $18000!$ гипотеза работает, а дальше пока не знаю, возиться с распараллеливанием мне было лень.

[Dmitriy40]

Работает даже до $10^8!$.
Вместо распараллеливания можно хранить лишь примерно 60 младших ненулевых цифр, при этом умножение на число до $2^{32}$ делается не так уж сложно.

[Pphantom]

Dmitriy40 в сообщении #1146588 писал(а):

Работает даже до $30000000!$.
Вместо распараллеливания можно хранить лишь примерно 60 младших ненулевых цифр, при этом умножение на число до $2^{32}$ делается не так уж сложно.

Ну, это совсем лень. Меня хватило на предельно тупой скриптик в пять строчек.

[Nemiroff]

Как там все любят делать?
A137580
A182049

[Yadryara]

Nemiroff
Об чём и речь недавно была. Разве ж трудно это было проверить...
То бишь, начиная с $42!$ уже все $10$ цифр встречаются постоянно.

GAA:

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

[Ktina]

Yadryara в сообщении #1146597 писал(а):

Nemiroff
То бишь, начиная с $42!$ уже все $10$ цифр встречаются постоянно.

Nemiroff в сообщении #1146592 писал(а):

Как там все любят делать?
A182049

Там написано:

Цитата:

conjecture: sequence is finite and a(32) = 41 is the last term.

Стало быть, ещё ничего не доказано.

[Pphantom]

(Dmitriy40)

Dmitriy40 в сообщении #1146588 писал(а):

Работает даже до $10^8!$.
Вместо распараллеливания можно хранить лишь примерно 60 младших ненулевых цифр, при этом умножение на число до $2^{32}$ делается не так уж сложно.

Что-то меня это заело и я занялся добросовестным программированием. Получилось выжать проверку до $10^9!$ за полторы минуты (на одном ядре).

[Legioner93]

Pphantom
А выложите код, может ещё ускорим

[Pphantom]

Legioner93 в сообщении #1146654 писал(а):

А выложите код, может ещё ускорим

Да я и сам его пока могу ускорить.

[mihaild]

До $10^9$ за $24$ секунды (но не очень тщательно протестировано).
До $10^{10}$ решений не обнаружено.

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

#include <iostream>
#include <ctime>
#include <vector>
#include <cassert>

constexpr size_t MOD = 1000000;
constexpr size_t DIGITS = 10;

struct mod10num {
    unsigned long long int digits[DIGITS];
    std::vector<bool> bad;
    mod10num(): bad(MOD, false) {
        for (size_t i = 0; i < DIGITS; ++i) {
            digits[i] = 0;
        }
        digits[0] = 1;
        for (size_t i = 0; i < bad.size(); ++i) {
            for (size_t j = i; j; j /= 10) {
                bad[i] = bad[i] || (j % 10 == 1 || j % 10 == 2 || j % 10 == 6);
            }
        }
    }
    mod10num& operator*=(unsigned long long int n) {
        for (size_t i = 0; i < DIGITS; ++i) {
            digits[i] *= n;
        }
        while (digits[0] % 10 == 0) {
            digits[0] /= 10;
            for (size_t i = 1; i < DIGITS; ++i) {
                digits[i - 1] += digits[i] % 10 * (MOD / 10);
                digits[i] /= 10;
            }
        }
        for (size_t i = 1; i < DIGITS; ++i) {
            digits[i] += digits[i - 1] / MOD;
            digits[i - 1] %= MOD;
        }
        digits[DIGITS - 1] %= MOD;
        return *this;
    }
    bool check() const {
        for (size_t i = 0; i < DIGITS; ++i) {
            if (bad[digits[i]]) {
                return false;
            }
        }
        return true;
    }
};

std::ostream& operator<<(std::ostream& os, const mod10num& r) {
    os << '(';
    for (size_t i = 0; i < DIGITS; ++i) {
        os << r.digits[i] << ' ';
    }
    os << ')';
    return os;
}

int main() {
    mod10num r;
    clock_t t = clock();
    for (unsigned long long int n = 1; ; ++n) {
        r *= n;
        if (r.check()) {
            std::cout << "OK: " << ' ' << n << ' ' << r << std::endl;
        }
        if (n % 10000000 == 0) {
            std::cout << n << ' ' << static_cast<double>(clock() - t) / CLOCKS_PER_SEC << std::endl;
        }
    }
    return 0;
}
 

[Pphantom]

Мое сооружение несколько медленнее (правда, у меня и Ваше работает больше минуты), но, пожалуй, попроще.

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

program zz
  implicit none

  integer,parameter :: ki=8               ! KIND-параметр типа
  integer,parameter :: c=range(1_ki)/2    ! Число цифр в ячейке
  integer(ki),parameter :: fi=10**c       ! Размер одной ячейки
  integer,parameter :: d=70/c             ! Длина массива

  integer(ki) :: i,z,p
  integer(ki),dimension(0:d) :: n
  integer :: k,pp,j

  n=0
  n(1)=1

main:  do i=1,1000000000
        z=0
        do k=0,d
          z=n(k)*i+z/fi
          n(k)=modulo(z,fi)
        end do

        do while(n(0)==0)
          n=eoshift(n,1,0_ki)
        end do

        do k=0,d
          p=n(k)
          do j=1,c
            pp=mod(p,10)
            if((pp==1).or.(pp==2).or.(pp==6)) cycle main
            p=p/10
          end do
        end do
        write(*,*) "НАШЛИ ",i
      end do main

end program zz

[Dmitriy40]

Pphantom в сообщении #1146646 писал(а):

Получилось выжать проверку до $10^9!$ за полторы минуты (на одном ядре).

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

До $10^9$ за $24$ секунды

Не, у меня всё сильно скромнее, порядка на два медленнее, до $10^9$ не дождался, а до $10^8$ проверяется около 7 минут:

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

{$APPTYPE CONSOLE}

uses    SysUtils;

var     f: array[0..7] of integer;//int32 mod 10^9

function Check(): boolean;
var     i, d, x: integer;
begin
        Result := false;
        for i := 0 to High(f) do begin
                x := f[i];
                while x > 0 do begin
                        d := x mod 10; x := x div 10;
                        if d in [1, 2, 6] then exit;
                end;
        end;
        Result := true;
end;

var     n, i, c: integer;
        m: int64;
begin
        f[0] := 1; for i := 1 to High(f) do f[i] := 0;
        for n := 2 to round(1e9) do begin
                c := 0;
                for i := 0 to High(f) do begin
                        m := f[i]; m := m * n + c; c := m div 1000000000; f[i] := m mod 1000000000;
                end;
                if f[0] = 0 then begin
                        for i := 1 to High(f) do f[i - 1] := f[i];
                        f[High(f)] := 0;
                end;
                if not Check() then continue;
                Write(n, '!=..'); for i := High(f) downto 0 do Write(Format('%9.9u', [f[i]])); Writeln;
        end;
end.
 

-- 26.08.2016, 03:01 --

Pphantom
mihaild
Друзья, я невольно ввёл и Вас и себя в заблуждение словами

Dmitriy40 в сообщении #1146588 писал(а):

можно хранить лишь примерно 60 младших ненулевых цифр,

После обдумывания и написания теста это оказалось не совсем правдой. При сдвиге результата умножения вправо надо уменьшать количество верных цифр (но можно не всегда), вот пример некорректности поведения для хранения 6-ти младших цифр:
$14! = 871782912$, младшие 6 цифр (только они и хранимые в примере): $782912$, пока было всё хорошо, но вот при вычислении следующего факториала беда:
$15! = 1307674368$, младшие 6 цифр: $674368$, но $\frac{782912 \cdot 15}{10} \mod 10^6 = 174368$, т.е. не совпадает с точным значением факториала в старшей цифре.
Забавно, что следующие факториалы снова совпадают до $25!$, у которого не совпадают уже две старшие цифры.

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