Dado un entero positivo n ≤ 500 :

• Encuentre el número entero positivo más pequeño k tal que todos los dígitos en la representación decimal de n * k sean 0 o d , con 1 ≤ d ≤ 9 .

• Imprima o devuelva d en menos de 30 segundos (lea más sobre eso en la sección de Aclaraciones y reglas ).

Ejemplos sencillos

Aquí están los primeros 30 valores de d .

+----+-------+---------+---+    +----+-------+---------+---+
|  n |     k |   n * k | d |    |  n |     k |   n * k | d |
+----+-------+---------+---+    +----+-------+---------+---+
|  1 |     1 |       1 | 1 |    | 16 |     5 |      80 | 8 |
|  2 |     1 |       2 | 2 |    | 17 |   653 |   11101 | 1 |
|  3 |     1 |       3 | 3 |    | 18 |     5 |      90 | 9 |
|  4 |     1 |       4 | 4 |    | 19 |   579 |   11001 | 1 |
|  5 |     1 |       5 | 5 |    | 20 |     1 |      20 | 2 |
|  6 |     1 |       6 | 6 |    | 21 |    37 |     777 | 7 |
|  7 |     1 |       7 | 7 |    | 22 |     1 |      22 | 2 |
|  8 |     1 |       8 | 8 |    | 23 |  4787 |  110101 | 1 |
|  9 |     1 |       9 | 9 |    | 24 |    25 |     600 | 6 |
| 10 |     1 |      10 | 1 |    | 25 |     2 |      50 | 5 |
| 11 |     1 |      11 | 1 |    | 26 |    77 |    2002 | 2 |
| 12 |     5 |      60 | 6 |    | 27 |    37 |     999 | 9 |
| 13 |    77 |    1001 | 1 |    | 28 |    25 |     700 | 7 |
| 14 |     5 |      70 | 7 |    | 29 | 37969 | 1101101 | 1 |
| 15 |     2 |      30 | 3 |    | 30 |     1 |      30 | 3 |
+----+-------+---------+---+    +----+-------+---------+---+

Ejemplos no tan fáciles

Una particularidad de este desafío es que algunos valores son mucho más difíciles de encontrar que otros, al menos con un enfoque puramente de fuerza bruta. A continuación se presentan algunos ejemplos de n que conducen a un alto valor de k .

+-----+------------+---------------+---+    +-----+------------+---------------+---+
|   n |          k |         n * k | d |    |   n |          k |         n * k | d |
+-----+------------+---------------+---+    +-----+------------+---------------+---+
|  81 |   12345679 |     999999999 | 9 |    | 324 |   13717421 |    4444444404 | 4 |
| 157 |   64338223 |   10101101011 | 1 |    | 353 |   28615017 |   10101101001 | 1 |
| 162 |   13717421 |    2222222202 | 2 |    | 391 |  281613811 |  110111000101 | 1 |
| 229 |   43668559 |   10000100011 | 1 |    | 405 |   13717421 |    5555555505 | 5 |
| 243 |   13717421 |    3333333303 | 3 |    | 439 |   22781549 |   10001100011 | 1 |
| 283 |   35371417 |   10010111011 | 1 |    | 458 |   43668559 |   20000200022 | 2 |
| 299 |   33478599 |   10010101101 | 1 |    | 471 |   64338223 |   30303303033 | 3 |
| 307 |   32576873 |   10001100011 | 1 |    | 486 |   13717421 |    6666666606 | 6 |
| 314 |   64338223 |   20202202022 | 2 |    | 491 |  203871711 |  100101010101 | 1 |
| 317 | 3154574483 | 1000000111111 | 1 |    | 499 |   22244489 |   11100000011 | 1 |
+-----+------------+---------------+---+    +-----+------------+---------------+---+

Aclaraciones y reglas.

