Crear un número multiplicando por $2$ y dividiendo por $3$ (parte entera)

Question

¿Cómo puedo crear un entero positivo dado $N$ multiplicando por $2$ y dividiendo por $3$ (parte entera)?

(Se permite escribir un programa de computadora) Por ejemplo: $$100 = 2*2*2*2*2*2*2*2*2*2*2/3/3/3/3*2*2$$

(El número de $2, 3$ debe ser mínimo)

($/3$ significa $\text{div}\ 3$, por ejemplo: $2/3 = 0, 4/3 = 1...$)

¿Resolver ecuación

$$\left \lfloor{\frac {2^a}{3^b} }\right \rfloor *2^c = N$$ ayuda?

---

Si ayuda, entonces cómo resolver $$\left \lfloor{\frac {2^a}{3^b} }\right \rfloor *2^c = N$$

tal que $a > c, a+b+c$ sea mínimo.

Answer 1

Espero no haberlo pasado por alto en alguno de los maravillosos comentarios y respuestas parciales anteriores, pero ¿has intentado un enfoque directo de fuerza bruta?

Por ejemplo, las siguientes líneas de Python:

from collections import deque

Q = deque([(2,"2")])
seen = {}
consecutive=-1

def eval(s): # para verificar resultados
        i=0
        resu=1
        while i

`

enumera todas las posibles soluciones en orden de longitud creciente, y las muestra en orden de valor creciente, si no me equivoco.

Alcanza 1434 en segundos en mi laptop, y luego se bloquea (creo que debido a limitaciones de memoria, y porque 1435 tiene una descomposición significativamente más larga). En mi servidor con más memoria, llega por encima de 2400 en minutos, luego se bloquea durante un tiempo, luego sube por encima de 4400, y luego se bloquea.

P.D.: Encuentra una descomposición, pero puede haber varias descomposiciones de la misma longitud mínima.

Una vez que se conoce esta longitud mínima para un número dado $N$, otro enfoque de fuerza bruta consiste en muestrear descomposiciones aleatorias de esta longitud y verificar si son descomposiciones de $N$. Por ejemplo, después de establecer con Gottfried (ver comentarios) que las descomposiciones más cortas de 4535 tienen longitud 77, muestreé 20 billones de descomposiciones (en pocos minutos) y obtuve las siguientes descomposiciones de 4535:

22222322223323222232222232323322223222232222222223222233322233233223333222233
22222322232232322232232222323232222322232232222223232233222233222233222333233
22223222322232322232232222322232232232322232222222333223322233232223322322233

Se obtuvieron solo una vez cada una, lo que sugiere que hay muchas más soluciones, y es consistente con el hecho de que estamos lejos de muestrear todas las $2^{77} > 10^{23}$ posibles descomposiciones.

¡Esto es un terrible desperdicio de recursos computacionales, por supuesto!

`

Answer 2

No estoy seguro si es óptimo, pero no debería ser demasiado malo encontrar la potencia más alta de $2$ que divide a $N$. Dejemos que esto sea $c$.
Deje que $M=N/2^c$
Comience con $a=b=0$
Si $\lfloor \frac {2^a}{3^b}\rfloor \lt M: a=a+1$
Si $\lfloor \frac {2^a}{3^b}\rfloor \gt M: b=b+1$
De lo contrario, devuelva $a,b,c$
Vuelva al primer Si

Tal vez quieras iterar sobre $0$ hasta este $c$ para el exponente final e intentar todas las posibilidades.

Después de algunos intentos, siempre encontré la mejor respuesta con $c$ lo más grande posible, pero no he probado que sea la mejor.

Answer 3

Lo que estoy intentando es esto.

Vamos en sentido inverso; comenzando en el valor $w_0=N$ y luego $w_1=w_0/2^{\nu_2(w_0) }$.

Después, posiblemente uno de $\{3w_1,3w_1+1,3w_1+2\}$ sea una potencia perfecta de $2$. Si lo es, hemos resuelto el problema.

Si no, posiblemente uno de $ 3^2 \cdot w_1 +\{0,1,2,3,4,5,6,7,8\}$ sea una potencia perfecta de $2$. Si sí, entonces hemos resuelto el problema.

