Un entier positif peut être représenté dans une base entière 1 <= b < inf.

Lorsqu'il est converti dans cette base, il a un certain nombre de chiffres distincts.

Tout entier positif dans la base 1a 1un chiffre distinct.

La plupart des entiers positifs dans la base 2ont 2des chiffres distincts, les exceptions étant celles de la forme 2^n - 1, qui ne l'ont que 1.

Ainsi, le premier entier positif qui peut être représenté dans une base entière avec 1un chiffre unique est 1et le premier qui peut être représenté avec 2des chiffres distincts est 2.

On peut dire que 1c'est le premier entier à diversité numérique 1et 2le premier entier à diversité numérique 2.

Défi:

Étant donné un entier positif, nrenvoyez le premier entier positif (en base dix *) qui a une diversité numérique de n.

* si votre langue ne prend en charge qu'une base spécifique (par exemple, unaire ou binaire), vous pouvez sortir dans cette base.

Votre algorithme doit fonctionner en théorie pour toute entrée entière positive: il peut échouer car la précision de l'entier de votre langue est trop petite pour la sortie; mais peut échouer car la conversion de base n'est définie que jusqu'à une certaine limite.

Cas de test

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

C'est le code-golf , la solution la plus courte en octets gagne.

OEIS: A049363 - également le plus petit numéro pandigital dans la base n.

Gelée , 4 octets

ṖaWḅ

Essayez-le en ligne! ou vérifier tous les cas de test

Comment ça fonctionne

Ṗ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.

Python, 40 octets

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

Testez-le sur Ideone .

Comment ça fonctionne

Un nombre à n chiffres distincts doit être clairement exprimé en base b ≥ n . Puisque notre objectif est de minimiser le nombre, b doit également être aussi petit que possible, donc b = n est le choix logique.

Cela nous laisse avec l'organisation des chiffres 0,…, n-1 pour créer un nombre aussi petit que possible, ce qui signifie que les chiffres les plus significatifs doivent être aussi petits que possible. Comme le premier chiffre ne peut pas être un 0 dans la représentation canonique, le plus petit nombre est
(1) (0) (2) ... (n-2) (n-1) _n = n ^n-1 + 2n ^n-3 +… + (N-2) n + (n-1) , que f calcule récursivement.

Python 2, 54 46 octets

C'est un très très très ! solution rapide et itérative.

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

Essayez-le en ligne

Il n'y a pas de récursivité, donc cela fonctionne pour de grandes entrées. Voici le résultat de n = 17000(prend 1-2 secondes):

http://pastebin.com/UZjgvUSW

JavaScript (ES6), 29 octets

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

J, 9 octets

#.],2}.i.

Basé sur la méthode @Dennis .

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

Explication

#.],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

Il existe une solution alternative basée sur l'utilisation de l'indice de permutation. Étant donné l'entrée n , créez la liste des chiffres [0, 1, ..., n]et recherchez la permutation en utilisant un index de n !, Et convertissez-la en une liste de chiffres n de base . La solution correspondante en J pour 12 octets

#.]{.!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

Rubis, 37 35 34 octets

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

La réponse pour une donnée nprend la forme 10234...(n-1)en base n. En utilisant n=10comme exemple:

Commencez par n:10

Multipliez par net ajoutez 2:102

Multiplier par net ajouter 3:1023

Etc.

EDIT: Il est plus court d'utiliser la carte, semble-t-il.

EDIT 2: Merci pour le conseil, m-chrzan!

CJam , 9 octets

ri__,2>+b

Essayez-le en ligne!

Explication

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.

CJam (9 octets)

qi_,X2$tb

Démo en ligne

Dissection

Évidemment, le plus petit nombre avec une diversité numérique nest trouvé par conversion [1 0 2 3 ... n-1]de base en base n. Cependant, notez que la conversion de base intégrée ne nécessite pas que les chiffres soient dans la plage 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

Notez que dans le cas spécial, n = 1nous obtenons 1 [0] 1 1 tbce 1 [0 1] bqui est 1.

Haskell, 31 octets

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

Convertit la liste [n,2,3,...,n-1]en base en nutilisant la méthode de Horner via le pliage. Une version moins golfée de ceci est donnée sur la page OEIS .

Merci à nimi pour 3 octets!

05AB1E , 9 octets

DL¦¨v¹*y+

Essayez-le en ligne!

Explication

n = 4 utilisé par exemple.

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

C ++ - 181 55

Était sur le point de publier cette vraie solution cool en utilisant <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;});}

puis j'ai réalisé que c'était beaucoup plus facile:

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

Perl 6 ,  34 31  30 octets

Traduit de l'exemple Haskell sur la page OEIS .

{(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

• [&(…)]se transforme …en un opérateur infixe sur place
• L' […]illustration ci-dessus transforme un op infixe en un pli (gauche ou droite selon l'associativité de l'opérateur)

Étendu:

{
  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

Brain-Flak , 84 76 octets

Merci à Wheat Wizard pour avoir joué au golf 8 octets

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

Essayez-le en ligne!

Explication

Le programme pousse les valeurs de 0à n-1vers la pile remplace le haut 0et 1avec 1et 0. Ensuite, il multiplie le haut de la pile parn et ajoute la valeur en dessous jusqu'à ce qu'il ne reste qu'une seule valeur sur la pile.

Essentiellement, il trouve les chiffres du plus petit nombre dans la base nqui contient ndifférents chiffres (pour n> 1, il est toujours de la forme 1023...(n-1)). Il calcule ensuite le nombre en fonction des chiffres et de la base.

Code annoté

(({})<>)       # 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

Julia, 26 octets

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

Essayez-le en ligne!

ShapeScript , 25 octets

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

L'entrée est en unaire, la sortie est en décimal. Essayez-le en ligne!

PHP, 78 octets

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

Version en ligne

60 octets ne fonctionne que jusqu'à n = 16 avec la précision des tests

Pour n = 144 INF

n = 145 NAN

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

k, 12 octets

Basé sur la réponse de Dennis .

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

JavaScript (ES6), 39 octets

N'utilise pas =>

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