Дж. Максфилд доказал следующую теорему (см. DOI: 10.2307 / 2688966 ):

Если $A$ является любым положительным целым числом, имеющим $m$ цифр, существует такое положительное целое число $N$ , что первые $m$ цифр $N!$ представляют собой целое число $A$ .

Вызов

Вашему вызову дан некоторый найдите соответствующий . $A \geqslant 1$ $N \geqslant 1$

Детали

$N!$ представляет факториал из . $N! = 1\cdot 2 \cdot 3\cdot \ldots \cdot N$ $N$
В нашем случае цифры понимаются как основание . $A$ $10$
Ваша заявка должна работать для произвольного $A\geqslant 1$ учитывая достаточно времени и памяти. Простого использования, например, 32-битных типов для представления целых чисел недостаточно.
Вам не обязательно нужно вывести наименьшее возможное . $N$

Примеры

A            N
1            1
2            2
3            9
4            8
5            7
6            3
7            6
9           96
12           5
16          89
17          69
18          76
19          63
24           4
72           6
841      12745
206591378  314

Наименьшее возможное для каждого можно найти по адресу https://oeis.org/A076219. $N$ $A$

code-golf math number integer factorial flawr
источник

26

Я ... почему он доказал эту теорему? Он проснулся однажды и сказал: «Я решу это!» или это послужило цели?

Волшебная Урна Осьминога

11

@MagicOctopusUrn Никогда раньше не занимался теорией чисел?

Брейди Гилг

2

Вот доказательство того, что кому-то интересно.

Esolanging Fruit

14

Python 2 , 50 байт

f=lambda a,n=2,p=1:(`p`.find(a)and f(a,n+1,p*n))+1

Попробуйте онлайн!

Это вариация 47-байтового решения, описанного ниже, с поправкой на возврат 1для ввода '1'. (А именно, мы добавляем 1к полному выражению, а не к рекурсивному вызову, и начинаем считать, n==2чтобы удалить один слой глубины, балансируя результат для всех не '1'входных данных.)

Python 2 , 45 байт (карты 1 в `True`)

f=lambda a,n=2,p=1:`-a`in`-p`or-~f(a,n+1,p*n)

Это еще один вариант, @Jo King и @xnor, который принимает входные данные как число и возвращает их Trueдля ввода 1. Некоторые люди думают это честная игра, но я лично нахожу ее немного странной.

Но для обтекания результата icky Boolean требуется всего 3 байта +(), что дает нам более короткое «хорошее» решение:

Python 2 , 48 байт

f=lambda a,n=2,p=1:+(`-a`in`-p`)or-~f(a,n+1,p*n)

Это мое предыдущее решение, которое возвращает 0для ввода '1'. Это было бы справедливо, если бы вопрос касался неотрицательногоN .

Python 2 , 47 байт (неверно)
f=lambda a,n=1,p=1:`p`.find(a)and-~f(a,n+1,p*n)
Попробуйте онлайн!

Принимает строку в качестве ввода, например f('18') .

Хитрость в том, что x.find(y) == 0именно когдаx.startswith(y) .

and-Expression будет короткое замыкание на `p`.find(a)с результатом , 0как только `p`начинается с a; в противном случае он будет оцениваться -~f(a,n+1,p*n), то есть1 + f(a,n+1,p*n) .

Конечный результат 1 + (1 + (1 + (... + 0))), nслои глубокие, так n.

Линн
источник

Хорошее решение, кстати. Я работал над тем же методом, но вычислял факториал на каждой итерации; В +1любом случае реализация вашего подхода позволила мне сэкономить несколько байт .

Лохматый

1

Для вашей версии True-for-1 вы можете сократить условие базового случая, приняв aчисло.

xnor

@xnor Я бы не подумал о `` -aв -p``, это хитрый трюк :)

Линн

Если доказательство все еще верно, если N ограничено четными значениями, то это 45-байтовое решение всегда будет выводить число.

минус семь

9

Брахилог , 3 5 байт

ℕ₁ḟa₀

Попробуйте онлайн!

Принимает ввод через свою выходную переменную и выводит через свою входную переменную. (С другой стороны, он просто находит произвольные префиксы факториала входных данных, что не так интересно.) Время ожидания второго контрольного примера на TIO, но хорошо на последнем . На момент написания этой статьи я запускал его на 841 на своем ноутбуке в течение нескольких минут, и он пока не выдал ответ, но я в это верю.

         The (implicit) output variable
   a₀    is a prefix of
  ḟ      the factorial of
         the (implicit) input variable
ℕ₁       which is a positive integer.

Поскольку единственный вход ḟa₀не работает для 1, а 1 является положительным префиксом 1! = 1,1|ḟa₀ работает так же хорошо.

Кроме того, на момент этого редактирования 841 работал почти три часа и до сих пор не дал результатов. Я предполагаю, что вычисление факториала каждого целого числа от 1 до 12745 не совсем быстрое.

Несвязанная строка
источник

2

Реализация факториального предиката в Brachylog немного запутана, так что его можно использовать в обоих направлениях с приемлемой эффективностью. Можно было бы реализовать гораздо более быстрый алгоритм для вычисления факториала, но он был бы крайне медленным, если выполнял бы другой путь (т.е. находил исходное число из факториала).