Si no, posiblemente uno de $ 3^3 \cdot w_1 +\{0,1,\ldots,3^3-1\}$ sea una potencia perfecta de $2$.

Podemos proceder de la manera obvia.

• Para $N=w_0=100$ obtuve $2^{A_1}=4$ así que $A_1=2$ y $w_1=25$
  Luego en el intervalo $25\cdot 3 \to 75+\{0,1,2\}$ no hay una potencia perfecta de $2$
  Luego en el intervalo $25 \cdot 3^2 \to 225+\{0,1,...,8\}$ no hay una potencia perfecta de $2$
  Luego en el intervalo $25 \cdot 3^3 \to 675+\{0,1,...,26\}$ no hay una potencia perfecta de $2$

  Luego en el intervalo $25 \cdot 3^4 \to 2025+\{0,1,...,80\}$ hay una potencia perfecta de $2$ (es decir, $2^{11}$ y tenemos la solución (que ya fue dada por el OP):

  $ \qquad \qquad 1 \cdot 2^{11} \backslash 3 \backslash 3\backslash 3\backslash 3 \cdot 2^2 = N (= 100)$
  donde "$\backslash$" significa división entera y procedemos de izquierda a derecha sin compactar las divisiones enteras.

Sin embargo, aún no intenté averiguar si esta es una solución óptima de alguna manera...

---

Por ejemplo, usando $w_1=25$ da $4$ pasos de multiplicación por $3$ (incluyendo la corrección del residuo) pero si usamos $w_1=w_0=100$ entonces necesité $57$ multiplicaciones por $3$ (incluyendo las correcciones de residuo). Así que claramente hay criterios de optimalidad que definir/satisfacer.

---

actualización1
Me pareció interesante que una restricción simple sea entonces equivalente con la transformación de Collatz. Si eliminamos el requisito de que en el ejemplo listado no aumentamos el exponente a 3 hasta que ocurra una potencia perfecta de 2 en el intervalo $25*3^k + \{0,1,2,...,3^k-1\}$ pero en su lugar en un número par que ocurre (en un residuo impar) eliminamos el factor par y luego procedemos tomando ese valor para la iteración, simplemente tenemos la transformación $(3a+1)/2^A$, y podríamos usar la órbita de esa transformación como límite superior para la longitud óptima, dando una normalización básica de la representación de un número.

Como tal vez una opción más interesante, miré otra restricción:
En el ejemplo, verifica los intervalos usando $N=25$ nuevamente:
$$ 25\cdot 3 \to w_{1,k}=75+\{1\}_k \\ 25 \cdot 3^2 \to w_{2,k}=225+\{1,3,...,7\}_k \\ 25 \cdot 3^3 \to w_{3,k}=675+\{1,3,...,25\}_k \\ \vdots \\ 25 \cdot 3^e \to w_{e,k}=25 \cdot 3^e +\{1,3,...,3^e-2\}_k $$ Prueba los números pares $w_{e,k}=2^j \cdot r_k$ (= elimina el factor primo par $2^j$) a lo largo de un aumento en $e$ y $k$ hasta la primera vez que $r_{k}<25$. Y itera, hasta que lleguemos a $r_k=1$.
Esto da una trayectoria de valores intermedios estrictamente decrecientes, siendo otro candidato para la normalización. Desafortunadamente, este método a veces necesita incluso más pasos de la operación básica que usar la regla $3a+1$, por lo que nuevamente este método no siempre produce una representación óptima (más corta) de algún $N$. Sin embargo, parece una pregunta interesante probar que tal regla siempre es aplicable en todo momento, llevando hacia $1$.

Para tener una mejor visión de las posibilidades de encontrar una representación óptima, la siguiente imagen :

Aquí podemos comenzar en la columna izquierda, con alguna potencia de 2, y caminar hacia la derecha por los pasos de $ /3$, hasta que ocurra $2$ o $1$. Si asumimos que este proceso cubre todos los números naturales, podría ser la mejor estrategia para obtener una trayectoria más corta para cualquier número $N$. Si contamos los pasos hacia abajo y luego pasos hacia la derecha hacia algún número $N$ como longitud de la trayectoria, parece que las longitudes hacia algunos duplicados (para algunos $N$ pequeños visibles en la parte derecha y coloreados de naranja) son siempre más largas. Para ayudar a la intuición, coloqué líneas indicadoras de duplicados para los valores $N=8$ y $N=42$ en la imagen.

Para la pregunta de si todos los números están cubiertos por este esquema, ordené por fuerza bruta todos los valores intermedios que ocurren menores que $1000$ y usando las primeras $120$ filas de la tabla obtuve la siguiente lista de números que ocurren $N$ (una parte más pequeña de ellos ocurre múltiples veces):

    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   83   84   85   86   87   88   89   90
   92   93   94   95   97   98   99  100  101  102
  103  105  106  107  109  110  112  113  115  116
  118  119  121  122  124  126  127  128  129  131
  132  133  134  136  138  140  141  142  143  145
  147  149  151  153  155  157  159  161  163  166
  168  170  172  174  177  179  181  184  186  189
  191  194  196  199  201  202  204  207  210  212

Pero creo que no es muy difícil demostrar que la tabla infinita realmente cubre todos los números naturales.

---

Al mirar las soluciones en la respuesta de @HandeBruijns, por ejemplo $N=11$, tiene una representación mucho mejor/más corta. Aplicando el principio de mi esquema a ellos, por ejemplo para $N=11$ puedo hacer esta ruta:

y indica que probablemente necesitamos mirar a la derecha de la tabla mucho más de lo posible en la imagen de ese pequeño segmento de la primera tabla.

Answer 4

Se aprendieron lecciones de experimentos numéricos. Las reglas básicas con mi último intento son:

1. Es más fácil trabajar al revés: definir secuencias de operaciones en orden de concisión y ver qué números resultan, en lugar de definir un número y descubrir cuál es su secuencia óptima.
2. Los números pares óptimos siempre terminan con (*2) . Los números impares siempre terminan con (/3) .
3. Los números pares siempre pueden construirse a partir de los anteriores multiplicando este último por 2 .
4. Todos los patrones se generan en orden, es decir, con contando binario e interpretando los bits como:
   0 → (*2) , 1 → (/3) .
5. La interpretación de la codificación binaria debe terminar en el bit más a la izquierda, por lo tanto, con (/3) como la última operación.
6. Las reglas anteriores ( 4 , 5 ) también resultan en números pares; deséchelos y use en cambio la regla ( 3 ).
7. Nuestro método es de fuerza bruta en todos los aspectos; es codicioso en cuanto a memoria y tiempo de computación.
8. Se encontrará una enorme cantidad de duplicados, la mayoría de ellos siendo 0 . Deshágase de ellos lo antes posible.
9. Bastante afortunadamente, el primer patrón encontrado con números impares siempre es el mejor. Consérvelo y deseche el resto.
10. Encontrar una secuencia contigua de números con sus patrones óptimos se ha convertido ahora en una cuestión de clasificación.
11. Dado un número máximo de operaciones, (grandes) brechas en la secuencia contigua de números se esperan que ocurran pronto.
12. El último intento (22 bits) fue interrumpido por la primera brecha (en 51) en la secuencia contigua de números.

Notas. Si no se tiene en cuenta la regla (6), se encontrarán resultados subóptimos como el siguiente: 2*2*2*2/3*2/3*2*2*2/3 = 8 en lugar de 2*2*2 = 8Se encuentran fuentes y salidas del programa acompañante en: Publicaciones / referencias MSE 2021.
La mayoría de las operaciones no son conmutativas ni asociativas. En cuanto a la regla (6), se nota lo siguiente: $$ 2^{\mbox{ par}}/3 = \mbox{impar} \qquad ; \qquad 2^{\mbox{ impar}}/3 = \mbox{par} = 2^{\mbox{ par}}/3\times 2 $$ Salida de mi último intento: 1 = 2*2/3 (#2) 2 = 2 (#0) 3 = 2*2*2*2/3*2/3 (#6) 4 = 2*2 (#1) 5 = 2*2*2*2/3 (#4) 6 = 2*2*2*2/3*2/3*2 (#7) 7 = 2*2*2*2*2*2/3/3 (#7) 8 = 2*2*2 (#2) 9 = 2*2*2*2*2*2/3/3*2*2/3 (#10) 10 = 2*2*2*2/3*2 (#5) 11 = 2*2*2*2/3*2*2*2/3*2*2/3*2/3 (#13) 12 = 2*2*2*2/3*2/3*2*2 (#8) 13 = 2*2*2*2/3*2*2*2/3 (#8) 14 = 2*2*2*2*2*2/3/3*2 (#8) 15 = 2*2*2*2/3*2*2*2*2*2/3*2/3*2/3*2/3 (#16) 16 = 2*2*2*2 (#3) 17 = 2*2*2*2/3*2*2*2/3*2*2/3 (#11) 18 = 2*2*2*2*2*2/3/3*2*2/3*2 (#11) 19 = 2*2*2*2/3*2*2*2/3*2*2/3*2/3*2*2*2/3*2/3 (#19) 20 = 2*2*2*2/3*2*2 (#6) 21 = 2*2*2*2*2*2/3 (#6) 22 = 2*2*2*2/3*2*2*2/3*2*2/3*2/3*2 (#14) 23 = 2*2*2*2/3*2*2*2*2*2/3*2/3*2/3 (#14) 24 = 2*2*2*2/3*2/3*2*2*2 (#9) 25 = 2*2*2*2*2*2*2*2/3*2*2/3*2/3/3 (#14) 26 = 2*2*2

Answer 5

Mientras que la 2ª respuesta mía proporciona un método de fuerza bruta (restringido), este método no se puede utilizar cuando la longitud descompuesta es superior a 30 o así: el tiempo de cálculo crece exponencialmente con la longitud. (Si usamos para los dígitos disponibles para los residuos módulo 3 solo los residuos $\{0,1\}$ tenemos un problema de $2^\text{length}$ en lugar de un problema de $3^\text{length}$, pero vemos que el método pronto alcanzará su límite.)

Aquí he aplicado mi algoritmo "estrictamente decreciente" en algunos números de ejemplo $a_0$ tomados de las páginas de Collatz de Eric Roosendaal. Creo que son números "complicados": poseedores de récords de duración, demora y trayectoria; y el algoritmo "estrictamente decreciente" puede manejar números con docenas (o incluso cientos) de dígitos. La longitud de la trayectoria del algoritmo "estrictamente decreciente" es en todos los casos drásticamente más corta que la trayectoria original de Collatz. Por un lado, hay ejemplos donde las descomposiciones "estrictamente decrecientes" no son óptimas, pero podrían ser el mejor enfoque sistemático disponible cuando la longitud de la descomposición se vuelve grande y la memoria y/o el tiempo de cálculo se vuelven galácticos cuando la fuerza bruta combinatoria completa ya no es aplicable. (Esto me recuerda, por cierto, al problema de las "reglas perfectas" y "reglas óptimas", creo que hay una entrada en Wikipedia)

No doy la tabla en mathjax porque me gustaría tener colores, etc., y eso no es mi área de expertise... Así que aquí hay una imagen de la tabla, y debajo los datos en bruto.

---

Roosendaal : 
aquí: idx= índice en la página web de E.R.
idx   a0                  collatz  collatz   collatz    stric dec       óptimo??
                           N (3^N)  S (2^S)  longitud(N+S)# de tokens         
      página: Récords de deslizamiento                                         
32    180352746940718527    714       1189      1903        241       
20            1200991791    326        547       873        113       
10                626331    189        319       508         84        
      página: Récords de demora                                         
100   14022512981985        590        979      1569        199       
96     3743559068799        583        966      1549        179       
66        1341234558        370        617       987        134       
30             26623        113        194       307         77        
      página: Récords de trayectoria                                           
93  274133054632352106267   672       1133      1805        280       
88    1980976057694848447   547        928      1475        216       
      página: (otro)                                               
30           903             41         75       116         54        

Eric Roosendaal: http://www.ericr.nl/wondrous/
Récords de deslizamiento: http://www.ericr.nl/wondrous/glidrecs.html
Récords de demora: http://www.ericr.nl/wondrous/delrecs.html 
Récords de trayectoria: http://www.ericr.nl/wondrous/pathrecs.html

El código Pari/GP es el siguiente (solo un poco ajustado para legibilidad, lo mejoraré más tarde)

\\ Pari/GP
\\ de algún a0 encuentra entre a1=a0*3^e3 ... a1+(3^e3 -1) un número a2 divisible por
\\    2^e2 de tal manera que a3=a2/2^e2 < a0 . Si para e3=1 no hay tal número,
\\ aumentar e3 hasta tener éxito o e3>maxe3. 
\\ Devolver una lista corta de primeras soluciones con e3 crecientes
\\
\\ la rutina de usuario "mcc( [vectorv,vectorv,...,vectorv])" devuelve una concatenación
\\  de matriz rectangular y "VE()" extrae las filas y columnas principales de la matriz
\\
{findstepdown(a0,maxe3=4)=mi(aa,ae,a1,p3,a2,m2,r1,A,res_a,res_A,res_e3,res_r,il);
      res_a=res_e3=res_A=res_r=vectorv(maxe3);il=0; \\ vectores de valores resultantes
      for(e3=1,maxe3,
          p3=3^e3;[aa=p3*a0,ae=aa+p3-1,p3-1,m2=2^ceil(ld3*e3)];
          [r1= (-aa % m2),p3-1] ; \\ >p3-1
          if(r1>=p3,siguiente());      \\ el residuo debe estar en el intervalo a1..a1+3^e3-1
          A=valuation(aa +r1,2);a1=(aa+r1)>>A;
          il++;
          res_e3[il]=e3;res_a[il]=a1;res_A[il]=A;res_r[il]=r1; 
               \\ llenar lista de vectores de resultado 
       ); return(VE(mcc([res_e3,res_a,res_A,res_r]),il,4));
   }

\\ llama a "findstepdown()" repetidamente hasta que a1 se acerca a 1 
{strictlydecreasing(a0,maxstepdown=8)=mi(lambda,st,st1,st2,res,res1,e3,e2,a1,r1);
 lambda=0; st=Str("");a1=a0;print1(a0,":");
 for(k=1,40,
     res= findstepdown(a1,maxstepdown); 
          res1=res[1,]; \\ ¡usa siempre el primer resultado de la disminución de paso!
          e3=res1[1];a1=res1[2];e2=res1[3];r1=res1[4];lambda+=(e2+e3);
          print1([a1,lambda]);
          st1=st2="";
             for(k=1,e2,st1=Str(st1,"*2"));
             for(k=1,e3,st2=Str(st2,"/3"));
             st=Str(st1,st2,st);
     si(a1==1,romper())
     );
  print("");
  print(a0,"=",Str(1,st," (#"lambda")")); }

  \\ aplicar esto
  a0=4535
  strictlydecreasing(a0) \\ imprime una descomposición de a0

Resultados ejemplares: descomposiciones de dos valores no demasiado grandes $a_0$:
Estos también son un desafío para los métodos competidores para encontrar descomposiciones mejores/óptimas.

leyenda: -------------------------------------------------------------
  a_0 :[a_k consecutivos, longitud parcial acumulativa] [...,...] ... 
626331:[528467, 8][297263, 14][3919, 28][3307, 36][2791, 44][785, 51][589, 54][221, 58][83, 62][47, 68][5, 79][1, 84]
  a_0 = cadena de descomposición comenzando en 1 creciendo hacia a_0:
626331=1*2*2*2*2/3*2*2*2*2*2*2*2*2/3/3/3*2*2*2*2/3/3*2*2*2/3*2*2*2/3*2*2/3*2*2*2*2*2/3/3*2*2*2*2*2/3/3/3*2*2*2*2*2/3/3/3*2*2*2*2*2*2*2*2*2*2*2/3/3/3*2*2*2*2/3/3*2*2*2*2*2/3/3/3 (#84)

26623:[14215, 19][1999, 27][1687, 35][949, 41][89, 47][67, 50][19, 57][11, 63][5, 72][1, 77]
26623=1*2*2*2*2/3*2*2*2*2*2*2/3/3/3*2*2*2*2/3/3*2*2*2*2*2/3/3*2*2/3*2*2*2*2*2/3*2*2*2*2/3/3*2*2*2*2*2/3/3/3*2*2*2*2*2*2/3/3*2*2*2*2*2*2*2*2*2*2*2*2/3/3/3/3/3/3/3 (#77)