Divisibilidad de prefijo

Nov 02 2020

Inspiración

Dado un entero positivo \$1 \le n \le 9\$, salida todo positivo \$n\$-dígitos enteros \$i\$ para lo cual se cumple lo siguiente:

  • Cada dígito de \$1\$a \$n\$aparece exactamente una vez en \$i\$. Por tanto, \$i\$Los dígitos son una permutación de los dígitos de \$1\$a \$n\$.
  • \$i\$es divisible por \$n\$
  • Eliminando el dígito más a la derecha de \$i\$produce otro entero \$i_{\text{trunc}(1)}\$que es divisible por \$n-1\$
  • Eliminando el dígito más a la derecha de \$i_{\text{trunc}(1)}\$produce otro entero \$i_{\text{trunc}(2)}\$que es divisible por \$n-2\$
  • Y así sucesivamente, hasta que \$i_{\text{trunc}(n-1)}\$, que es divisible por 1.

Por ejemplo, para \$n = 3\$, uno de esos enteros es \$321\$, como \$321\$es divisible por \$3\$, \$32\$por \$2\$y \$3\$ por 1.

Para \$n = 4, 5, 7\$, no existen tales números enteros. En este caso, es posible que la salida cualquier cosa que no puede ser confundido con una posible salida (por ejemplo 0, [], nada, etc.). Para \$n = 3, 6\$, puede generar los dos números en cualquier formato en el que los dos números estén claramente separados entre sí.

Esto es código de golf, por lo que gana el código más corto en bytes.

Si usa un método de tabla de búsqueda, brownie apunta \${}^\dagger\$ se otorgan si también incluye una versión que calcula la salida correcta.

\${}^\dagger\$Los puntos brownie pueden o no tener la forma de un voto a favor

Casos de prueba

Estos casos son exhaustivos, por lo que nunca recibirá (o tendrá que manejar) una entrada que no esté incluida aquí.

n -> i
1 -> [1]
2 -> [12]
3 -> [123, 321]
4 -> []
5 -> []
6 -> [123654, 321654]
7 -> []
8 -> [38165472]
9 -> [381654729]

Respuestas

5 ovs Nov 02 2020 at 19:28

05AB1E , 8 bytes

LœJʒηāÖP

¡Pruébelo en línea!

Comentó :

L         # push [1..n]
 œ        # push all permutations
  J       # join each permutation into a number
   ʒ      # filter those numbers on:
    η     #   each prefix ...
      Ö   #   ... is divisible ...
     ā    #   ... by its index
       P  #   take the product (all)
5 xnor Nov 02 2020 at 21:12

Python 2 , 68 bytes

lambda n:[`s`[:n]for s in 321654,381654729,123654][380712>>n*2&3::2]

¡Pruébelo en línea!

Genera una lista de cadenas.


71 bytes

lambda n:[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729][n]

¡Pruébelo en línea!

Solo un código duro y aburrido. Emite un solo número, o una lista de dos números, o 0 si no hay salida.

Ninguno de los otros métodos que probé parecía ser más corto que este. Por ejemplo, una idea es generar números como prefijos de un solo número, generando como 123654/10**(6-i).

Un método de objeto da la misma longitud. Desafortunadamente, no podemos usar el mucho más corto .popporque hace que la función no sea reutilizable porque modifica la lista con cada llamada.

[0,1,12,[123,321],0,0,[123654,321654],0,38165472,381654729].__getitem__

¡Pruébelo en línea!

Aliasing la constante más larga también da la misma longitud:

lambda n,c=381654729:[0,1,12,[123,321],0,0,[123654,321654],0,c/10,c][n]

¡Pruébelo en línea!

4 xash Nov 02 2020 at 18:43

J , 42 37 bytes

Calcula los números.

