cp's OEIS Frontend

A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.

%I A346742 #21 Oct 03 2021 18:55:03
%S A346742 1860043,3198487,4782847,5580129,6111571,9300217,9566302,9595461,
%T A346742 9595462,9654511,10678027,12725059,12843157,13551745,14349271,
%U A346742 14614627,16740391,17094685,18334713,18334714,19220449,27900651,28698178,28701094,29494975,31620739,32034081,33484063,34100797,35872267,37998031
%N A346742 Numbers that may be built from fewer ones using floor(j/k) in addition to +, -, and *.
%C A346742 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).
%C A346742 Because of the inequality c(n) <= b(n) <= A091333(n), every entry in A348069 will eventually appear in this sequence. For example, the first term of A348069 is 50221174 = (7*3^15)//2, so we have c(50221174) = 53, b(50221174) = 54, and A091333(50221174) = 55.
%C A346742 The extended domain of division means that terms of this sequence are much more frequent than A348069, but it's still quite rare for division to provide more compact expressions for natural numbers (except in the presence of exponentiation, see A348089).
%e A346742 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.
%e A346742 The next three terms with their respective minimal expressions:
%e A346742 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).
%e A346742 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]
%e A346742 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.
%Y A346742 Cf. A253177 and A348069.
%Y A346742 Cf. A091333 and A005245 (other integer complexity measures).
%K A346742 nonn
%O A346742 1,1
%A A346742 _Glen Whitney_, Sep 28 2021