Uwaga na temat N!

32

JE Maxfield udowodnił następujące twierdzenie (patrz DOI: 10.2307 / 2688966 ):

Jeśli A jest dowolną liczbą całkowitą dodatnią cyfr, istnieje dodatnia liczba całkowita taka, że ​​pierwsze cyfrstanowią całkowitą .mNmN!A

Wyzwanie

Twoje wyzwanie otrzymuje trochę znajdującą odpowiedni .A1N1

Detale

  • N!reprezentuje silnię o .N!=123NN
  • Cyfry w naszym przypadku są rozumiane jako podstawa .A10
  • Twoje zgłoszenie powinno działać dla dowolnego biorąc pod uwagę wystarczającą ilość czasu i pamięci. Samo użycie np. Typów 32-bitowych do przedstawienia liczb całkowitych nie jest wystarczające.ZA1
  • Nie koniecznie trzeba wyjściu z najmniejszą możliwą N. .

Przykłady

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

Najmniejszą możliwą N. dla każdego ZA można znaleźć na https://oeis.org/A076219

wada
źródło
26
Ja ... dlaczego udowodnił to twierdzenie? Czy on właśnie się obudził i powiedział: „Rozwiążę to!”. czy to miało jakiś cel?
Magic Octopus Urn
11
@MagicOctopusUrn Nigdy nie zajmowałeś się teoretykiem liczb, prawda?
Brady Gilg
2
Oto dowód, że każdy jest zainteresowany.
Esolanging Fruit

Odpowiedzi:

14

Python 2 , 50 bajtów

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

Wypróbuj online!

Jest to odmiana 47-bajtowego rozwiązania wyjaśnionego poniżej, dostosowanego do zwrotu 1danych wejściowych '1'. (Mianowicie, dodajemy 1do pełnego wyrażenia, a nie do wywołania rekurencyjnego, i zaczynamy odliczać, n==2aby usunąć jedną warstwę głębokości, równoważąc wynik dla wszystkich '1'danych innych niż wejściowe.)

Python 2 , 45 bajtów (mapy od 1 do True)

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

To kolejna odmiana autorstwa: @Jo King i @xnor, która przyjmuje dane wejściowe jako liczbę i zwraca Truedane wejściowe 1. Niektórzy uważają, że to uczciwa gra, ale osobiście uważam, że to trochę dziwne.

Ale zawinięcie chropowatego wyniku logicznego kosztuje tylko 3 bajty +(), co daje nam krótsze „fajne” rozwiązanie:

Python 2 , 48 bajtów

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

To jest moje poprzednie rozwiązanie, które wraca 0do danych wejściowych '1'. Byłoby ważne, gdyby pytanie dotyczyło odpowiedzi nieujemnejN .

Python 2 , 47 bajtów (niepoprawny)

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

Wypróbuj online!

Pobiera ciąg jako dane wejściowe, takie jak f('18').

Sztuczka polega na tym x.find(y) == 0, że właśnie wtedy x.startswith(y).

Wyrażenie andspowoduje zwarcie `p`.find(a)z wynikiem, 0gdy tylko `p`zacznie się na a; w przeciwnym razie oceni to -~f(a,n+1,p*n), id est 1 + f(a,n+1,p*n).

Efektem końcowym jest 1 + (1 + (1 + (... + 0))), ngłębokie warstwy, więc n.

Lynn
źródło
Nawiasem mówiąc, fajne rozwiązanie. Pracowałem nad tą samą metodą, ale obliczałem silnię dla każdej iteracji; wdrożenie twojego podejścia pozwoliło mi zaoszczędzić kilka bajtów +1.
Kudłaty
1
W przypadku wersji True-for-1 możesz skrócić podstawowy warunek, przyjmując aliczbę.
xnor
@xnor Nie pomyślałbym o `` -aw -p'', to fajna sztuczka :)
Lynn
Jeśli dowód nadal obowiązuje, jeśli N jest ograniczone do parzystych wartości, to 45-bajtowe rozwiązanie zawsze wyświetli liczbę.
negatywne siedem
9

Brachylog , 3 5 bajtów

ℕ₁ḟa₀

Wypróbuj online!

Pobiera dane wejściowe przez zmienną wyjściową i dane wyjściowe przez zmienną wejściową. (Odwrotnie, po prostu znajduje arbitralne prefiksy silni wejściowej, co nie jest aż tak interesujące.) Przekracza czas od ostatniego do ostatniego przypadku testowego na TIO, ale radzi sobie dobrze na ostatnim . W chwili pisania tego uruchomiłem go na 841 na moim laptopie i tak naprawdę jeszcze nie wydzieliłem odpowiedzi, ale wierzę w to.

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

Ponieważ jedyne wejście ḟa₀nie działa dla 1, a 1 jest dodatnim prefiksem 1! = 1, 1|ḟa₀działa równie dobrze.

Ponadto od tej edycji 841 działało przez prawie trzy godziny i nadal nie wygenerowało danych wyjściowych. Chyba obliczenie silni każdej liczby całkowitej od 1 do 12745 nie jest dokładnie szybkie.

Niepowiązany ciąg
źródło
2
Implementacja predykatu czynnikowego w Brachylog jest nieco skomplikowana, dzięki czemu można go używać na dwa sposoby z akceptowalną wydajnością. Można by zaimplementować znacznie szybszy algorytm do obliczania silni, ale byłoby bardzo wolno działać w drugą stronę (tj. Znaleźć pierwotną liczbę z silni).
Fatalize
Fajnie! Patrząc na źródło, nie mogę powiedzieć, co on robi, ale mogę powiedzieć, że dobrze się nad tym zastanowiliście.
Niepowiązany ciąg
7

