Diversidad digital

16

Un entero positivo puede representarse en una base entera 1 <= b < inf.

Cuando se convierte a esa base, tiene cierto número de dígitos distintos.

Cualquier número entero positivo en la base 1tiene 1un dígito distinto.

La mayoría de los enteros positivos en la base 2tienen 2dígitos distintos, las excepciones son las de la forma 2^n - 1, que solo tienen 1.

Entonces, el primer entero positivo que se puede representar en una base entera con 1un dígito único es 1y el primero que se puede representar con 2dígitos distintos es 2.

Podemos decir que 1es el primer número entero con diversidad digital 1y 2es el primer número entero con diversidad digital 2.

Desafío:

Dado un entero positivo, ndevuelve el primer entero positivo (en base diez *) que tiene una diversidad digital de n.

* si su idioma solo es compatible con una base específica (p. ej., unario o binario), puede imprimir en esa base.

Su algoritmo debe funcionar en teoría para cualquier entrada entera positiva: puede fallar porque la precisión del entero de su idioma es demasiado pequeña para la salida; pero puede no fallar porque la conversión base solo se define hasta cierto límite.

Casos de prueba

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

Este es el , la solución más corta en bytes gana.

OEIS: A049363 - también el número pandigital más pequeño en la base n.

Jonathan Allan
fuente

Respuestas:

11

Jalea , 4 bytes

ṖaWḅ

Pruébalo en línea! o verificar todos los casos de prueba

Cómo funciona

Ṗ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.
Dennis
fuente
Olvidé que los valores de lugar podrían desbordarse, supera a mi pésimo 7 :)
Jonathan Allan
Desearía que hubiera un gráfico de representación vs bytes usados ​​por usuario en codegolf. Tal vez una gráfica del total de bytes utilizados frente al representante actual.
Filip Haglund
Me tomó un poco entender por qué esto funciona ... ¡listo!
Greg Martin
9

Python, 40 bytes

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

Pruébalo en Pruébalo Ideone .

Cómo funciona

Un número con n dígitos distintos debe expresarse claramente en la base b ≥ n . Dado que nuestro objetivo es minimizar el número, b también debe ser lo más pequeño posible, por lo que b = n es la opción lógica.

Eso nos deja con la disposición de los dígitos 0, ..., n-1 para crear un número lo más pequeño posible, lo que significa que los dígitos más significativos deben mantenerse lo más pequeños posible. Como el primer dígito no puede ser un 0 en la representación canónica, el número más pequeño es
(1) (0) (2) ... (n-2) (n-1) n = n n-1 + 2n n-3 +… + (N-2) n + (n-1) , que f calcula de forma recursiva.

Dennis
fuente
6

Python 2, 54 46 bytes

Este es un muy muy muy ! Solución rápida e iterativa.

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

Pruébalo en línea

No hay recursividad, por lo que funciona para entradas grandes. Aquí está el resultado den = 17000 (toma 1-2 segundos):

http://pastebin.com/UZjgvUSW

mbomb007
fuente
¿Cuánto tardó la entrada 17000? Toma 26 segundos en mi máquina, lo que parece lento en comparación con los 0.9 segundos de Jelly ...
Dennis
Similar pero al revés por tres bytes menos:lambda n:n**~-n+sum(i*n**(n+~i)for i in range(2,n))
Jonathan Allan
2
46 bytes y mucho más rápido:n=r=input();k=2\nwhile k<n:r=r*n+k;k+=1\nprint r
Dennis
Sí, es sorprendente cuánto más rápido son los bucles que las comprensiones en Python.
Jonathan Allan
@ JonathanAllan Esa no es la razón. Calcular los poderes es muy lento, mientras que el ciclo solo usa multiplicación y suma.
Dennis
5

JavaScript (ES6), 29 bytes

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

J, 9 bytes

#.],2}.i.

Basado en el método de @Dennis .

Uso

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

Explicación

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

Existe una solución alternativa basada en el uso del índice de permutación. Dada la entrada n , cree la lista de dígitos [0, 1, ..., n]y encuentre la permutación usando un índice de n !, Y conviértala como una lista de dígitos base n . La solución correspondiente en J para 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
millas
fuente
¿Podría ser más corto de construir [1,0,2,3,...,n-1]?
Jonathan Allan
1
@JonathanAllan No puedo encontrar una manera, ¡pero noté que los índices de permutación de esos serían ( n -1)!
millas
4

