Digital Diversity

Question

A positive integer may be represented in an integer base \1ドル \le b < \infty\$.

When converted to that base it has some number of distinct digits.

Any positive integer in base \1ドル\$ has \1ドル\$ distinct digit.

Most positive integers in base \2ドル\$ have \2ドル\$ distinct digits, the exceptions being those of the form \2ドル^n - 1\$, which only have \1ドル\$.

So the first positive integer that may be represented in an integer base with \1ドル\$ unique digit is \1ドル\$ and the first that may be represented with \2ドル\$ distinct digits is \2ドル\$.

We can say that \1ドル\$ is the first integer with digital diversity \1ドル\$ and \2ドル\$ is the first integer with digital diversity \2ドル\$.

Challenge:

Given a positive integer \$n\$ return the first positive integer (in base ten*) that has a digital diversity of \$n\$.

* if your language only supports a specific base (e.g. unary or binary) then you may output in that base.

Your algorithm must work in theory for any positive integer input: it may fail because the precision of your language's integer is too small for the output; but may not fail because base conversion is only defined up to some limit.

Test cases

input output
 1 1
 2 2
 3 11
 4 75
 5 694
 6 8345
 7 123717
 17 49030176097150555672
 20 5271200265927977839335179
 35 31553934355853606735562426636407089783813301667210139
 63 3625251781415299613726919161860178255907794200133329465833974783321623703779312895623049180230543882191649073441
 257 87678437238928144977867204156371666030574491195943247606217411725999221158137320290311206746021269051905957869964398955543865645836750532964676103309118517901711628268617642190891105089936701834562621017362909185346834491214407969530898724148629372941508591337423558645926764610261822387781382563338079572769909101879401794746607730261119588219922573912353523976018472514396317057486257150092160745928604277707892487794747938484196105308022626085969393774316283689089561353458798878282422725100360693093282006215082783023264045094700028196975508236300153490495688610733745982183150355962887110565055971546946484175232

This is code-golf, the shortest solution in bytes wins.

OEIS: A049363 - also smallest pandigital number in base n.

Answer 1

Jelly, 4 bytes

ṖaWḅ

Try it online! or verify all test cases

How it works

ṖaWḅ Main link. Argument: n
Ṗ Pop; yield [1, 2, 3, ..., n-1].
 W Wrap; yield [n].
 a Logical AND; yield [n, 2, 3, ..., n-1].
 ḅ Convert the result from base n to integer.

• Jonathan Allan: I forgot place values could overflow, beats my lousy 7 :)
• Drathier: I wish there was a rep vs bytes used chart per user on codegolf. Maybe a plot of total bytes used vs current rep.
• Greg Martin: Took me a bit to figure out why this works ... slickly done!

Answer 2

Python, 40 bytes

f=lambda n,k=1:n*(n<k+2)or-~f(n,k+1)*n-k

Test it on Ideone.

How it works

A number with n distinct digits must clearly be expressed in base b ≥ n. Since our goal is to minimize the number, b should also be as small as possible, so b = n is the logical choice.

That leaves us with arranging the digits 0, ..., n-1 to create a number as small as possible, which means the most significant digits must be kept as small as possible. Since the first digit cannot be a 0 in the canonical representation, the smallest number is
(1)(0)(2)...(n-2)(n-1)_n = n^n-1 + 2n^n-3 + ... + (n-2)n + (n-1), which f computes recursively.

Answer 3

Python 2, (削除) 54 (削除ここまで) 46 bytes

This is a very very very! fast, iterative solution.

n=r=input();k=2
while k<n:r=r*n+k;k+=1
print r

Try it online

There's no recursion, so it works for large input. Here's the result of n = 17000 (takes 1-2 seconds):

http://pastebin.com/UZjgvUSW

• Dennis: How long did input 17000 take? It takes 26 seconds on my machine, which seems slow compared to Jelly's 0.9 seconds...
• Jonathan Allan: Similar but other way around for three bytes less: lambda n:n**~-n+sum(i*n**(n+~i)for i in range(2,n))
• Dennis: 46 bytes and a lot faster: n=r=input();k=2\nwhile k<n:r=r*n+k;k+=1\nprint r
• Jonathan Allan: Yes, it's amazing how much faster while loops are than comprehensions in Python.
• Dennis: @JonathanAllan That's not the reason. Computing the powers is very slow, while the loop only uses multiplication and addition.

Answer 4

JavaScript (ES6), 29 bytes

f=(b,n=b)=>n>2?f(b,--n)*b+n:b

Answer 5

J, 9 bytes

#.],2}.i.

Based on @Dennis' method.