0({:#~0=[:+/#\|])@|:i.@!10&#.\@A.1+i.

¡Pruébelo en línea!

  • 1+i. 1… n
  • i.@!…@A. todas las posibles permutaciones de 1… n
  • 10&#.\ convertir cada prefijo de una permutación en un número
  • 0(…)@|: transponer la matriz y ...
  • #\|] 1… n mod los prefijos, p. Ej. 1 2 3 | 1 12 123
  • 0=[:+/suma el resultado; es 0?
  • {:#~ luego toma el último prefijo de la permutación (la permutación en sí)
3 user Nov 02 2020 at 22:36

Scala, 81 80 bytes

| =>1.to(|).mkString.permutations.filter{i=>1 to|forall(r=>i.take(r).toInt%r<1)}

Pruébalo en Scastie

Explicación:

| =>                          //n, the input
  1.to(|)                     //Range to n
    .mkString                 //Turn it into a string
    .permutations             //Get all permutations
    .filter{ i =>             //Filter them
      1 to | forall(r =>      //For every r from 1 to n
        i.take(r).toInt       //The number made from i's first r digits
          % r < 1             //Should be divisible by r
      )
    }
2 Neil Nov 02 2020 at 19:50

Carbón , 25 bytes

NθΦEXχθIι⬤…·¹θ›№ιIλ﹪I…ιλλ

¡Pruébelo en línea! El enlace corresponde a la versión detallada del código. Demasiado lento para n>5TIO. Explicación:

Nθ

Entrada n.

ΦEXχθIι

Enumere todos los enteros ihasta 10ⁿ, de modo que ...

⬤…·¹θ

... para cada entero lde 1a n...

›№ιIλ﹪I…ιλλ

les un dígito de iy el lprefijo de carácter de ies divisible por l.

Versión un poco más rápida de 28 bytes:

NθΦEX⊕θθ⍘ι⊕θ⬤…·¹θ›№ιIλ﹪I…ιλλ

¡Pruébelo en línea! El enlace corresponde a la versión detallada del código. Explicación: Genera los dígitos en base en n+1lugar de base 10, lo que permite completar n=6en TIO.

La versión más rápida de 29 bytes con una tabla de búsqueda comprimida:

§⪪”)‴a3HSGS⸿Dπ¬Z⦄O<ε≔<πUθ8”0N

¡Pruébelo en línea! El enlace corresponde a la versión detallada del código.

2 J42161217 Nov 02 2020 at 18:38

Wolfram Language (Mathematica) , 78 bytes

(f=FromDigits)/@Select[Permutations@Range[s=#],f@#[[;;k]]~Mod~k~Sum~{k,s}<1&]&

¡Pruébelo en línea!

-8 bytes de @att

2 Razetime Nov 03 2020 at 03:47

Cáscara , 15 bytes

mdföΛIṠz¦ŀmdḣPḣ

¡Pruébelo en línea!

Casi lo mismo que la otra pregunta, excepto con parámetros.

2 Noodle9 Nov 02 2020 at 18:44

C (gcc) -lm, 67 101 96 bytes

Se agregaron 34 bytes para corregir un error amablemente señalado por xnor .
5 bytes guardados gracias a techocat !!!

f(n){write(1,"321654",n-3&&n-6?0:n);n=n<4?123/exp10(3-n):n>7?381654729/exp10(9-n):n-6?0:123654;}

¡Pruébelo en línea!

Solución total basada en búsquedas. Si hay dos soluciones: envía una a stdouty devuelve la otra. Si solo hay una respuesta, simplemente se devuelve. Devoluciones \$0\$ si no hay respuesta.

Ronda de bonificación por puntos de brownie

C (gcc) , 232 212 bytes

¡ ¡ ¡ Ahorré la friolera de 20 bytes gracias a roofcat !!!

p;m;j;char b[9],c[9];d;i;f(n){for(d=0,i=n;i;)d+=9*d+i--;for(sprintf(c,"%d",d);d/++i;)if(sprintf(b,"%d",i),qsort(b,n,1,L"\xf06be0f\xd02917beǃ"),!strcmp(b,c)){for(p=0,m=n,j=i;j;j/=10)p|=j%m--;p||printf("%d ",i);}}

¡Pruébelo en línea!

Calcula los números correctos a través del cálculo y los envía a stdout. No emite nada si no hay respuesta. Se agota el tiempo de espera en TIO para \$n=9\$pero los tiene todos 3m36.499sen mi computadora portátil.

2 JonathanAllan Nov 02 2020 at 18:44

Gelatina ,  11  10 bytes

-1 gracias a caird coinheringaahing !

Este es un método ingenuo, podría haber uno más escueto.

Œ!JḍḌƤẠƲƇḌ

Un enlace monádico que acepta \$n\$que produce 0si no se encuentra ninguno o una lista de números válidos.

¡Pruébelo en línea! O vea la suite de pruebas .

¿Cómo?

Œ!JḍḌƤẠƲƇḌ - Link: n
Œ!         - all permutations of [1..n]
        Ƈ  - filter keep those (p for p in Œ!) for which:
       Ʋ   -   last four links as a monad f(p):
  J        -     range of length = [1..n]
     Ƥ     -     apply to prefixes (of p):
    Ḍ      -       un-decimal
   ḍ       -     divides? (vectorises)
      Ạ    -     all truthy?
         Ḍ - un-decimal
1 KjetilS. Nov 02 2020 at 20:41

Perl 5 , 64 bytes

sub{grep"@_"==y///c,1,12,123,321,123654,321654,$x=38165472,$x.9}

¡Pruébelo en línea!

1 Arnauld Nov 02 2020 at 22:55

JavaScript (V8) , 97 bytes

Una función recursiva que calcula e imprime los enteros coincidentes.

f=(n,s='987654321'.slice(-n),d,p)=>p%d?0:s?[...s].map(v=>f(n,s.replace(v,''),-~d,[p]+v)):print(p)

¡Pruébelo en línea!


JavaScript (ES6), 59 bytes

La codificación rígida es obviamente más corta.

n=>[,1,12,[321,123],,,[321654,123654],,q=38165472,q+[9]][n]

¡Pruébelo en línea!

att Nov 03 2020 at 02:48

Wolfram Language (Mathematica) , 71 bytes

f[s_:0,l_:0]=0!=##2&&l∣s&&If[l<#,##~f[10s+i,l+1]~i~Do~{i,#},Print@s]&

¡Pruébelo en línea!

Llamar como f[][n]. Imprime los resultados.

EngineerToast Nov 03 2020 at 13:32

Excel, 64 bytes

=CHOOSE(A1,1,12,"123,321",,,"123654,321654",,38165472,381654729)

La entrada está en A1. La respuesta codificada es más corta de lo que sería el cálculo.