A253057 -id:A253057 - cp's OEIS frontend

A253952 Numbers that require three steps to collapse to a single digit in base 4 (written in base 10).

43, 103, 139, 154, 163, 169, 223, 343, 403, 463, 523, 547, 553, 610, 643, 649, 673, 703, 823, 847, 862, 1231, 1303, 1363, 1486, 1603, 2059, 2083, 2089, 2179, 2185, 2209, 2239, 2434, 2563, 2569, 2593, 2623, 2689, 2731

Offset: 1

Steve Butler, Jan 20 2015

One step consists of taking the number in base 4 and inserting some plus signs between the digits with no restrictions and adding the resulting numbers together in base 4. The numbers given here cannot be taken to a single digit in one or two steps. It is known that three steps always suffice to get to a single digit, and that there are infinitely many numbers that require three steps.

			As an example a(1)=43 which in base 4 can be written as 223.  There are then three ways to insert plus signs in the first step:
2+23   22+3   2+2+3
This gives the numbers (in base 4) as 31, 31, and 13 respectively.  In the second step we have one of the following two:
3+1   1+3
In both cases this gives the number (in base 4) of 10.  Finally in the third step we have the following:
1+0
Which gives 1, a single digit, and we cannot get to a single digit in one or two steps.  (Note, the single digit that we reduce to is independent of the sequence of steps taken.)

Steve Butler, Table of n, a(n) for n = 1..638
S. Butler, R. Graham and R. Stong, Partition and sum is fast, arXiv:1501.04067 [math.HO], 2014.

Cf. A253057, A253058, A253953.

A253953 Numbers that require three steps to collapse to a single digit in base 4 (written in base 4).

Original entry on oeis.org

223, 1213, 2023, 2122, 2203, 2221, 3133, 11113, 12103, 13033, 20023, 20203, 20221, 21202, 22003, 22021, 22201, 22333, 30313, 31033, 31132, 103033, 110113, 111103, 113032, 121003, 200023, 200203, 200221, 202003, 202021

Offset: 1

Steve Butler, Jan 20 2015

			As an example a(1)=223 (in base 4).  There are then three ways to insert plus signs in the first step:
2+23   22+3   2+2+3
This gives the numbers (in base 4) as 31, 31, and 13 respectively.  In the second step we have one of the following two:
3+1   1+3
In both cases this gives the number (in base 4) of 10.  Finally in the third step we have the following:
1+0
Which gives 1, a single digit, and we cannot get to a single digit in one or two steps.  (Note, the single digit that we reduce to is independent of the sequence of steps taken.)

Steve Butler, Table of n, a(n) for n = 1..637
S. Butler, R. Graham and R. Stong, Partition and sum is fast, arXiv:1501.04067 [math.HO], 2014.

Cf. A253057, A253058, A253952.

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

Original entry on oeis.org

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

Offset: 0

Simon Demers, Oct 19 2017

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

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

S. Butler, R. Graham and R. Stong, Inserting Plus Signs and Adding, The American Mathematical Monthly, 123(3), March 2016, 274-279.
Simon 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.
Simon Demers, The smallest number that cannot be collapsed using fewer than 6 plus signs is 3003344034004, Amer. Math. Monthly, 126 (April 2019) 351.

Cf. A006050, A045646, A253057.

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

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

cp's OEIS Frontend

A253058 Complete list of numbers that take three steps to collapse to a single digit in base 3 (written in base 3).

Views

Author

Keywords

Links

Crossrefs

A253952 Numbers that require three steps to collapse to a single digit in base 4 (written in base 10).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A253953 Numbers that require three steps to collapse to a single digit in base 4 (written in base 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions