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 1
tiene 1
un dígito distinto.
La mayoría de los enteros positivos en la base 2
tienen 2
dí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 1
un dígito único es 1
y el primero que se puede representar con 2
dígitos distintos es 2
.
Podemos decir que 1
es el primer número entero con diversidad digital 1
y 2
es el primer número entero con diversidad digital 2
.
Desafío:
Dado un entero positivo, n
devuelve 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 código de golf , 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.
fuente
Python, 40 bytes
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.
fuente
Python 2,
5446 bytesEste es un muy muy muy ! Solución rápida e iterativa.
Pruébalo en línea
No hay recursividad, por lo que funciona para entradas grandes. Aquí está el resultado de
n = 17000
(toma 1-2 segundos):http://pastebin.com/UZjgvUSW
fuente
lambda n:n**~-n+sum(i*n**(n+~i)for i in range(2,n))
n=r=input();k=2\nwhile k<n:r=r*n+k;k+=1\nprint r
JavaScript (ES6), 29 bytes
fuente
J, 9 bytes
Basado en el método de @Dennis .
Uso
Explicación
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 bytesfuente
[1,0,2,3,...,n-1]
?Ruby,
373534 bytesLa respuesta para un dado
n
toma la forma10234...(n-1)
en basen
. Usandon=10
como ejemplo:Comience con
n
:10
Multiplica por
n
y suma 2:102
Mutliply by
n
y suma 3:1023
Y así.
EDITAR: parece más corto para usar el mapa.
EDIT 2: Gracias por el consejo, m-chrzan!
fuente
(2...n)
Será un byte más corto.CJam , 9 bytes
Pruébalo en línea!
Explicación
fuente
CJam (9 bytes)
Demostración en línea
Disección
Obviamente, el número más pequeño con diversidad digital
n
se encuentra mediante la conversión[1 0 2 3 ... n-1]
de base en basen
. Sin embargo, tenga en cuenta que la conversión de base incorporada no requiere que los dígitos estén en el rango0 .. n-1
.Tenga en cuenta que en el caso especial
n = 1
obtenemos1 [0] 1 1 tb
dando1 [0 1] b
que es1
.fuente
Haskell, 31 bytes
Convierte la lista
[n,2,3,...,n-1]
a basen
utilizando 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!
fuente
f
?) Para ser una solución de golf válida? (simplementef
no se menciona más adelante en el código)\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 an
.foldl
y comenzar conn
:f n=foldl((+).(*n))n[2..n-1]
05AB1E , 9 bytes
Pruébalo en línea!
Explicación
n = 4
utilizado por ejemplo.fuente
C ++ -
18155Estaba a punto de publicar esa solución realmente genial usando
<numeric>
:y luego me di cuenta de que es mucho más fácil:
fuente
Perl 6 ,
34 3130 bytesTraducido del ejemplo de Haskell en la página OEIS .
[&(…)]
se convierte…
en un operador infijo in situ[…]
muestra arriba convierte un op infix en un pliegue (izquierda o derecha dependiendo de la asociatividad del operador)Expandido:
Uso:
fuente
Brain-Flak ,
8476 bytesGracias a Wheat Wizard por jugar 8 bytes.
Pruébalo en línea!
Explicación
El programa empuja los valores de
0
an-1
la pila reemplaza la parte superior0
y1
con1
y0
. 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
n
que contienen
diferentes dígitos (paran
> 1 siempre es de la forma1023...(n-1)
). Luego calcula el número dado los dígitos y la base.Código anotado
fuente
{}{}(()(<()>))([][()])
con(<{}{}>)([(())][])
para guardar cuatro bytes(<{}{}>)((()))
para guardar cuatro bytes másJulia, 26 bytes
Pruébalo en línea!
fuente
ShapeScript , 25 bytes
La entrada está en unario, la salida está en decimal. Pruébalo en línea!
fuente
PHP, 78 bytes
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
fuente
k, 12 bytes
Basado en la respuesta de Dennis .
fuente
JavaScript (ES6), 39 bytes
No se usa
=>
fuente