OFFSET
1,1
COMMENTS
Consider an integer complexity measure c(n) which is the number of ones required to build n using +, -, *, and "floor division" which for convenience will be written in this entry (after Python notation) j//k = floor(j/k). In other words, c(n) is defined identically to A091333(n) except that this floor division is also allowed, and identically to the complexity b(n) described in A348069 except that division is extended to all pairs of natural numbers by taking the floor of the quotient. Clearly for all n, c(n) <= b(n) <= A091333(n). This sequence lists the integers k for which c(k) < A091333(k).
EXAMPLE
The smallest n for which c(n) as defined in the comments is strictly less than A091333(n) is 1860043, because 1860043 = (7*3^12)//2 which requires c(7) + 12*c(3) + c(2) = 6 + 12*3 + 2 = 44 ones to express with these operations, whereas A091333(1860043) = A005245(1860043) = 45 by virtue of the minimal expression 1860043 = 2(2^2*5*7(3^4(3^4+1)+1)+1)+1 requiring 2+2*2+5+6+3*4+3*4+1+1+1+1 = 45 ones. Hence, the first term in this sequence is 1860043.
The next three terms with their respective minimal expressions:
3198487 = (3^9(2^2*3^4+1))//2 [46 ones] = 2*3(3^2(2^2*3*5+1)(2^2*3^5-1)+2)+1 [47 ones] = 2*3(2(7(2^2*3+1)(2^2*3(3^5+1)+1)+1)+1)+1 [48 ones]. Thus n=319487 is the least n for which c(n) < A091333(n) < A005245(n).
4782847 = (3^5(2*3^9-1))//2 [47 ones] = 2*3(2*5(3^2(2^2*3^3(3^4+1)+1)+1)+1)+1 [48 ones]
5580129 = 3*1860043 = 3((7*3^12)//2) [47 ones] = 2^3(3*5*7(3^4(3^4+1)+1)+1)+1 [48 ones]. Note this example critically takes advantage of the fact that * and // are not associative.
CROSSREFS
KEYWORD
nonn
AUTHOR
Glen Whitney, Sep 28 2021
STATUS
approved