Number Theory

Consider representing the natural numbers by using 1, +, * and brackets. One can prove easily that the best way of representing the powers of 3 is as follows:

3ⁿ = (1+1+1)*(1+1+1)*...*(1+1+1).

All the other variants contain more than 3n 1's.

Problem 1. Is 2ⁿ = (1+1)*(1+1)*...*(1+1) the best way of representing the powers of 2?

It is the best way at least for n≤39 – as verified by Janis Iraids.

More about the context – see A005245 in the The On-Line Encyclopedia of Integer Sequences.

February 26, 2011

Added April 30 , 2012

H. Altman, J. Zelinsky. Numbers with Integer Complexity Close to the Lower Bound, 2012, http://www-personal.umich.edu/~haltman/ogshort.pdf

J. Iraids, K. Balodis, J. Čerņenoks, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results, March 29, 2012, http://arxiv.org/abs/1203.6462

Complexity Theory

Consider representing the natural numbers by using 1, +, *, ^ and brackets (^ stands for exponentiation), for example: 10^(10^(10^10)). One cannot compute the “value” of this short expression in real time (whatever it means).

Problem 2. How complicated is comparing the values of two expressions based on {1, +, *, ^}, the longer expression having the length n?

More about the context – see: K. Podnieks. Towards a Real Finitism? December 2005.

February 26, 2011

Mathematical Logic

Problem 3. Prove that any formal theory of natural numbers allows deriving of contradictions – as predicted in 1908 by Henri Poincare.

More about the context – see the end of Section 6.1 of my book about Goedel's Theorem.

February 26, 2011