2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 16:56 
Аватара пользователя


01/12/11

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

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

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

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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 18:17 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 19:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 20:02 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 20:12 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 20:18 
Заслуженный участник


09/05/12
25179
Dmitriy40 в сообщении #1146588 писал(а):
Работает даже до $30000000!$.
Вместо распараллеливания можно хранить лишь примерно 60 младших ненулевых цифр, при этом умножение на число до $2^{32}$ делается не так уж сложно.
Ну, это совсем лень. :-) Меня хватило на предельно тупой скриптик в пять строчек.

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 20:25 
Заслуженный участник


20/07/09
4026
МФТИ ФУПМ
Как там все любят делать?
A137580
A182049

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 20:34 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 22:20 
Аватара пользователя


01/12/11

8634
Yadryara в сообщении #1146597 писал(а):
Nemiroff
То бишь, начиная с $42!$ уже все $10$ цифр встречаются постоянно.

Nemiroff в сообщении #1146592 писал(а):
Как там все любят делать?
A182049

Там написано:
Цитата:
conjecture: sequence is finite and a(32) = 41 is the last term.

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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 23:05 
Заслуженный участник


09/05/12
25179

(Dmitriy40)

Dmitriy40 в сообщении #1146588 писал(а):
Работает даже до $10^8!$.
Вместо распараллеливания можно хранить лишь примерно 60 младших ненулевых цифр, при этом умножение на число до $2^{32}$ делается не так уж сложно.
Что-то меня это заело и я занялся добросовестным программированием. :-) Получилось выжать проверку до $10^9!$ за полторы минуты (на одном ядре).

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 23:19 
Заслуженный участник
Аватара пользователя


28/07/09
1178
Pphantom
А выложите код, может ещё ускорим

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение25.08.2016, 23:27 
Заслуженный участник


09/05/12
25179
Legioner93 в сообщении #1146654 писал(а):
А выложите код, может ещё ускорим
Да я и сам его пока могу ускорить. :D

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение26.08.2016, 00:10 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
До $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;
}
 

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение26.08.2016, 01:34 
Заслуженный участник


09/05/12
25179
Мое сооружение несколько медленнее (правда, у меня и Ваше работает больше минуты), но, пожалуй, попроще. :-)
код: [ скачать ] [ спрятать ]
Используется синтаксис 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

 Профиль  
                  
 
 Re: Гипотеза о факториале из нефакториальных цифр
Сообщение26.08.2016, 02:24 
Заслуженный участник


20/08/14
11066
Россия, Москва
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$, т.е. не совпадает с точным значением факториала в старшей цифре. :facepalm:
Забавно, что следующие факториалы снова совпадают до $25!$, у которого не совпадают уже две старшие цифры.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group