%I #84 May 06 2022 15:11:22

%S 0,10,19,118,3187,3014173,3003344034004

%N Smallest number in base 10 that cannot be collapsed to a single digit using fewer than n plus signs.

%C A253057 considers the number of applications needed to collapse numbers. An alternative is to look at the number of times a plus sign needs to be inserted, disregarding the number of applications.

%C The sequence is believed to be infinite. Only five terms, a(1)-a(5), were provided by Butler et al. (2016).

%C Butler et al. (2016) conjectured that collapsing each term x by simply inserting a plus sign in the "middle" of the decimal expansion and adding would require in the order of log (log x) plus signs.

%C a(5) reveals that all five-digit and six-digit numbers can be collapsed by inserting no more than four plus signs.

%C a(6) should contain at least 13 digits. After inserting a plus sign in the middle of numbers with 7, 8, 9 and 10 digits and performing the addition, the resulting sums must have at most 5, 5, 6 and 6 digits, respectively. Furthermore, after inserting a plus sign in the middle of any number with 11 or 12 digits and performing the addition, the result must be smaller or equal to, respectively, 1099998 and 1999998 < a(5). This means at most 4 plus signs would be required to collapse the result after the first application. It follows that all 7, 8, 9, 10, 11 and 12-digit numbers can be collapsed using no more than 5 plus signs. - _Simon Demers_, Oct 30 2017 [Updated Nov 29 2017]

%C Between 10 and 10^7-1=9999999 inclusively, 270 numbers require only one plus sign, 175803 numbers require two plus signs, 5952451 numbers require three plus signs, 3866392 numbers require four plus signs, and 5074 numbers require five plus signs. - _Simon Demers_, Oct 29 2017

%C Conjecture: Digital root for terms a(n) > 0 is 1. - _Simon Demers_ and _J. Stauduhar_, Nov 16 2017

%C Using brute-force, no new term less than 10^9 was found. - _J. Stauduhar_, Nov 20 2017

%C Proof of claim that all a(n), n > 0, have digital root 1: Assume terms a(1) to a(n) all have digital root 1, but a(n+1) = x does not. Increment a(n) by one until we reach x. Insert one plus sign into x in the optimal way that guarantees that the result of the addition, y, requires exactly n more insertions of a plus sign to arrive at a single digit. Because y requires n insertions it cannot be less than a(n), otherwise we would have found y before a(n). Because x has digital root greater than 1, y cannot equal a(n). So y must be in the range a(n) < y < x, but we already checked these before arriving at x, so no such y can exist, therefore no such x can exist. Clearly, a(n+1) cannot have digital root 0. Since no a(n+1) = x with digital root 0 or 2 through 9 can exist, a(n+1) must have digital root 1. Q.E.D. - _J. Stauduhar_, Dec 08 2017

%H S. Butler, R. Graham and R. Stong, <a href="http://orion.math.iastate.edu/butler/papers/16_03_insert_and_add.pdf">Inserting Plus Signs and Adding</a>, The American Mathematical Monthly, 123(3), March 2016, 274-279.

%H Simon Demers, <a href="https://drive.google.com/uc?export=download&amp;id=1TItQtDrhKUFwhrDALEpxP0lbfzZbTpzt">Minimum number of plus signs needed to collapse every integer 1..10^7-1=9999999.</a> Calculated using brute-force approach. Starting with i=1 and sequentially for each subsequent integer with d digits, all 2^(d-1)-1 possibilities to insert plus signs are considered in the first application. Then, lookup the minimum number of plus signs required to collapse each resulting integer after the first addition is performed. This dataset confirms a(1)=10, a(2)=19, a(3)=118, a(4)=3187, a(5)=3014173.

%H Simon Demers, <a href="https://doi.org/10.1080/00029890.2018.1538435">The smallest number that cannot be collapsed using fewer than 6 plus signs is 3003344034004</a>, Amer. Math. Monthly, 126 (April 2019) 351.

%F a(n) <= ((a(n-1)-1)^2)/3 + a(n-2) for n > 1 (conjectured). This would provide a relatively tight upper bound on a(n). If the Demers-Stauduhar conjecture in the Comments turns out to be true, this upper bound will always be an integer. - _Simon Demers_, Nov 29 2017

%e For n=3, the a(3)=118 solution reflects the fact that 1+18 = 19, 1+9 = 10 and 1+0 = 1. Alternatively, 1+1+8 = 10 and 1+0 = 1. Three plus signs are required in both cases. For a(4)=3187, one plus sign is required to obtain 31+87 = 118 = a(3).

%Y Cf. A006050, A045646, A253057.

%K nonn,base,more

%O 0,2

%A _Simon Demers_, Oct 19 2017

%E a(6) (found by _Simon Demers_) added by _Stan Wagon_, May 02 2019