¿Cuántas potencias de 2 son fáciles de duplicar?

Question

Posible duplicado:
¿Es 2048 la mayor potencia de 2 con todos los dígitos pares (base diez)?

Números escritos en base $10$ son más fáciles de duplicar cuando sus dígitos se encuentran en el rango $0, \ldots, 4$ para que no se realice ningún acarreo. Por ejemplo, ...

• $1$ es fácil de duplicar, dando lugar a $2$ ;
• $2$ también es fácil de duplicar, dando lugar a $4$ ;
• $4$ también es fácil de duplicar, dando lugar a $8$ ;
• pero $8$ no es fácil de duplicar, ya que $8+8 = 16$ implica una carga.

Los únicos números $2^n$ que son fáciles de duplicar que yo sepa son los tres mencionados anteriormente, junto con $2^5 = 32$ y $2^{10} = 1024$ . Mi sospecha es que $2^{10}$ es el último poder de $2$ Y esa es mi pregunta:

Mi pregunta es: Es $2^{10} = 1024$ el último ejemplo de un poder de $2$ que es fácil de duplicar? Si no es el último ejemplo, ¿cuántos más hay? ¿Existe una(n infinita) familia de ejemplos que sea fácil de producir?

Hay un teorema de Kummer que se puede utilizar para resolver una "base $p$ análogo" de esta pregunta para $p$ un primo:

Teorema (Kummer): En $p$ -Aritmética radical, el número de veces que se realiza un acarreo al sumar los números $n$ y $m$ (en base $p$ ) es igual al número de veces $p$ divide el coeficiente binomial $\binom{n+m}{m}$ .

No he encontrado ningún análogo que se mantenga en la base $10$ . Un obstáculo esencial es que $\binom{5}{3} = 10$ muestra que $2 + 3$ lleva cuando se escribe tanto en base $2$ y la base $5$ pero no en la base $10$ . Debido a este tipo de fenómeno, sospecho que esta no es la manera correcta de enfocar mi problema, pero ayuda a formar una pregunta completa y pensé que alguien podría encontrarla linda.

Answer 1

Demasiado largo para un comentario.

La pregunta que se hace es básicamente la siguiente: ¿cuántas potencias de dos sólo tienen los dígitos 0,1,2,3 y 4? O, de forma similar, qué potencia de dos tiene todos los dígitos pares $2^{n+1}$ tiene esta propiedad si $2^n$ es fácil de duplicar.

Es muy fácil demostrar que hay infinitas potencias de dos que no tienen esta propiedad. En realidad, utilizando la irracionalidad de $\log_2(10)$ es fácil demostrar que, dado cualquier $n$ -de cifras, hay infinitas potencias de dos que empiezan por ese número. Y también se puede obtener un límite inferior del número de potencias hasta $N$ de dos que pueden empezar con una determinada combinación, pero dudo mucho que esto pueda llevarte a alguna parte. El mejor resultado que puedes esperar con este enfoque es que entre $1$ y $N$ al menos $p\%$ no son fáciles de doblar, donde probablemente se pueden conseguir porcentajes altos pero nunca el 100 $\%$ .

Answer 2

Siguiendo la típica tradición experimental, vamos a escribir un código para comprobarlo.

(defun difficult-to-double-p (n)
  (loop :for (x y) := (multiple-value-list (floor n 10))
          :then (multiple-value-list (floor x 10))
        :thereis (> y 4)
        :until (zerop x)))

(defun test (max-pow)
  (loop :for x := 1 :then (* 2 x)
        :for i :from 0 :to max-pow
        :unless (difficult-to-double-p x)
          :do (format t "~D " i)))

Esto imprimirá las potencias de 2 que satisfagan su condición. Lo he probado hasta $n=500,000$ y sólo se ha encontrado con $\{0, 1, 2, 5, 10\}$ . ¿Es una coincidencia que esas potencias de 2, excepto $n=0$ ¿son factores de 10?

Aquí está el resultado para los curiosos.

> (test 500000)
0 1 2 5 10

Evaluation took:
  174.270 seconds of real time
  174.940405 seconds of total run time (173.307653 user, 1.632752 system)
  [ Run times consist of 5.225 seconds GC time, and 169.716 seconds non-GC time. ]
  100.38% CPU
  371,799,804,896 processor cycles
  46,761,694,928 bytes consed

NIL

EDITAR : En lugar de doblar, intentemos $k$ -tupling. Aquí hay una buena tabla para $2 \le n \le 100$ :

2: 0 1 2 5 10
3: 0 1 5
4: 0 1 5
5: 0
6: 0
7: 0 3 4
8: 0
9: 0
10: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
11: 0 1 2 3
12: 0 1 2
13: 0 1
14: 0 1
15: 0
16: 0
17: 0
18: 0 2 6
19: 0 4
20: 0 1 2 5 10
21: 0 1 2
22: 0 1
23: 0 1
24: 0 1
25: 0
26: 0
27: 0
28: 0
29: 0
30: 0 1 5
31: 0 1
32: 0 1 2
33: 0 1
34: 0 1
35: 0
36: 0
37: 0
38: 0 2
39: 0 4
40: 0 1 5
41: 0 1
42: 0 1
43: 0 1
44: 0 1
45: 0
46: 0
47: 0
48: 0 2
49: 0 2
50: 0

