16
\$\begingroup\$

A positive integer may be represented in an integer base 1 <= b < inf.

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 , the shortest solution in bytes wins.

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

\$\endgroup\$

18 Answers 18

10
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ I forgot place values could overflow, beats my lousy 7 :) \$\endgroup\$ – Jonathan Allan Oct 14 '16 at 18:16
  • \$\begingroup\$ I wish there was a rep vs bytes used chart per user on codegolf. Maybe a plot of total bytes used vs current rep. \$\endgroup\$ – Filip Haglund Oct 14 '16 at 20:47
  • \$\begingroup\$ Took me a bit to figure out why this works ... slickly done! \$\endgroup\$ – Greg Martin Oct 14 '16 at 23:25
9
\$\begingroup\$

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 = nn-1 + 2nn-3 + … + (n-2)n + (n-1), which f computes recursively.

\$\endgroup\$
6
\$\begingroup\$

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

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

JavaScript (ES6), 29 bytes

f=(b,n=b)=>n>2?f(b,--n)*b+n:b
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Could it be shorter to construct [1,0,2,3,...,n-1]? \$\endgroup\$ – Jonathan Allan Oct 14 '16 at 18:57
  • 1
    \$\begingroup\$ @JonathanAllan I can't find a way, but I did notice that the permutation indices of those would be (n-1)! \$\endgroup\$ – miles Oct 14 '16 at 19:08
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ (2...n) will be a byte shorter. \$\endgroup\$ – m-chrzan Oct 14 '16 at 19:06
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Jonathan Allan Oct 14 '16 at 19:55
  • \$\begingroup\$ @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. \$\endgroup\$ – xnor Oct 14 '16 at 20:01
  • \$\begingroup\$ Cool, thanks for the explanation. Haskell syntax confuses me somewhat. \$\endgroup\$ – Jonathan Allan Oct 14 '16 at 20:04
  • \$\begingroup\$ You can use foldl and start with n: f n=foldl((+).(*n))n[2..n-1] \$\endgroup\$ – nimi Oct 14 '16 at 22:19
3
\$\begingroup\$

05AB1E, 9 bytes

DL¦¨v¹*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
     ¹*     # multiply current stack with input
       y+   # and add y
            # STACK, first pass: 4*4+2 = 18
            # STACK, second pass: 18*4+3 = 75
\$\endgroup\$
2
\$\begingroup\$

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;}
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can replace {}{}(()(<()>))([][()]) with (<{}{}>)([(())][]) to save four bytes \$\endgroup\$ – Sriotchilism O'Zaic Oct 15 '16 at 18:20
  • \$\begingroup\$ You could then replace that with (<{}{}>)((())) to save four more bytes \$\endgroup\$ – Sriotchilism O'Zaic Oct 15 '16 at 18:22
1
\$\begingroup\$

Julia, 26 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

ShapeScript, 25 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

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;
\$\endgroup\$
0
\$\begingroup\$

k, 12 bytes

Based off of Dennis' answer.

{x/x,2+!x-2}
\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 39 bytes

Does not use =>

function f(b,n){throw f(b,n>2?--n:1)*b}
\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Stephen Jun 28 '17 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.