¿Cuántas patas son necesarias para representar números hasta %#% #%?

Question

El objetivo de las cuatro patas de puzzle es representar cada número natural, usando cuatro copias de los dígitos $ comunes y símbolos matemáticos.

Por ejemplo, 5=(\sqrt{4} + \sqrt{\sqrt{{\sqrt{4^{4!}}}}}) \div .4$.

Si queremos eliminar la restricción en el número de patas, vamos a $f(N)$ be the number of fours required to be able to represent all positive integers no greater than $N$. What is the asymptotic behaviour of $f(N)$? Can it be shown that $f(N) \sim r \log N$ for some $r$?

Para ser más específicos, vamos a restringir las operaciones a los siguientes:

• además: $x+y$
• resta: $x-y$
• multiplicación: $x\times y$
• división: $x\div y$
• exponenciación: $y^x$
• raíces: $\sqrt[x]{y}$
• raíz cuadrada: $\sqrt{x}$
• factorial de $n!$
• punto decimal: $.4$
• recurrente decimal: $. \overline 4$

Es fácil ver que $f(N)$ is $O(\log N)$. For example, with four fours, numbers up to 2$ can be represented (see here for a tool for generating solutions), so, since = 4\times4!$, we can use k-2$ a cuatro patas en el formulario $(\dots((a_1\times 96+a_2)\times 96+a_3)\dots)\times96+a_k$ para representar cada número hasta el ^k$.

Por otro lado, podemos intentar contar el número de expresiones distintas que se pueden hacer con $k$ fours. For example, if we (arbitrarily) permit factorial only to be applied to the digit $, and allow no more than two successive applications of the square root operation, we get $\frac{216^k}{18}C_{k-1}$ distinct expressions where $C_k$ is the $k$th Catalan number. (Of course, many of these expressions won't represent a positive integer, many different expressions will represent the same number, and the positive integers generated won't consist of a contiguous range from $ to some $N$.)

Utilizando la fórmula de Stirling, para un gran $k$, this is approximately $\frac{864^k}{72k\sqrt{\pi k}}$. So for $f(N)$ to grow slower than $r\log N$, tendríamos que eliminar las restricciones sobre el uso de operaciones unarias. (Es bien conocido que el uso de los registros permite que cualquier número que puede representarse con sólo cuatro patas.)

Puede este enfoque se extiende a mostrar que $f(N)$ is $\Omega(\log N)$? O hace uso irrestricto de factorial y raíces cuadradas significa que $f(N)$ is actually $o(\log N)$? Es la respuesta diferente si el uso de $x\%$ (porcentajes) también está permitida?

Answer 1

Yo soy uno de los autores del documento se hace referencia por David Bevan en su comentario. Los de cuatro patas fue una inspiración para ese problema, aunque otros han pensado sobre eso también. La versión específica del problema no se ve en el mínimo número de 1s necesarias para representar n donde uno sólo se permite la adición y la multiplicación, pero cualquier número de paréntesis. Llamar a este g(n). Por ejemplo, g(6) <= 5, ya que 6=(1+1)(1+1+1), y no es difícil mostrar que g(6)=5. Incluso en esta versión limitada del problema, la pregunta es en general difícil, incluso para obtener asymptotics.

En cierto sentido, la mayoría de las preguntas naturales de asintótica de crecimiento son algo contenido en esta pregunta, ya que uno puede escribir cualquier k como 1+1+1...+1 k veces, y 1=k/k. Así, a partir de algunos k distinto de 1 (como k=4), el asymptotics estancia delimitada dentro de un factor constante, suponiendo que la suma y la división están permitidos.

Sin embargo, en realidad el cálculo de este tipo de cosas para cualquier conjunto de operaciones es generalmente difícil. En el caso de los enteros complejidad uno tiene una forma directa de hacerlo, ya que si se calcula g(i) para todo i menor que n, el cálculo de g(n) es factible. Esto no se aplica cuando uno tiene otras operaciones en general, con la división y la resta ya de hacer un algoritmo difícil. En este caso, uno puede hacer un algoritmo, pero exactamente cómo hacerlo es más sutil. De hecho, siempre y cuando uno se limita a las operaciones binarias que esto es posible (a prueba de dibujo: ¿ qué hizo usted para buscar en todas las distintas expresiones).

La adición en la no-operaciones binarias, que hace que todo sea aún más difícil. La adición de las raíces cuadradas no hará las cosas mucho más difíciles, ni la adición de factorial por sí mismo. El par de ellos juntos hace que el cálculo de los valores específicos mucho más difícil. Mi conjetura sería que, incluso con factorial, la raíz cuadrada y las cuatro operaciones binarias, que hay números que requieren arbitrariamente un gran número de 1s, pero también sospecho que sería muy difícil de probar. Tenga en cuenta que esto ya es considerablemente más débil que lo que están pidiendo - si el orden de crecimiento es de log n. Aquí, sin embargo, las raíces cuadradas, probablemente no alterar las cosas; para que la materia se necesita tener una gran cantidad de números de la forma n^2^k con la sorprendente baja complejidad. Esto parece poco probable.

Answer 2

Usted puede conseguir 103 con cuatro 4s como (64 + 4 + sqrt(.4.)) ÷sqrt(.4.) donde 64 = sqrt(sqrt(sqrt(4^4!))) y.4. = .4recurring = 4/9.

De hecho, 113 es el primer número que no puedo con cuatro 4s.

[Disculpas: este es mi primer post nunca: no han encontrado la manera obtener la notación de la matemáticas.]

Answer 3

No puede ser %#% #% cadenas legales, por lo que no puede representar más números que.