EDITAR 2 : A continuación, vamos a intentar cambiar la base $b$ donde los dígitos deben estar entre $0$ y $\tfrac{b}{2}-1$ si $b$ está en paz, $\lfloor b/2\rfloor$ si impar. Aquí hay una tabla de $b$ para $2 \le n\le 100$ .

3: 0 2 8
4: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100
5: 0 1 5 8
6: 0 1 3 9
7: 0 1 3 4 6 9
8: 0 1 3 4 6 7 9 10 12 13 15 16 18 19 21 22 24 25 27 28 30 31 33 34 36 37 39 40 42 43 45 46 48 49 51 52 54 55 57 58 60 61 63 64 66 67 69 70 72 73 75 76 78 79 81 82 84 85 87 88 90 91 93 94 96 97 99 100
9: 0 1 2 8 13 14
10: 0 1 2 5 10
11: 0 1 2 4 8 14 30
12: 0 1 2 4 6 12
13: 0 1 2 4 5 9 24
14: 0 1 2 4 5 8 10 25
15: 0 1 2 4 5 6 8 9 12 13 16 24
16: 0 1 2 4 5 6 8 9 10 12 13 14 16 17 18 20 21 22 24 25 26 28 29 30 32 33 34 36 37 38 40 41 42 44 45 46 48 49 50 52 53 54 56 57 58 60 61 62 64 65 66 68 69 70 72 73 74 76 77 78 80 81 82 84 85 86 88 89 90 92 93 94 96 97 98 100
17: 0 1 2 3 11 18
18: 0 1 2 3 7 13
19: 0 1 2 3 6 14 18 19 34
20: 0 1 2 3 6 7 11
21: 0 1 2 3 6 7 9 12 18 45
22: 0 1 2 3 5 9 11 12 19
23: 0 1 2 3 5 8
24: 0 1 2 3 5 7 25
25: 0 1 2 3 5 7 8 14 21
26: 0 1 2 3 5 6 13
27: 0 1 2 3 5 6 8 13
28: 0 1 2 3 5 6 8 12
29: 0 1 2 3 5 6 7 10
30: 0 1 2 3 5 6 7 10 11 13 15 22
31: 0 1 2 3 5 6 7 8 10 11 12 15 16 17 20 21 25 36
32: 0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 20 21 22 23 25 26 27 28 30 31 32 33 35 36 37 38 40 41 42 43 45 46 47 48 50 51 52 53 55 56 57 58 60 61 62 63 65 66 67 68 70 71 72 73 75 76 77 78 80 81 82 83 85 86 87 88 90 91 92 93 95 96 97 98 100
33: 0 1 2 3 4 14 23 42
34: 0 1 2 3 4 9 17 49
35: 0 1 2 3 4 8 12 14 40
36: 0 1 2 3 4 8 9
37: 0 1 2 3 4 7 11
38: 0 1 2 3 4 7 9 14 21 38
39: 0 1 2 3 4 7 9 13 16 33
40: 0 1 2 3 4 7 8 11 20 27
41: 0 1 2 3 4 7 8 9 15
42: 0 1 2 3 4 7 8 9 14 19 20 28
43: 0 1 2 3 4 6 12 20
44: 0 1 2 3 4 6 12 13 14 22
45: 0 1 2 3 4 6 9 12 13 14 15 24 25 26 36 45
46: 0 1 2 3 4 6 9 10 15
47: 0 1 2 3 4 6 8 19 21 39
48: 0 1 2 3 4 6 8 10 14 20
49: 0 1 2 3 4 6 8 9 13
50: 0 1 2 3 4 6 8 9 10 15 17 23