Fatalize

О, круто! Глядя на источник для этого, я не могу сказать, что все это делает, но я могу сказать, что вы вложили много хорошего в это.

Несвязанная строка

7

C ++ (gcc) , 107 95 байт, используя`-lgmp` и`-lgmpxx`

Спасибо людям в комментариях за указание на некоторые глупые ошибки.

#import<gmpxx.h>
auto f(auto A){mpz_class n,x=1,z;for(;z!=A;)for(z=x*=++n;z>A;z/=10);return n;}

Попробуйте онлайн!

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

Нил А.
источник

Вам больше не нужно считать флаги, так что это 107байты.

AdmBorkBork

Зачем вам вторая точка с запятой раньше return?

Руслан

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

лохматый

6

Желе , 8 байт

1!w⁼1ʋ1#

Попробуйте онлайн!

Принимает целое число и возвращает синглтон.

Эрик Outgolfer
источник

6

05AB1E , 7 байтов

∞.Δ!IÅ?

Попробуйте онлайн или проверьте почти все тестовые случаи ( 841время ожидания исключено).

Объяснение:

∞.Δ      # Find the first positive integer which is truthy for:
   !     #  Get the factorial of the current integer
    IÅ?  #  And check if it starts with the input
         # (after which the result is output implicitly)

Кевин Круйссен
источник

2

Pyth - 8 байт

f!x`.!Tz

f              filter. With no second arg, it searches 1.. for first truthy
 !             logical not, here it checks for zero
  x    z       indexof. z is input as string
   `           string repr
    .!T        Factorial of lambda var

Попробуйте онлайн .

Maltysen
источник

2

JavaScript, 47 43 байта

Вывод как BigInt.

n=>(g=x=>`${x}`.search(n)?g(x*++i):i)(i=1n)

Попробуйте онлайн!

Сохраните несколько байтов, приняв подход Линн «строить» факториал, а не вычислять его на каждой итерации, поэтому, пожалуйста, также проголосуйте за ее решение, если вы голосуете против этого.

мохнатый
источник

К сожалению, _Ês bU}f1в Japt не работает

Воплощение неведения

@EmbodimentofIgnorance, да, у меня это тоже было. Вы можете удалить пространство после s.

Лохматый

@EmbodimentofIgnorance, вы также можете удалить 1if 0для n=1.

Лохматый

На 3 байта меньше:x=i=1n;f=n=>`${x*=++i}`.search(n)?f(n):i

vrugtehagel

@ Vrugtehagel, это не будет многоразовым.

Лохматый

2

C # (.NET Core) , 69 + 22 = 91 байт

a=>{var n=a/a;for(var b=n;!(b+"").StartsWith(a+"");b*=++n);return n;}

Попробуйте онлайн!

Использует System.Numerics.BigIntegerкоторый требует usingутверждения.

-1 байт благодаря @ExpiredData!

Dana
источник

1

69 + 22

Просроченные данные

1

Желе , 16 байт

‘ɼ!³;D®ß⁼Lḣ@¥¥/?

Попробуйте онлайн!

объяснение

‘ɼ                | Increment the register (initially 0)
  !               | Factorial
   ³;             | Prepend the input
     D            | Convert to decimal digits
        ⁼   ¥¥/?  | If the input diguts are equal to...
         Lḣ@      | The same number of diguts from the head of the factorial
      ®           | Return the register
       ß          | Otherwise run the link again

Ник Кеннеди
источник

1

Perl 6 , 23 байта

{+([\*](1..*).../^$_/)}

Попробуйте онлайн!

объяснение

{                     }  # Anonymous code block
   [\*](1..*)            # From the infinite list of factorials
             ...         # Take up to the first element
                /^$_/    # That starts with the input
 +(                  )   # And return the length of the sequence

Джо Кинг
источник

1

Древесный уголь , 16 байт

⊞υ¹Ｗ⌕ＩΠυθ⊞υＬυＩ⊟υ

Попробуйте онлайн! Ссылка на подробную версию кода. Объяснение:

⊞υ¹

Нажмите 1на пустой список, чтобы он начинался с определенного продукта.

Ｗ⌕ＩΠυθ

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

⊞υＬυ

... подтолкнуть длину списка к себе.

Ｉ⊟υ

Выведите последнее значение, помещенное в список.

Нил
источник

1

Perl 5 `-Mbigint -p` , 25 байт

