Desafío
Dado un número entero, n
como entrada donde 36 >= n >= 2
, salida cuántos números Lynch-Bell hay en la base n
.
La salida debe estar en la base 10.
Números de Lynch-Bell
Un número es un número de Lynch-Bell si:
- Todos sus dígitos son únicos (sin repetición de dígitos)
- El número es divisible por cada uno de sus dígitos.
- No contiene cero como uno de sus dígitos
Como todos los dígitos tienen que ser únicos y tiene un conjunto finito de números de un solo dígito en cada base, hay un número finito de números de Lynch-Bell.
Por ejemplo, en la base 2 solo hay un número de Lynch-Bell 1
, ya que todos los demás números repiten dígitos o contienen un 0.
Ejemplos
Input > Output
2 > 1
3 > 2
4 > 6
5 > 10
6 > 10
7 > 75
8 > 144
9 > 487
10 > 548
Mathematica Online se quedó sin memoria por encima de la base 10. Puede usar el siguiente código para generar el suyo propio:
Do[Print[i," > ",Count[Join@@Permutations/@Rest@Subsets@Range[#-1],x_/;And@@(x\[Divides]FromDigits[x,#])]&[i]],{i,10,36,1}]
Victorioso
El código más corto en bytes gana.
code-golf
number
base-conversion
Decaimiento Beta
fuente
fuente
>10
?f(36)
. Hacer un desafío de código más rápido basado en esto sería probablemente interesante.Respuestas:
Jalea , 13 bytes
Pruébalo en línea!
Otra solución O (n n ) .
Explicación
fuente
ṖŒPḊŒ!€Ẏ⁼g¥"ḅ¥³S
y más rápidoJalea , 15 bytes
Pruébalo en línea!
Complejidad .
O(nn)
fuente
O(N^N)
solución no solo aceptable, sino buena.O(N↑↑N)
O(N^(N+1))
porque verifica la validez de cada número generadoO(N)
? (aunque no entiendo Jelly)N+1
está enO(N)
) no implica queN^(N+1)
está enO(N^N)
.Java,
222212190 bytes-10 bytes gracias a Herman
-22 bytes gracias a Kevin
Sin golf:
Pruébalo en línea!
Se vuelve muy lento para grandes números.
fuente
a->{int c=0,i=1;A:for(;i<Math.pow(a,a);i++){java.util.Set<Character>g=new java.util.HashSet<>();for(char b:Long.toString(i,a).toCharArray())if(!g.add(b)|b<49||i%Long.parseLong(b+"",a)>0)continue A;c++;}return c;}
A:
ycontinue A;
son 13 bytes mientras que{--c;break;}
es 12. ¿Introduciría algún error que no veo?i%a
yi/=a
en cada ciclo. Puedes evitar el set usando unint[]
y verificando esox[b]++<2
java.util.Set<Character>g=new java.util.HashSet<>();
puede serimport java.util.*;
+Set g=new HashSet();
;Long.toString
puede sera.toString
; yLong.parseLong
puede sera.parseInt
.Perl 6 ,
868477 bytes-2 bytes gracias a Ramillies
Pruébalo en línea!
Funciona para n = 8 en TIO.
fuente
.all
lugar deall $_
.En realidad , 24 bytes
Pruébalo en línea!
Explicación
Este programa consta de dos partes principales: la generación de permutación y la prueba Lynch-Bell. Entonces, esta explicación analizará cada parte por separado, para mayor claridad.
Generando permutaciones
Entrada:
n
(un entero en[2, 36]
)Salida: todas las permutaciones parciales y totales de
[1, n-1]
(secuencias que contienen valores[1, n-1]
sin repetición cuya longitud está en[1, n-1]
)Prueba de Lynch-Bell
Entrada: una lista de
n
enteros base , representados como listas den
dígitos baseSalida: el número de números de Lynch-Bell en la base
n
fuente
Mathematica,
827976 bytesfuente
[<parameter>]
después. Conparameter
ser un número.05AB1E , 22 bytes
Pruébalo en línea!
O_O
También era mi cara cuando esto finalmente funcionó.<ÝIBJ0Kæ¦Ù€œ˜
es más rápido que la forma en que uso para generar los números en la respuesta real, pero deja de funcionar aleatoriamente para algo mayor que 7 (¿sin razón aparente?)Explicación
fuente
ε0KÙ}
puede ser0м€Ù
guardar un byte.Perl 5,
8076 bytes (75 +-p
)Abusar
$;
por diversión y ganancias. Tiempo de espera en entradas> 8.EDITAR: -4 bytes fusionando los dos bucles.
fuente
Rubí ,
8065 bytesPruébalo en línea!
Gracias a GB por -15 bytes.
fuente
Japt
-x
,2519 bytes-6 bytes gracias a Shaggy
Pruébalo en línea!
fuente
-x
bandera.Python 3 ,
204174 bytesPruébalo en línea!
Para cada permutación de cada elemento del conjunto de potencias de rango (1, n) (sin ceros, único), convierta a cadena numérica a base n. Suma todos los que son divisibles por cada dígito, resta 1 debido a que el conjunto de potencia genera el conjunto vacío.
-30 bytes gracias a @ovs!
fuente
Haskell , 117 bytes
Pruébalo en línea! Funciona en TIO hasta
n=7
antes de que se agote el tiempo de espera.fuente
Perl 5 , 108 + 1 (
-p
) = 109 bytesPruébalo en línea!
Es un cerdo. No estoy seguro de si hará más que la base 8 en TIO sin tiempo de espera.
fuente
C # (compilador interactivo de Visual C #) , 144 bytes
Pasa por todos los números del 0 al
ulong.MaxValue
, y selecciona aquellos que son números de Lynch-Bell en la base especificada. Tarda una eternidad en ejecutarse, incluso para 2, aunque si configura la~0UL
parte del bucle for en algo más pequeño, puede obtener la salida para la entrada de hasta 7 en un minuto en TIO.Pruébalo en línea!
fuente