JE Maxfield a démontré le théorème suivant (voir DOI: 10.2307 / 2688966 ):

Si $A$ est un entier positif à $m$ chiffres, il existe un entier positif $N$ tel que les $m$ premiers chiffres de $N!$ constituent l'entier $A$ .

Défi

$A \geqslant 1$ $N \geqslant 1$

Détails

$N!$ représente la factorielle de . $N! = 1\cdot 2 \cdot 3\cdot \ldots \cdot N$ $N$
Les chiffres de dans notre cas sont compris dans la base . $A$ $10$
Votre soumission devrait fonctionner pour arbitraire avec suffisamment de temps et de mémoire. Il ne suffit pas d'utiliser par exemple des types 32 bits pour représenter des nombres entiers. $A\geqslant 1$
Vous n'avez pas nécessairement besoin de produire le moins de possible . $N$

Exemples

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

Le moins possible pour chaque se trouve dans https://oeis.org/A076219 $N$ $A$

code-golf math number integer factorial flawr
la source

26

Je ... pourquoi a-t-il prouvé ce théorème? Est-ce qu'il vient de se réveiller un jour et de dire "je vais résoudre ça!" ou a-t-elle servi un but?

Magic Octopus Urn

11

@MagicOctopusUrn Jamais eu affaire à un théoricien des nombres auparavant, n'est-ce pas?

Brady Gilg

2

Voici la preuve que quiconque est intéressé.

Esolanging Fruit

14

Python 2 , 50 octets

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

Essayez-le en ligne!

Il s'agit d'une variante de la solution de 47 octets expliquée ci-dessous, ajustée pour revenir 1en entrée '1'. (À savoir, nous ajoutons 1à l'expression complète plutôt qu'à l'appel récursif, et commençons à compter à partir de n==2pour supprimer une couche de profondeur, en équilibrant le résultat pour toutes les non- '1'entrées.)

Python 2 , 45 octets (cartes 1 à `True`)

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

Ceci est une autre variation, par @Jo King et @xnor, qui prend l'entrée comme un nombre et retourne Truepour l'entrée 1. Certaines personnes pensent que c'est un jeu équitable, mais personnellement, je le trouve un peu bizarre.

Mais cela ne coûte que 3 octets pour encapsuler le résultat booléen icky +(), ce qui nous donne une solution "sympa" plus courte:

Python 2 , 48 octets

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

Ceci est ma solution précédente, qui retourne 0pour entrée '1'. Elle aurait été valable si la question concernait une question non négativeN .

Python 2 , 47 octets (invalide)
f=lambda a,n=1,p=1:`p`.find(a)and-~f(a,n+1,p*n)
Essayez-le en ligne!

Prend une chaîne en entrée, comme f('18').

L'astuce ici est que x.find(y) == 0précisément quand x.startswith(y).

L' andexpression -court en court-circuit `p`.find(a)avec le résultat 0dès qu'elle `p`commence par a; sinon, il évaluera à -~f(a,n+1,p*n), id est 1 + f(a,n+1,p*n).

Le résultat final est 1 + (1 + (1 + (... + 0))), des ncouches profondes, donc n.

Lynn
la source

Belle solution au fait. Je travaillais sur la même méthode mais en calculant la factorielle à chaque itération; la mise en œuvre de votre approche m'a fait économiser quelques octets de +1toute façon.

Shaggy

1

Pour votre version True-for-1, vous pouvez raccourcir la condition de base en prenant aun nombre.

xnor

@xnor Je n'aurais pas pensé à `` -adans -p'', c'est une bonne astuce :)

Lynn

Si la preuve tient toujours si N est limité aux valeurs paires, alors cette solution de 45 octets affichera toujours un nombre.

négatif sept

9

Brachylog , 3 5 octets

ℕ₁ḟa₀

Essayez-le en ligne!

