Integer Complexity With Hyperoperations

[Joshua Searle]

Seqfans,

I'd been thinking about integer complexity recently, and there is a good page on the oeis wiki [https://oeis.org/wiki/User:Glen_Whitney/IntegerComplexityTable] that covers what number and operator sets have entries.

One thing caught my attention was that the primary metric is the number of 1s. The operators themselves are not part of the calculation. You could simply count each operation as a 1 and progress this way, but an alternative - and the one I have been focusing on - is to replace each operation with a number corresponding to its "rank" with the hyperoperation hierachy - addition has rank 1, multiplication 2, exponents 3 and so on.

This means that the operation 1+1 for example, is now 1[1]1, making a total "cost" of 3. the brackets of the operator are ignored, as are any parentheses (it is possible to convert into an RPN format that doesn't require them).

I also decided to include the inverse operators subtraction, division, logarithms, super-logarithms and so on, which have the same cost as their counterpart. 0 can be made from 1s with 1-1 and this would be 1[1]'1, with the extra mark being there being only there to differentiate it from addition.

Initially, I tried using 0s as the unit instead of 1s. This is because the 0th operation is defined as the successor function. Successorship, or perhaps more fittingly in this context, "Zeration", is a unary function, and what with 0 being the base, this combination makes for an extremely efficient operator, to the point that addition is never better. After several ideas, what seemed to work was to define z(n) as nzn = n+1, with the z being used in an analogous way to an addition symbol.

The cost of n starting from 0 begins:

1,3,7,13,17,23,27,33,31,33,37,...

Addition is first better at n=3, multiplication is first joint best at 6 and sole best at 8, exponents are first joint best at 9 and sole best at 16. (2[3]4 and 2[4]3 have the same cost so you can consider this to be when at least exponents are required). For tetration (repeated exponentiation) I found that 16384 is better but it may well be improvable beyond simply putting a few -1s on it.

Subtraction first makes an appearance at joint best at 7 and sole best at 23. For division, I went on a wild goose chase but after some time I realised I missed the simple 41 as being best. I'll leave logarithms and square roots to the reader!

After this I turned my attention back to using 1s, and with analogous rules, the cost for n starting from 0 is:

3,1,3,5,7,9,11,13,13,13,15,...

With zeration gone we have these milestones:

multiplication joint best at 6, sole best at 8

exponents joint best at 8, sole best at 16

subtraction joint best at 9, sole best at 23

division joint best at 40, sole best at 41

tetration is <16384

I'm aware that this message is getting long, so as a final thing I wanted to mention, one ruleset I tried was to "optimise" the operation so 1+2+3 would be +(1,2,3). This works perfectly well until inverse operations. You can define -(1,2,3) as -(1,+(2,3)) and similarly for division but this doesn't work for logs and higher order versions. I was initially fooled that it was true until I got suspicious and checked log_{2^3}(2^(3^2)) and found it giving 3 instead of 2 :)

Hopefully this is of interest,

Joshua

[Joshua Searle]

Apologies for the double message, but the moment I clicked send I realised that by nesting the logarithm until the end is a binary function would work, which is how you'd define something like +(a,b,c,...) in the first place from simple addition.