Ruby, 37 35 34 bytes

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

La respuesta para un dado ntoma la forma 10234...(n-1)en base n. Usando n=10como ejemplo:

Comience con n:10

Multiplica por ny suma 2:102

Mutliply by ny suma 3:1023

Y así.

EDITAR: parece más corto para usar el mapa.

EDIT 2: Gracias por el consejo, m-chrzan!

Lee W
fuente
(2...n)Será un byte más corto.
m-chrzan
3

CJam , 9 bytes

ri__,2>+b

Pruébalo en línea!

Explicación

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.
Martin Ender
fuente
3

CJam (9 bytes)

qi_,X2$tb

Demostración en línea

Disección

Obviamente, el número más pequeño con diversidad digital nse encuentra mediante la conversión [1 0 2 3 ... n-1]de base en base n. Sin embargo, tenga en cuenta que la conversión de base incorporada no requiere que los dígitos estén en el rango 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

Tenga en cuenta que en el caso especial n = 1obtenemos 1 [0] 1 1 tbdando 1 [0 1] bque es 1.

Peter Taylor
fuente
3

Haskell, 31 bytes

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

Convierte la lista [n,2,3,...,n-1]a base nutilizando el método de Horner mediante plegado. Una versión menos golfizada de esto se da en la página OEIS .

Gracias a nimi por 3 bytes!

xnor
fuente
No conozco demasiado bien a Haskell, ¿el pliegue requiere que la función sea nombrada ( f?) Para ser una solución de golf válida? (simplemente fno se menciona más adelante en el código)
Jonathan Allan
@JonathanAllan La forma de la función lambda en Haskell es \n->fold1..., que es tan larga como nombrarla. Puede escribir una función sin puntos donde la variable de entrada no se nombra combinando subfunciones, pero eso sería horrible aquí con tres referencias a n.
xnor
Genial, gracias por la explicación. La sintaxis de Haskell me confunde un poco.
Jonathan Allan
Puede usar foldly comenzar con n:f n=foldl((+).(*n))n[2..n-1]
nimi
3

05AB1E , 9 bytes

DL¦¨v¹*y+

Pruébalo en línea!

Explicación

n = 4 utilizado por ejemplo.

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
Emigna
fuente
2

C ++ - 181 55

Estaba a punto de publicar esa solución realmente genial usando <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;});}

y luego me di cuenta de que es mucho más fácil:

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

Perl 6 ,  34 31  30 bytes

Traducido del ejemplo de Haskell en la página 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 convierte en un operador infijo in situ
  • Lo que se […]muestra arriba convierte un op infix en un pliegue (izquierda o derecha dependiendo de la asociatividad del operador)

Expandido:

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

Uso:

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
Brad Gilbert b2gills
fuente
2

Brain-Flak , 84 76 bytes

Gracias a Wheat Wizard por jugar 8 bytes.

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

Pruébalo en línea!

Explicación

El programa empuja los valores de 0a n-1la pila reemplaza la parte superior 0y 1con 1y 0. Luego, multiplica la parte superior de la pila porn y agrega el valor debajo de ella hasta que solo quede un valor en la pila.

Básicamente, encuentra los dígitos para el número más pequeño en la base nque contiene ndiferentes dígitos (para n> 1 siempre es de la forma 1023...(n-1)). Luego calcula el número dado los dígitos y la base.

Código anotado

(({})<>)       # 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
0 '
fuente
Puede reemplazar {}{}(()(<()>))([][()])con (<{}{}>)([(())][])para guardar cuatro bytes
Post Rock Garf Hunter
Luego, puede reemplazar eso con (<{}{}>)((()))para guardar cuatro bytes más
Post Rock Garf Hunter
1

PHP, 78 bytes

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

Versión en línea

60 Bytes funciona solo hasta n = 16 con la precisión en los casos de prueba

Para n = 144 INF

n = 145 NAN

for(;$j<$a=$argn;)$t+=($j<2?1-$j:$j)*$a**($a-1-$j++);echo$t;
Jörg Hülsermann
fuente
0

JavaScript (ES6), 39 bytes

No se usa =>

function f(b,n){throw f(b,n>2?--n:1)*b}
usuario71511
fuente
Bienvenido a PPCG!
Stephen