Prend l'entrée par le biais de sa variable de sortie et sort par le biais de sa variable d'entrée. (Dans l'autre sens, il trouve simplement des préfixes arbitraires de la factorielle de l'entrée, ce qui n'est pas aussi intéressant.) Délai d'attente avant-dernier test sur TIO, mais convient parfaitement au dernier . Je l'ai exécuté sur 841 sur mon ordinateur portable pendant plusieurs minutes au moment de la rédaction de ce document, et il n'a pas encore craché de réponse, mais j'y crois.

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

Puisque la seule entrée ḟa₀ne fonctionne pas pour 1, et 1 est un préfixe positif de 1! = 1, 1|ḟa₀fonctionne aussi bien.

De plus, à la date de cette modification, 841 fonctionne depuis près de trois heures et n'a toujours pas produit de sortie. Je suppose que le calcul de la factorielle de chaque entier de 1 à 12745 n'est pas exactement rapide.

Chaîne non liée
la source

2

La mise en œuvre du prédicat factoriel dans Brachylog est un peu compliquée de sorte qu'il peut être utilisé dans les deux sens avec une efficacité acceptable. On pourrait implémenter un algorithme beaucoup plus rapide pour calculer la factorielle, mais ce serait extrêmement lent dans l'autre sens (c'est-à-dire trouver le nombre d'origine à partir de la factorielle).

Fatalize

Oh cool! En regardant la source, je ne peux pas dire ce que tout cela fait, mais je peux vous dire que vous y avez réfléchi.

Unrelated String

7

C ++ (gcc) , 107 95 octets, en utilisant `-lgmp`et`-lgmpxx`

Merci aux personnes dans les commentaires d'avoir signalé quelques mésaventures idiotes.

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

Essayez-le en ligne!

Calculeen multipliantpar , puis le divise à plusieurs reprises par jusqu'à ce qu'il ne soit plus supérieur à l'entier passé. À ce stade, la boucle se termine si la factorielle est égale à l'entier passé, ou passe au suivant sinon. $n!$ $(n-1)!$ $n$ $10$ $n$

Neil A.
la source

Vous n'avez plus besoin de compter les indicateurs, il s'agit donc d' 107octets.

AdmBorkBork

Pourquoi avez-vous besoin du deuxième point-virgule avant return?

Ruslan

Vous pouvez utiliser un seul nom de caractère pour la fonction, enregistrer quelques octets.

Shaggy

6

Gelée , 8 octets

1!w⁼1ʋ1#

Essayez-le en ligne!

Prend un entier et retourne un singleton.

Erik le golfeur
la source

6

05AB1E , 7 octets

∞.Δ!IÅ?

Essayez-le en ligne ou vérifiez-presque tous les cas de test ( expire841 , donc est exclu).

Explication:

∞.Δ      # 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)

Kevin Cruijssen
la source

2

Pyth - 8 octets

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

Essayez-le en ligne .

Maltysen
la source

2

JavaScript, 47 43 octets

Sortie en tant que BigInt.

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

Essayez-le en ligne!

Vous avez économisé quelques octets en adoptant l'approche de Lynn consistant à "construire" la factorielle plutôt que de la calculer à chaque itération, veuillez également voter pour sa solution si vous votez pour celle-ci.

Hirsute
la source

Malheureusement, _Ês bU}f1dans Japt ne fonctionne pas

Embodiment of Ignorance

@EmbodimentofIgnorance, oui, je l'avais aussi. Vous pouvez supprimer l'espace après s.

Shaggy

@EmbodimentofIgnorance, vous pouvez également supprimer le 1si 0peut être retourné n=1.

Shaggy

3 octets de moins:x=i=1n;f=n=>`${x*=++i}`.search(n)?f(n):i

vrugtehagel

@vrugtehagel, ce ne serait pas réutilisable.

Shaggy

2

C # (.NET Core) , 69 + 22 = 91 octets

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

Essayez-le en ligne!

Utilisations System.Numerics.BigIntegerqui nécessitent une usingdéclaration.

-1 octet grâce à @ExpiredData!

Dana
la source

1

69 + 22

Données expirées le

1

Gelée , 16 octets

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

Essayez-le en ligne!

Explication

‘ɼ                | 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
la source

1

Perl 6 , 23 octets

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

Essayez-le en ligne!

Explication

{                     }  # 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
la source

1

Charbon de bois , 16 octets

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

Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication:

⊞υ¹

Poussez 1vers la liste vide pour qu'elle démarre avec un produit défini.

Ｗ⌕ＩΠυθ

Répétez l'opération si l'entrée est introuvable au début du produit de la liste ...

⊞υＬυ

... repousser la longueur de la liste à elle-même.

Ｉ⊟υ

Imprime la dernière valeur poussée dans la liste.

Neil
la source

1

Perl 5 `-Mbigint -p` , 25 octets

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

Essayez-le en ligne!

Xcali
la source

1

J , ²⁸ 22 octets

-6 octets grâce à FrownyFrog

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

Essayez-le en ligne!

réponse d'origine J , 28 octets

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

Essayez-le en ligne!