• n * k siempre contendrá al menos un dígito d , pero puede no contener ningún cero.
• Este es el código de golf , por lo que gana el código más corto en bytes. Sin embargo, su programa o función debe poder devolver el resultado para cualquier 1 ≤ n ≤ 500 en menos de 30 segundos en hardware de rango medio.
• Tenga en cuenta que algunos valores son más difíciles de encontrar que otros. Es improbable que un programa que intente aplicar fuerza bruta al valor de k cumpla con la restricción del límite de tiempo (un buen caso de prueba es n = 317 ). Hay métodos significativamente más rápidos para encontrar d .

Tabla de referencia

Todos los valores de d para 1 ≤ n ≤ 500 se enumeran a continuación.

n       | d
--------+--------------------------------------------------
001-025 | 1 2 3 4 5 6 7 8 9 1 1 6 1 7 3 8 1 9 1 2 7 2 1 6 5
026-050 | 2 9 7 1 3 1 8 3 2 7 9 1 2 3 4 1 6 1 4 9 2 1 6 7 5
051-075 | 3 4 1 9 5 7 1 2 1 6 1 2 9 8 5 6 1 4 3 7 1 9 1 2 3
076-100 | 4 7 6 1 8 9 2 1 4 5 2 3 8 1 9 1 4 3 2 5 6 1 7 9 1
101-125 | 1 6 1 8 7 2 1 9 1 1 1 7 1 2 5 4 9 2 7 6 1 2 3 4 5
126-150 | 6 1 8 3 1 1 6 7 2 9 8 1 6 1 7 1 2 1 9 5 2 7 4 1 3
151-175 | 1 8 9 7 5 4 1 2 1 8 7 2 1 4 3 2 1 8 1 1 3 4 1 6 7
176-200 | 8 3 2 1 9 1 2 1 8 5 6 1 4 9 1 1 6 1 2 3 7 1 9 1 2
201-225 | 3 2 7 4 5 2 9 8 1 7 1 4 1 2 5 9 7 2 3 2 1 2 1 7 9
226-250 | 2 1 4 1 1 3 8 1 6 5 4 3 7 1 6 1 2 3 4 7 6 1 8 3 5
251-275 | 1 6 1 2 3 8 1 6 7 2 9 2 1 6 5 7 3 4 1 9 1 8 3 2 5
276-300 | 6 1 2 9 7 1 2 1 4 5 2 7 9 1 1 3 4 1 7 5 8 9 2 1 3
301-325 | 7 2 3 8 5 6 1 4 3 1 1 8 1 2 9 4 1 2 1 8 1 7 1 4 5
326-350 | 2 1 8 7 3 1 4 3 2 5 8 1 2 3 2 1 6 1 8 3 2 1 4 1 7
351-375 | 9 8 1 6 5 4 7 2 1 9 1 2 3 4 5 2 1 8 9 1 7 6 1 2 3
376-400 | 8 1 9 1 2 3 2 1 6 7 2 9 4 1 3 1 7 1 2 5 9 1 2 7 4
401-425 | 1 6 1 4 5 2 1 8 1 1 3 4 7 9 5 8 1 2 1 6 1 2 3 8 5
426-450 | 2 7 4 3 1 1 9 1 7 3 4 1 6 1 4 3 2 1 4 5 2 3 7 1 9
451-475 | 1 4 3 2 5 8 1 2 9 2 1 6 1 8 3 2 1 6 7 1 3 8 1 6 5
476-500 | 7 3 2 1 6 1 2 3 4 5 6 1 8 3 7 1 6 1 2 9 8 7 6 1 5

Jalea , 16 15 14 bytes

²B€Ḍ9×þF%Þ¹ḢQS

Tiempo de ejecución cuadrático (menos de 25 segundos en TIO).

Pruébalo en línea!

Versión alternativa, 15 bytes.

2ȷB€Ḍ9×þF%Þ¹ḢQS

Tiempo de ejecución constante (aprox. 1 segundo en TIO).

Pruébalo en línea!

Cómo funciona

²B€Ḍ9×þF%Þ¹ḢQS  Main link. Argument: n

