# A ​Note ​on ​N!

J. E. Maxfield proved following theorem (see DOI: 10.2307/2688966):

If $$\A\$$ is any positive integer having $$\m\$$ digits, there exists a positive integer $$\N\$$ such that the first $$\m\$$ digits of $$\N!\$$ constitute the integer $$\A\$$.

### Challenge

Your challenge is given some $$\A \geqslant 1\$$ find a corresponding $$\N \geqslant 1\$$.

### Details

• $$\N!\$$ represents the factorial $$\N! = 1\cdot 2 \cdot 3\cdot \ldots \cdot N\$$ of $$\N\$$.
• The digits of $$\A\$$ in our case are understood to be in base $$\10\$$.
• Your submission should work for arbitrary $$\A\geqslant 1\$$ given enough time and memory. Just using e.g. 32-bit types to represent integers is not sufficient.
• You don't necessarily need to output the least possible $$\N\$$.

### Examples

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

The least possible $$\N\$$ for each $$\A\$$ can be found in https://oeis.org/A076219

• I... why did he prove that theorem? Did he just wake up one day and say "I shall solve this!" or did it serve a purpose? – Magic Octopus Urn Apr 25 at 19:53
• @MagicOctopusUrn Never dealt with a number theorist before, have you? – Brady Gilg Apr 26 at 16:16
• Here's the proof it anyone's interested. – Esolanging Fruit Apr 29 at 2:39

# Python 2, 50 bytes

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

Try it online!

This is a variation of the 47-byte solution explained below, adjusted to return 1 for input '1'. (Namely, we add 1 to the full expression rather than the recursive call, and start counting from n==2 to remove one layer of depth, balancing the result out for all non-'1' inputs.)

## Python 2, 45 bytes (maps 1 to True)

f=lambda a,n=2,p=1:-ain-por-~f(a,n+1,p*n)

This is another variation, by @Jo King and @xnor, which takes input as a number and returns True for input 1. Some people think this is fair game, but I personally find it a little weird.

But it costs only 3 bytes to wrap the icky Boolean result in +(), giving us a shorter "nice" solution:

## Python 2, 48 bytes

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

This is my previous solution, which returns 0 for input '1'. It would have been valid if the question concerned a non-negative N.

## Python 2, 47 bytes (invalid)

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

Try it online!

Takes a string as input, like f('18').

The trick here is that x.find(y) == 0 precisely when x.startswith(y).

The and-expression will short circuit at p.find(a) with result 0 as soon as p starts with a; otherwise, it will evaluate to -~f(a,n+1,p*n), id est 1 + f(a,n+1,p*n).

The end result is 1 + (1 + (1 + (... + 0))), n layers deep, so n.

• Nice solution by the way. I was working on the same method but calculating the factorial on each iteration; implementing your approach saved me a few bytes so +1 anyway. – Shaggy Apr 25 at 20:58
• For your True-for-1 version, you can shorten the base case condition taking a as a number. – xnor Apr 27 at 3:40
• @xnor I would have not thought of  -ain-p , that's a neat trick :) – Lynn Apr 27 at 14:20
• If the proof still holds if N is restricted to even values, then this 45 byte solution will always output a number. – negative seven May 27 at 12:25

# Brachylog, 3 5 bytes

ℕ₁ḟa₀

Try it online!

Takes input through its output variable, and outputs through its input variable. (The other way around, it just finds arbitrary prefixes of the input's factorial, which isn't quite as interesting.) Times out on the second-to-last test case on TIO, but does fine on the last one. I've been running it on 841 on my laptop for several minutes at the time of writing this, and it hasn't actually spit out an answer yet, but I have faith in it.

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

Since the only input ḟa₀ doesn't work for is 1, and 1 is a positive prefix of 1! = 1, 1|ḟa₀ works just as well.

Also, as of this edit, 841 has been running for nearly three hours and it still hasn't produced an output. I guess computing the factorial of every integer from 1 to 12745 isn't exactly fast.

• The implementation of the factorial predicate in Brachylog is a bit convoluted so that it can be used both ways with acceptable efficiency. One could implement a much faster algorithm to compute the factorial, but it would be extremely slow running the other way (i.e. finding the original number from the factorial). – Fatalize Apr 26 at 9:28
• Oh, cool! Looking at the source for it, I can't tell what all it's doing, but I can tell you put a lot of good thought into it. – Unrelated String Apr 26 at 9:37

# C++ (gcc), 107 95 bytes, using -lgmp and -lgmpxx

Thanks to the people in the comments for pointing out some silly mishaps.

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

Try it online!

Try it online!

Defines $:: Integer -> Integer. Uses Data.Integer's arbitrary size integers for IO. # Wolfram Language (Mathematica), 62 bytes (b=1;While[⌊b!/10^((i=IntegerLength)[b!]-i@#)⌋!=#,b++];b)& Try it online! # Ruby, 40 bytes ->n{a=b=1;a*=b+=1until"%d"%a=~/^#{n}/;b} Try it online! # Icon, 65 63 bytes procedure f(a);p:=1;every n:=seq()&1=find(a,p*:=n)&return n;end Try it online! # Haskell, 89 bytes import Data.List a x=head$filter(isPrefixOf$show x)$((show.product.(\x->[1..x]))<\$>[1..])

If anyone knows how to bypass the required import, let me know.

• It seems that you output $N!$ and not $N$ as required. – flawr May 3 at 21:49