A285248 All positive integers n which for some k can be computed by a straight line program (SLP) of length k but not by a monotone straight line program (mSLP) of length k.

14, 23, 31, 56, 59, 62, 63, 71, 78, 79, 94, 95, 107, 115, 118, 119, 138, 141, 142, 158, 159, 161, 176, 182, 188, 191, 192, 193, 194, 195, 196, 197, 204, 208, 209, 210, 211, 212, 213, 214, 215, 221, 223, 224, 229, 236, 237, 238, 239, 240, 241, 248, 251, 252, 253, 254, 255, 267, 268, 269, 271, 280, 282, 283, 284

Offset

1,1

Comments

Or equivalently, all positive integers n which for some k can be computed by a non-monotone arithmetic circuit with initial input 1 with k nodes but not by a monotone arithmetic circuit with initial input 1 with k nodes.

In other words, all the integers which can be computed faster through the use of subtraction.

Links

Table of n, a(n) for n=1..65.

Thatchaphol Saranurak, and Gorav Jindal, Subtraction makes computing integers faster, arXiv preprint arXiv:1212.2549 [cs.CC] (2012).

Paul Sinclair, Separating the Complexity of Monotone and Non-Monotone Straight Line Programs, Unpublished masters' project, The University of Edinburgh (2017)

Paul Sinclair, Python program

Crossrefs

Sequence in context: A005734 A003694 A217837 * A102876 A188166 A184220

Adjacent sequences: A285245 A285246 A285247 * A285249 A285250 A285251

Keyword

nonn

Author

Paul Sinclair, Apr 15 2017

Status

approved