Y aquí hay una representación pictórica. El punto significa fácil, el espacio significa que no.

  4: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
  5: ..   .  .
  6: .. .     .
  7: .. .. .  .
  8: .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
  9: ...     .    ..
 10: ...  .    .
 11: ... .   .     .               .
 12: ... . .     .
 13: ... ..   .              .
 14: ... ..  . .              .
 15: ... ... ..  ..  .       .
 16: ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
 17: ....       .      .
 18: ....   .     .
 19: ....  .       .   ..              .
 20: ....  ..   .
 21: ....  .. .  .     .                          .
 22: .... .   . ..      .
 23: .... .  .
 24: .... . .                 .
 25: .... . ..     .      .
 26: .... ..      .
 27: .... .. .    .
 28: .... .. .   .
 29: .... ...  .
 30: .... ...  .. . .      .
 31: .... .... ...  ...  ..   .          .
 32: .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .
 33: .....         .        .                  .
 34: .....    .       .                               .
 35: .....   .   . .                         .
 36: .....   ..
 37: .....  .   .
 38: .....  . .    .      .                .
 39: .....  . .   .  .                .
 40: .....  ..  .        .      .
 41: .....  ...     .
 42: .....  ...    .    ..       .
 43: ..... .     .       .
 44: ..... .     ...       .
 45: ..... .  .  ....        ...         .        .
 46: ..... .  ..    .
 47: ..... . .          . .                 .
 48: ..... . . .   .     .
 49: ..... . ..   .
 50: ..... . ...    . .     .
 51: ..... . ...   . .       .
 52: ..... ..      ...         .
 53: ..... ..  . .       .    .
 54: ..... .. .           .
 55: ..... .. .  .
 56: ..... .. .. .  .
 57: ..... ...     .      .    .
 58: ..... ...    .
 59: ..... ... . .  .  . .       .                 .
 60: ..... ... . .  ..     .
 61: ..... ....  ..    .   .
 62: ..... ....  ... . ..       ..    .
 63: ..... ..... ....  ....  ...   ..    .       .
 64: ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
 65: ......           .          .            .
 66: ......     .         .
 67: ......    .    . .
 68: ......    ..              .  .                            .
 69: ......   .    .
 70: ......   . .  . .            .
 71: ......   ..     .. .   .        .    .
 72: ......   ...   . .    ..
 73: ......   ...  .    .
 74: ......  .                  .
 75: ......  .  . .      .
 76: ......  . .     .      .         .
 77: ......  . .  .  ..    .
 78: ......  . .. . .    .                  .
 79: ......  ..       .  ..              .
 80: ......  ..   .  ..
 81: ......  .. . ..
 82: ......  ...      .      .
 83: ......  ...   .  ..     .
 84: ......  ....  . .     .         .  .
 85: ......  .... .  ...  .  . .  .      .
 86: ...... .     . .  .        .   .
 87: ...... .     ..      ..      .
 88: ...... .   . ...       .
 89: ...... .   . .... .       .
 90: ...... .  .  .....        ....         ..
 91: ...... .  . .
 92: ...... .  ..             .
 93: ...... .  ...    .  .                                 .
 94: ...... . .      .        .
 95: ...... . .  .     .  .                  .
 96: ...... . . .     .     .
 97: ...... . . ..       .                     .
 98: ...... . ..    .
 99: ...... . .. .
100: ...... . ...      .   .        .

EDITAR 3 : Definir la base $b$ para ser fácil si hay un número infinito de duplicaciones fáciles.

CONJUNTO 1 : Las únicas bases fáciles son $2^j$ para $j\ge 2$ .

Un amigo se dio cuenta...

CONJUNTO 2 : Los únicos números difíciles de doblar en base $2^j$ son números cuya potencia es $\{ij-1\mid i\ge 1\}$ .

Y en la imagen, fíjate cuando la columna de la izquierda se hace más gruesa. Sucede después de cada potencia de dos.

CONJUNTO 3 : $2^n$ en la base $2^k$ es fácil de duplicar para todos $k > n$ .

Answer 3

Si lo haces en binario, todos ellos son muy fáciles de doblar: Sólo hay que añadir otro $0$ . Por ejemplo, $\{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, \ldots\}$ .

Answer 4

He aquí otro posible enfoque del problema: los poderes de $2$ finalmente caen en un ciclo $\bmod\,10^k$ para cada $k$ y este ciclo no está "lleno" en el sentido de que sólo tiene $4\cdot 5^{k-1}$ (véase http://www.exploringbinary.com/cycle-length-of-powers-of-two-mod-powers-of-ten/ ); sólo necesitamos que todos estos elementos incluyan un dígito $\geq 5$ para algunos $k$ para garantizar que siempre habrá una carga para cualquier poder de $2$ más grande que ese ciclo, y luego el resto podría ser fácilmente comprobado a mano. Si suponemos que estos elementos son todos independientes, entonces las probabilidades de que cualquiera de ellos sea "libre de dígitos altos" son $\frac{1}{2^k}$ lo que parece una buena probabilidad; desgraciadamente, hay tantos números que tienen que evitar la zona "libre de dígitos altos" que es imposible acotar razonablemente la probabilidad de no colisión lejos de $1$ (si sólo tuviéramos $2^k$ elementos, entonces tendríamos una probabilidad aproximada de $\left(1-2^{-k}\right)^{2^k}\approx e^{-1}$ de evitar una colisión; con tantos elementos como tenemos, la probabilidad de que todos nuestros elementos del ciclo sean buenos es aproximadamente $e^{-2.5^k}$ ), así que de hecho es probable que cada ciclo de poderes de $2\bmod\,10^k$ contiene algún conjunto "malo" (sin carga) de dígitos finales, aunque no haya potencias reales de $2$ hacer. Aún así, esto sería bastante fácil de comprobar para todos $k$ hasta un límite relativamente modesto, por ejemplo $k=16$ más o menos.