Usage

 f =: #.],2}.i.
 (,.f"0) >: i. 7
1 1
2 2
3 11
4 75
5 694
6 8345
7 123717
 f 17x
49030176097150555672

Explanation

#.],2}.i. Input: n
 i. Get range, [0, 1, ..., n-1]
 2}. Drop the first 2 values, [2, 3, ...., n-1]
 ] Get n
 , Prepend it, [n, 2, 3, ..., n-1]
#. Convert that to decimal from a list of base-n digits and return

There is an alternative solution based on using the permutation index. Given input n, create the list of digits [0, 1, ..., n], and find the permutation using an index of n!, and convert that as a list of base-n digits. The corresponding solution in J for 12 bytes

#.]{.!A.i.,] Input: n
 i. Make range [0, 1, ..., n-1]
 ] Get n
 , Join, makes [0, 1, ..., n-1, n]
 ! Factorial of n
 A. Permutation index using n! into [0, 1, ..., n]
 ] Get n
 {. Take the first n values of that permutation
 (This is to handle the case when n = 1)
#. Convert that to decimal from a list of base-n digits and return

• Jonathan Allan: Could it be shorter to construct [1,0,2,3,...,n-1]?
• miles: @JonathanAllan I can't find a way, but I did notice that the permutation indices of those would be (n-1)!

Answer 6

Ruby, (削除) 37 (削除ここまで) (削除) 35 (削除ここまで) 34 bytes

->n{s=n;(2...n).map{|d|s=s*n+d};s}

The answer for a given n takes the form 10234...(n-1) in base n. Using n=10 as an example:

Start with n: 10

Multiply by n and add 2: 102

Mutliply by n and add 3: 1023

And so on.

EDIT: Shorter to use map, it seems.

EDIT 2: Thanks for the tip, m-chrzan!

• m-chrzan: (2...n) will be a byte shorter.

Answer 7

CJam, 9 bytes

ri__,2>+b

Try it online!

Explanation

ri e# Read input N.
__ e# Make two copies.
, e# Turn last copy into range [0 1 2 ... N-1].
2> e# Discard up to two leading values.
+ e# Prepend a copy of N.
b e# Treat as base-N digits.

Answer 8

CJam (9 bytes)

qi_,X2$tb

Online demo

Dissection

Obviously the smallest number with digital diversity n is found by base-converting [1 0 2 3 ... n-1] in base n. However, note that the base conversion built-in doesn't require the digits to be in the range 0 .. n-1.

qi e# Read integer from stdin
_, e# Duplicate and built array [0 1 ... n-1]
X2$t e# Set value at index 1 to n
b e# Base conversion

Note that in the special case n = 1 we get 1 [0] 1 1 tb giving 1 [0 1] b which is 1.

Answer 9

Haskell, 31 bytes

f n=foldl((+).(*n))n[2..n-1]

Converts the list [n,2,3,...,n-1] to base n using Horner's method via folding. A less golfed version of this is given on the OEIS page.

Thanks to nimi for 3 bytes!

• Jonathan Allan: I don't know Haskell too well, does the fold require the function to be named (f?) to be a valid a golf solution? (it's just f is not referenced later in the code)
• xnor: @JonathanAllan The lambda function form in Haskell is \n->fold1..., which is just as long as naming it. You can write a point-free function where the input variable isn't named by combining sub-functions, but that would be awful here with three references to n.
• Jonathan Allan: Cool, thanks for the explanation. Haskell syntax confuses me somewhat.
• nimi: You can use foldl and start with n: f n=foldl((+).(*n))n[2..n-1]

Answer 10

05AB1E, 9 bytes

DL¦ ̈v1*y+

Try it online!

Explanation

n = 4 used for example.

D # duplicate input
 # STACK: 4, 4
 L # range(1, a)
 # STACK: 4, [1,2,3,4]
 ¦ ̈ # remove first and last element of list
 # STACK: 4, [2,3]
 v # for each y in list
 1* # multiply current stack with input
 y+ # and add y
 # STACK, first pass: 4*4+2 = 18
 # STACK, second pass: 18*4+3 = 75

Answer 11

C++ - (削除) 181 (削除ここまで) 55

Was about to post that real cool solution using <numeric>:

#import <vector>
#import <numeric>
using namespace std;int f(int n){vector<int> v(n+1);iota(v.begin(),v.end(),0);swap(v[0],v[1]);return accumulate(v.begin(),v.end()-1,0,[n](int r,int a){return r*n+a;});}

and then i realized it is way easier:

int g(int n){int r=n,j=2;for(;j<n;)r=r*n+j++;return r;}

Answer 12

