A285248 - OEIS

%I #24 Sep 29 2018 05:51:08

%S 14,23,31,56,59,62,63,71,78,79,94,95,107,115,118,119,138,141,142,158,

%T 159,161,176,182,188,191,192,193,194,195,196,197,204,208,209,210,211,

%U 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

%N 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.

%C 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.

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

%H Thatchaphol Saranurak, and Gorav Jindal, <a href="http://arxiv.org/abs/1212.2549">Subtraction makes computing integers faster</a>, arXiv preprint arXiv:1212.2549 [cs.CC] (2012).

%H Paul Sinclair, <a href="https://project-archive.inf.ed.ac.uk/ug4/20170972/ug4_proj.pdf">Separating the Complexity of Monotone and Non-Monotone Straight Line Programs</a>, Unpublished masters' project, The University of Edinburgh (2017)

%H Paul Sinclair, <a href="https://raw.githubusercontent.com/pbsinclair42/SLP-Analyser/master/dfs.py">Python program</a>

%K nonn

%O 1,1

%A _Paul Sinclair_, Apr 15 2017