login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A293929 Smallest number in base 10 that cannot be collapsed to a single digit using fewer than n plus signs. 1
0, 10, 19, 118, 3187, 3014173, 3003344034004 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

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

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.

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

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]

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

Conjecture: Digital root for terms a(n) > 0 is 1. - Simon Demers and J. Stauduhar, Nov 16 2017

Using brute-force, no new term less than 10^9 was found. - J. Stauduhar, Nov 20 2017

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

LINKS

Table of n, a(n) for n=0..6.

S. Butler, R. Graham and R. Stong, Inserting Plus Signs and Adding, The American Mathematical Monthly, 123(3), March 2016, 274-279.

S. Demers, Minimum number of plus signs needed to collapse every integer 1..10^7-1=9999999. 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.

S. Demers, The smallest number that cannot be collapsed using fewer than 6 plus signs is 3003344034004, Amer. Math. Monthly, 126 (April 2019) 351.

FORMULA

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). Under this conjecture, a(6) < 3028410951715. 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

EXAMPLE

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).

CROSSREFS

Cf. A006050, A045646, A253057.

Sequence in context: A015445 A220005 A253213 * A177203 A177167 A299575

Adjacent sequences:  A293926 A293927 A293928 * A293930 A293931 A293932

KEYWORD

nonn,base,more

AUTHOR

Simon Demers, Oct 19 2017

EXTENSIONS

a(6) (found by Simon Demers) added by Stan Wagon, May 02 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 09:58 EDT 2021. Contains 346294 sequences. (Running on oeis4.)