C ++ (gcc) , 107 95 bajtów, przy użyciu -lgmpi-lgmpxx

Dzięki ludziom w komentarzach za wskazanie głupich wpadek.

#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;}

Wypróbuj online!

Oblicza n!przez pomnożenie (n-1)!przezn , a następnie kilkakrotnie dzieli go przez10 aż nie będzie już większy niż przekazana liczba całkowita. W tym momencie pętla kończy się, jeśli silnia jest równa przekazanej liczbie całkowitej lub wprzeciwnym razieprzechodzi do następnegon .

Neil A.
źródło
Nie potrzebujesz już liczyć flag, więc to 107bajty.
AdmBorkBork
Dlaczego wcześniej potrzebujesz drugiego średnika return ?
Ruslan
Możesz użyć nazwy pojedynczego znaku dla funkcji, zaoszczędzić kilka bajtów.
Kudłaty
6

Galaretka , 8 bajtów

1!w⁼1ʋ1#

Wypróbuj online!

Bierze liczbę całkowitą i zwraca singleton.

Erik the Outgolfer
źródło
2

Pyth - 8 bajtów

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

Wypróbuj online .

Maltysen
źródło
2

JavaScript, 47 43 bajtów

Dane wyjściowe jako BigInt.

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

Wypróbuj online!

Zaoszczędziłem kilka bajtów, przyjmując podejście Lynn do „budowania silni”, a nie obliczania jej przy każdej iteracji, więc proszę o głosowanie na jej rozwiązanie, jeśli popierasz to.

Kudłaty
źródło
Niestety _Ês bU}f1w Japt nie działa
of Ignorance
@EmbodimentofIgnorance, tak, ja też to miałem. Możesz usunąć miejsce później s.
Kudłaty
@EmbodimentofIgnorance, możesz również usunąć 1if, jeśli 0można zwrócić n=1.
Kudłaty
3 bajty mniej:x=i=1n;f=n=>`${x*=++i}`.search(n)?f(n):i
vrugtehagel
@vrugtehagel, to nie będzie wielokrotnego użytku.
Kudłaty
2

C # (.NET Core) , 69 + 22 = 91 bajtów

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

Wypróbuj online!

Zastosowania, System.Numerics.BigIntegerktóre wymagająusing oświadczenia.

-1 bajt dzięki @ExpiredData!

dana
źródło
1
69 + 22
Data wygasła
1

Galaretka , 16 bajtów

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

Wypróbuj online!

Wyjaśnienie

‘ɼ                | 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
Nick Kennedy
źródło
1

Perl 6 , 23 bajtów

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

Wypróbuj online!

Wyjaśnienie

{                     }  # 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
Jo King
źródło
1

Węgiel drzewny , 16 bajtów

⊞υ¹W⌕IΠυθ⊞υLυI⊟υ

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

⊞υ¹

Naciśnij 1pustą listę, aby rozpocząć od zdefiniowanego produktu.

W⌕IΠυθ

Powtarzaj, dopóki danych wejściowych nie można znaleźć na początku produktu z listy ...

⊞υLυ

... przesuń do siebie długość listy.

I⊟υ

Wydrukuj ostatnią wartość wypchniętą na listę.

Neil
źródło
1

J , 28 22 bajtów

-6 bajtów dzięki FrownyFrog

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

Wypróbuj online!

oryginalna odpowiedź J , 28 bajtów

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

Wypróbuj online!

  • >:@] ... x:@1zaczynając od rozszerzonej precyzji 1, zwiększaj ją, jednocześnie ...
  • -.@ nie jest tak, że ...
  • {.@ pierwszy wiąz to mecz początkowy ...
  • E.&":wszystkie podłańcuchy pasują (po łańcuchowaniu obu argumentów &":) wyszukiwania oryginalnego wejścia w ...
  • ! silnia liczby, którą zwiększamy
Jonasz
źródło
(]+1-0{(E.&":!))^:_&1x
FrownyFrog
Uwielbiam to użycie „stałego punktu”, aby uniknąć tradycyjnego czasu.
Jonasz
1

C (gcc) -lgmp, 161 bajtów

#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));}

Wypróbuj online!

LambdaBeta
źródło
Zaproponuj strstr(b=mpz_get_str(0,10,_),a)-b;mpz_mul(_,_,n))mpz_add_ui(n,n,1)zamiastb=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n))
ceilingcat
1

Python 3 , 63 bajty

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

Wypróbuj online!

-24 bajty dzięki Jo King

-3 bajty dzięki Chasowi Brownowi

HyperNeutrino
źródło
@JoKing miło, dziękuję
HyperNeutrino
61 bajtów
Chas Brown
@ChasBrown dzięki
HyperNeutrino
Myślę, f=że to, co masz w nagłówku, ma się liczyć do liczby bitów.
mypetlion
@mypetlion Masz rację; dzięki za złapanie tego.
HyperNeutrino
0

Czysty , 88 bajtów

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

Wypróbuj online!

Definiuje $ :: Integer -> Integer.

Używa Data.Integerliczb całkowitych o dowolnym rozmiarze dla operacji wejścia / wyjścia.

Obrzydliwe
źródło
0

Ikona , 65 63 bajtów

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

Wypróbuj online!

Galen Iwanow
źródło
0

Haskell, 89 bajtów

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

Jeśli ktoś wie, jak ominąć wymagany import, daj mi znać.

Mega człowiek
źródło
Wygląda na to, że wyprowadzasz a nie N zgodnie z wymaganiami.N.!N.
flawr