mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency

My personal page

Any comments are welcome: Karlis.Podnieks@lu.lv

Mathematical Challenge


By Karlis Podnieks

University of Latvia


Number Theory

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

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

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

Problem 1. Is 2n = (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 later:

H. Altman, J. Zelinsky. Numbers with Integer Complexity Close to the Lower Bound, INTEGERS, Vol. 12A, 2012 (available online).

J. Iraids, K. Balodis, J. Čerņenoks, M. Opmanis, R. Opmanis, K. Podnieks. Integer Complexity: Experimental and Analytical Results. Scientific Papers University of Latvia, Computer Science and Information Technologies, Vol. 787, 2012, pp. 153-179 (available online).

Complexity Theory

Consider representing of 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 that 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.

According to Gödel's First Incompleteness Theorem, any formal theory of natural numbers is either inconsistent, or incomplete. The final step: prove that the second clause can be dropped.

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

Possibly, the first real step towards a solution is announced in:

N. V. Belyakin. One $omega$-inconsistent formalization of set theory. The 9th Asian Logic Conference, 16-19 August, 2005, Novosibirsk, Russia (online abstract),


where the following is announced: "From this fact follows, in particular, that the existence of strongly inaccessible cardinals is refutable in ZF."


Note. The English translation of the abstract contains an error: one should remove [in] from the statement “It is not hard to check that T is [in]consistent wrt ZF+(existence of strongly inaccessible cardinals)”.

February 26, 2011

mathematical challenge, number theory, A005245, integer complexity, complexity theory, exponentiation, mathematics is inconsistent, arithmetic is inconsistent, inconsistency