²               Take the square of n.
                This bound is high enough for all integers up to 500. 
                In fact, The highest value we need is 1387 for input 471, so
                2000 (2ȷ) is also enough (and a lot faster).

 B€             Binary; convert 1, ..., 4159 to base 2.
   Ḍ            Undecimal; convert each digit array from base 10 to integer.
                This generates the array A of all positive integers up to n²
                whose decimal representations consist entirely of 1's and 0's.
    9×þ         9 multiply table; for each x in A, yield [x, 2x, ..., 8x, 9x].
       F        Flatten; concatenate the resulting arrays, yielding the vector
                V. Note that V contains all numbers that match the regex ^d[0d]*$
                in base 10, in ascending order.
          ¹     Identity; yield n.
        %Þ      Sort the entries for V by their remainders modulo n. This places
                multiples of n at the beginning. The sorting algorithm in stable,
                so the first element of sorted V is the smallest multiple of n.
           Ḣ    Head; extract the first element.
            Q   Unique; deduplicate its digits in base 10. This yields [d, 0].
             S  Take the sum, yielding d.

JavaScript (ES6), 83 bytes

n=>{for(p=1;;p=k)for(d=0;d++<9;)for(k=p;k<p+p;k++)if(k.toString(2)*d%n<1)return d;}

Ahora vuelve 6por n=252! Intenté un enfoque recursivo, pero también tiene 83 bytes y se bloquea por los números más difíciles:

f=(n,p=1,d=1,k=p)=>k<p+p?k.toString(2)*d%n<1?d:f(n,p,d,k+1):d>8?f(n,p+p):f(n,p,d+1)

Mathematica, 103 100 97 bytes

#&@@IntegerDigits[Sort[Join@@Table[Cases[FromDigits/@{0,i}~Tuples~13/#,_Integer],{i,9}]][[10]]#]&

encuentra 317 en 0.39 segundos

Pruébelo en línea, copie / pegue el código, agregue [317] al final y presione Mayús + Intro para ejecutar

-3 bytes de @JungHwan Min
-3 bytes de @Keyu Gan

Python 2/3, 129 128 127 bytes

from itertools import*
lambda n:next(d for p in count()for d in range(1,10)for k in range(2**p,2*2**p)if d*int(bin(k)[2:])%n<1)

-1 byte: count(0) → count()
-1 byte: ==0→ <1ya que no puede ser negativo

Jalea , 21 bytes

9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ

Un enlace monádico que devuelve el número O un programa completo que lo imprime.

Una fuerza bruta de rango limitado que toma menos de 20 segundos para cualquier 1 ≤ n ≤ 500 (menos de 3 segundos para un costo de código de 1 byte - reemplace ⁴con 13).

Pruébalo en línea!

¿Cómo?

9Rṭ€0ṗ€⁴ẎḌḍ@Ðf⁸ṢDFḟ0Ḣ - Link: number, n
9R                    - range of 9 = [1,2,3,4,5,6,7,8,9]
  ṭ€0                 - tack €ach to 0 -> [[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9]]
       ⁴              - literal 16
     ṗ€               - Cartesian product for €ach
        Ẏ             - tighten (flatten by 1 level)
         Ḍ            - covert from decimal list to number (vectorises)
              ⁸       - chain's left argument (n)
            Ðf        - filter keep items for which this yields a truthy value:
          ḍ@          -   divisible? with swapped @rguments
               Ṣ      - sort
                D     - convert to decimal list (vectorises)
                 F    - flatten into a single list
                  ḟ0  - filter out zeros
                    Ḣ - head (get the first value)

PHP , 87 bytes

for(;++$i<5e3;)for($n=10;$d=--$n*decbin($i);)($y&&$d>$y)|$d%$argn?:$x=$n.!$y=$d;echo$x;

Pruébalo en línea!

PHP , 89 bytes

for(;++$i<5e3;)for($n=10;$d=--$n*decbin($i);)$d%$argn?:$r[$d]=$n;krsort($r);echo end($r);

Pruébalo en línea!