>:@] ... x:@1en commençant par une précision étendue 1, continuez à l'incrémenter tout en ...
-.@ ce n'est pas le cas que ...
{.@ le premier orme est un match de départ de ...
E.&":toutes les correspondances de sous-chaîne (après avoir vérifié les deux arguments &":) de la recherche de l'entrée d'origine dans ...
! la factorielle du nombre que nous incrémentons

Jonas
la source

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

FrownyFrog

J'adore cette utilisation de "virgule fixe" pour éviter le traditionnel.

Jonah

1

C (gcc) -lgmp, 161 octets

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

Essayez-le en ligne!

LambdaBeta
la source

Suggérer à la strstr(b=mpz_get_str(0,10,_),a)-b;mpz_mul(_,_,n))mpz_add_ui(n,n,1)place deb=mpz_get_str(0,10,_),strstr(b,a)-b;mpz_add_ui(n,n,1),mpz_mul(_,_,n))

plafondcat

1

Python 3 , 63 octets

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

Essayez-le en ligne!

-24 octets grâce à Jo King

-3 octets grâce à Chas Brown

HyperNeutrino
la source

@JoKing nice, thanks

HyperNeutrino

61 octets

Chas Brown

@ChasBrown thanks

HyperNeutrino

Je pense f=que le que vous avez dans l'en-tête est censé compter pour votre nombre de bits.

mypetlion

@mypetlion Vous avez raison; merci d'avoir attrapé ça.

HyperNeutrino

0

Gelée , 11 octets

‘ɼµ®!Dw³’µ¿

Essayez-le en ligne!

HyperNeutrino
la source

0

Nettoyer , 88 octets

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

Essayez-le en ligne!

Définit $ :: Integer -> Integer.

Utilise Data.Integerles entiers de taille arbitraire pour IO.

Οurous
la source

0

Wolfram Language (Mathematica) , 62 octets

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

Essayez-le en ligne!

J42161217
la source

0

Rubis , 40 octets

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

Essayez-le en ligne!

GB
la source

0

Icône , 65 63 octets

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

Essayez-le en ligne!

Galen Ivanov
la source

0

Haskell, 89 octets

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

Si quelqu'un sait comment contourner l'importation requise, faites-le moi savoir.

Mega Man
la source

N!

$N!$

N

$N$

Une note sur N!

Défi

Détails

Exemples

Réponses:

Python 2 , 50 octets

Python 2 , 45 octets (cartes 1 à `True`)

Python 2 , 48 octets

Python 2 , 47 octets (invalide)

Brachylog , 3 5 octets

C ++ (gcc) , 107 95 octets, en utilisant `-lgmp`et`-lgmpxx`

Gelée , 8 octets

05AB1E , 7 octets

Pyth - 8 octets

JavaScript, 47 43 octets

C # (.NET Core) , 69 + 22 = 91 octets

Gelée , 16 octets

Explication

Perl 6 , 23 octets

Explication

Charbon de bois , 16 octets

Perl 5 `-Mbigint -p` , 25 octets

J , ²⁸ 22 octets

réponse d'origine J , 28 octets

C (gcc) -lgmp, 161 octets

Python 3 , 63 octets

Gelée , 11 octets

Nettoyer , 88 octets

Wolfram Language (Mathematica) , 62 octets

Rubis , 40 octets

Icône , 65 63 octets

Haskell, 89 octets

Une note sur N!

Défi

Détails

Exemples

Réponses:

Python 2 , 50 octets

Python 2 , 45 octets (cartes 1 à True)

Python 2 , 48 octets

Python 2 , 47 octets (invalide)

Brachylog , 3 5 octets

C ++ (gcc) , 107 95 octets, en utilisant -lgmpet-lgmpxx

Gelée , 8 octets

05AB1E , 7 octets

Pyth - 8 octets

JavaScript, 47 43 octets

C # (.NET Core) , 69 + 22 = 91 octets

Gelée , 16 octets

Explication

Perl 6 , 23 octets

Explication

Charbon de bois , 16 octets

Perl 5 -Mbigint -p , 25 octets

J , 28 22 octets

réponse d'origine J , 28 octets

C (gcc) -lgmp, 161 octets

Python 3 , 63 octets

Gelée , 11 octets

Nettoyer , 88 octets

Wolfram Language (Mathematica) , 62 octets

Rubis , 40 octets

Icône , 65 63 octets

Haskell, 89 octets

Python 2 , 45 octets (cartes 1 à `True`)

C ++ (gcc) , 107 95 octets, en utilisant `-lgmp`et`-lgmpxx`

Perl 5 `-Mbigint -p` , 25 octets

J , ²⁸ 22 octets