1while($.*=++$\)!~/^$_/}{

Попробуйте онлайн!

Xcali
источник

1

J , ²⁸ 22 байта

-6 байт благодаря FrownyFrog

(]+1-0{(E.&":!))^:_&1x

Попробуйте онлайн!

оригинальный ответ J , 28 байт

>:@]^:(-.@{.@E.&":!)^:_ x:@1

Попробуйте онлайн!

>:@] ... x:@1 начиная с повышенной точности 1 , продолжайте увеличивать его, пока ...
-.@ дело не в том, что ...
{.@ первый вяз - стартовый матч ...
E.&":все подстроки совпадают (после строкового определения обоих аргументов &":) поиска исходного ввода в ...
! факториал числа, которое мы увеличиваем

Ион
источник

(]+1-0{(E.&":!))^:_&1x

FrownyFrog

Мне нравится это использование «фиксированной точки», чтобы избежать традиционного времени.

Иона

1

C (gcc) -lgmp, 161 байт

#include"gmp.h"
f(a,n,_,b)char*a,*b;mpz_t n,_;{for(mpz_init_set_si(n,1),mpz_init_set(_,n);b=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n));}

Попробуйте онлайн!

LambdaBeta
источник

Предлагаю strstr(b=mpz_get_str(0,10,_),a)-b;mpz_mul(_,_,n))mpz_add_ui(n,n,1)вместоb=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n))

floorcat

1

Python 3 , 63 байта

f=lambda x,a=2,b=1:str(b).find(str(x))==0and a-1or f(x,a+1,b*a)

Попробуйте онлайн!

-24 байта благодаря Джо Кингу

-3 байта благодаря Часу Брауну

HyperNeutrino
источник

@ Отлично, спасибо

HyperNeutrino

61 байт

Час Браун

@ChasBrown спасибо

HyperNeutrino

Я думаю, f=что то, что у вас есть в заголовке, должно засчитываться в счет ваших битов.

mypetlion

@mypetlion Вы правы; спасибо, что поймали это.

HyperNeutrino

0

Желе , 11 байт

‘ɼµ®!Dw³’µ¿

Попробуйте онлайн!

HyperNeutrino
источник

0

Чисто , 88 байт

import StdEnv,Data.Integer,Text
$a=hd[n\\n<-[a/a..]|startsWith(""<+a)(""<+prod[one..n])]

Попробуйте онлайн!

Определяет $ :: Integer -> Integer.

Использует Data.Integerпроизвольные целые числа размера для ввода-вывода.

Οurous
источник

0

Wolfram Language (Mathematica) , 62 байта

(b=1;While[⌊b!/10^((i=IntegerLength)[b!]-i@#)⌋!=#,b++];b)&

Попробуйте онлайн!

J42161217
источник

0

Рубин , 40 байт

->n{a=b=1;a*=b+=1until"%d"%a=~/^#{n}/;b}

Попробуйте онлайн!

гигабайт
источник

0

Icon , 65 63 байта

procedure f(a);p:=1;every n:=seq()&1=find(a,p*:=n)&return n;end

Попробуйте онлайн!

Гален Иванов
источник

0

Haskell, 89 байт

import Data.List
a x=head$filter(isPrefixOf$show x)$((show.product.(\x->[1..x]))<$>[1..])

Если кто-нибудь знает, как обойти требуемый импорт, дайте мне знать.

Мега человек
источник

Кажется, вы выводите

N!

$N!$ и нет

N

$N$ как требуется.

flawr

Примечание о N!

Вызов

Детали

Примеры

Ответы:

Python 2 , 50 байт

Python 2 , 45 байт (карты 1 в `True`)

Python 2 , 48 байт

Python 2 , 47 байт (неверно)

Брахилог , 3 5 байт

C ++ (gcc) , 107 95 байт, используя`-lgmp` и`-lgmpxx`

Желе , 8 байт

05AB1E , 7 байтов

Pyth - 8 байт

JavaScript, 47 43 байта

C # (.NET Core) , 69 + 22 = 91 байт

Желе , 16 байт

объяснение

Perl 6 , 23 байта

объяснение

Древесный уголь , 16 байт

Perl 5 `-Mbigint -p` , 25 байт

J , ²⁸ 22 байта

оригинальный ответ J , 28 байт

C (gcc) -lgmp, 161 байт

Python 3 , 63 байта

Желе , 11 байт

Чисто , 88 байт

Wolfram Language (Mathematica) , 62 байта

Рубин , 40 байт

Icon , 65 63 байта

Haskell, 89 байт

Примечание о N!

Вызов

Детали

Примеры

Ответы:

Python 2 , 50 байт

Python 2 , 45 байт (карты 1 в True)

Python 2 , 48 байт

Python 2 , 47 байт (неверно)

Брахилог , 3 5 байт

C ++ (gcc) , 107 95 байт, используя-lgmp и-lgmpxx

Желе , 8 байт

05AB1E , 7 байтов

Pyth - 8 байт

JavaScript, 47 43 байта

C # (.NET Core) , 69 + 22 = 91 байт

Желе , 16 байт

объяснение

Perl 6 , 23 байта

объяснение

Древесный уголь , 16 байт

Perl 5 -Mbigint -p , 25 байт

J , 28 22 байта

оригинальный ответ J , 28 байт

C (gcc) -lgmp, 161 байт

Python 3 , 63 байта

Желе , 11 байт

Чисто , 88 байт

Wolfram Language (Mathematica) , 62 байта

Рубин , 40 байт

Icon , 65 63 байта

Haskell, 89 байт

Python 2 , 45 байт (карты 1 в `True`)

C ++ (gcc) , 107 95 байт, используя`-lgmp` и`-lgmpxx`

Perl 5 `-Mbigint -p` , 25 байт

J , ²⁸ 22 байта