Perl 6, (削除) 34 31 (削除ここまで) 30 bytes

Translated from the Haskell example on the OEIS page.

{(1,0,|(2..^$^n)).reduce: $n×ばつ*+*} # 34
{(1,0,|(2..^$^n)).reduce: $n* *+*} # 34
{reduce $^n×ばつ*+*,1,0,|(2..^$n)} # 31
{[[&($^n×ばつ*+*)]] 1,0,|(2..^$n)} # 31
{reduce $_×ばつ*+*,1,0,|(2..^$_)} # 30

• [&(...)] turns ... into an in-place infix operator
• The [...] shown above turns an infix op into a fold (left or right depending on the operator associativity)

Expanded:

{
 reduce
 # declare the blocks only parameter 「$n」 ( the 「^」 twigil )
 # declare a WhateverCode lambda that takes two args 「*」
 $^n ×ばつ * + *
 # a list that always contains at least (1,0)
 1, 0,
 # with a range slipped in
 |(
 2 ..^ $n # range from 2 up-to and excluding 「$n」
 # it is empty if $n <= 2
 )
}

Usage:

my &code = {reduce $_×ばつ*+*,1,0,|(2..^$_)}
say code 1; # 1
say code 2; # 2
say code 3; # 11
say code 4; # 75
say code 7; # 123717
# let's see how long it takes to calculate a largish value:
my $start-time = now;
$_ = code 17000;
my $calc-time = now;
$_ = ~$_; # 25189207981120412047...86380901260421982999
my $display-time = now;
say "It takes only { $calc-time - $start-time } seconds to calculate 17000";
say "but { $display-time - $calc-time } seconds to stringify"
# It takes only 1.06527824 seconds to calculate 17000
# but 5.3929017 seconds to stringify

Answer 13

Brain-Flak, (削除) 84 (削除ここまで) 76 bytes

Thanks to Wheat Wizard for golfing 8 bytes

(({})<>){(({}[()]))}{}(<{}{}>)((())){{}({<({}[()])><>({})<>}{}{})([][()])}{}

Try it online!

Explanation

The program pushes the values from 0 to n-1 to the stack replaces the top 0 and 1 with 1 and 0. Then it multiplies the top of the stack by n and adds the value below it until there is only one value remaining on the stack.

Essentially it finds the digits for the smallest number in base n that contains n different digits (for n > 1 it's always of the form 1023...(n-1)). It then calculates the number given the digits and the base.

Annotated Code

(({})<>) # Pushes a copy of n to the right stack and switches to right stack
{(({}[()]))}{} # While the top of the stack != 0 copy the top of the stack-1
 # and push it
(<{}{}>) # Discard the top two values (0 and 1 for n > 1) and push 0
((())) # Push 1 twice (second time so that the loop is works properly)
{{} # Loop while stack height > 1
 ( # Push...
 {<({}[()])><>({})<>}{} # The top value of the stack * n
 {} # Plus the value below the top of the stack
 ) # End push
([][()])}{} # End loop

• Wheat Wizard: You can replace {}{}(()(<()>))([][()]) with (<{}{}>)([(())][]) to save four bytes
• Wheat Wizard: You could then replace that with (<{}{}>)((())) to save four more bytes

Answer 14

Japt, 8 bytes

o1 hU ìU

Try it

Answer 15

Rockstar, 79 bytes

listen to N
cast N
X's1
let T be N
while N-X-1
let X be+1
let T be T*N+X
say T

Try it here (Code will need to be pasted in)

• Razetime: Mystery Link

Answer 16

Julia, 26 bytes

\(n,k=n)=k<3?n:n\~-k*n+~-k

Try it online!

Answer 17

ShapeScript, 25 bytes

_0?1'1+@2?*1?+@'2?2-*!#@#

Input is in unary, output is in decimal. Try it online!

Answer 18

PHP, 78 Bytes

for(;$i<$a=$argn;)$s=bcadd($s,bcmul($i<2?1-$i:$i,bcpow($a,$a-1-$i++)));echo$s;

Online Version

60 Bytes works only till n=16 with the precision in the testcases

For n=144 INF

n=145 NAN

for(;$j<$a=$argn;)$t+=($j<2?1-$j:$j)*$a**($a-1-$j++);echo$t;

Answer 19

k, 12 bytes

Based off of Dennis' answer.

{x/x,2+!x-2}

Answer 20

JavaScript (ES6), 39 bytes

Does not use =>

function f(b,n){throw f(b,n>2?--n:1)*b}

• Stephen: Welcome to PPCG!

Answer 21

Husk, 7 bytes

B1ṙ_1tḣ

Try it online!