[math-fun] Better than additive persistence
I just heard a delightful claim from a work colleague; so far I have no idea how to check or prove it. The "additive persistence" of a number is how many times you need to apply the operation "n -> sum of the digits when you write n in base 10" before you get to a single digit. For example 199 has additive persistence 3, since 199 -> 1+9+9 = 19 -> 1+0 = 10 -> 1+0 = 1. Sometimes you can get to a single digit more quickly if you're allowed to only insert + signs between *some* of the digits in the base-10 writing, rather than all of them. For example, if you're allowed to choose 199 -> 1+99 = 100, then you can get to a single digit in only 2 steps instead of 3. Here's the remarkable claim: By appropriate choice of where to insert + signs, you can always reach a single digit in at most 4 steps! It is extremely not obvious to me that any finite number of steps suffices, much less that it's 4. Right now I believe it only because the person I heard the problem from has a good record of relaying puzzles with correct solutions :-) --Michael -- Forewarned is worth an octopus in the bush.
M.K., That result is the subject of a famous paper by Ron Graham, Steve Butler, possibly Fan Chung, possibly others. There is at least one sequence based on it in the OEIS. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Wed, Jul 1, 2020 at 4:06 PM Michael Kleber <michael.kleber@gmail.com> wrote:
I just heard a delightful claim from a work colleague; so far I have no idea how to check or prove it.
The "additive persistence" of a number is how many times you need to apply the operation "n -> sum of the digits when you write n in base 10" before you get to a single digit. For example 199 has additive persistence 3, since 199 -> 1+9+9 = 19 -> 1+0 = 10 -> 1+0 = 1.
Sometimes you can get to a single digit more quickly if you're allowed to only insert + signs between *some* of the digits in the base-10 writing, rather than all of them. For example, if you're allowed to choose 199 -> 1+99 = 100, then you can get to a single digit in only 2 steps instead of 3.
Here's the remarkable claim: By appropriate choice of where to insert + signs, you can always reach a single digit in at most 4 steps!
It is extremely not obvious to me that any finite number of steps suffices, much less that it's 4. Right now I believe it only because the person I heard the problem from has a good record of relaying puzzles with correct solutions :-)
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Try %H A293929 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 A321318 Steve Butler, Ron Graham, and Richard Stong, <a href=" http://www.math.ucsd.edu/~ronspubs/mis_17_bases.pdf">Collapsing numbers in bases 2, 3, and beyond</a>, in The Proceedings of the Gathering for Gardner 10 (2012). Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Wed, Jul 1, 2020 at 7:13 PM Neil Sloane <njasloane@gmail.com> wrote:
M.K., That result is the subject of a famous paper by Ron Graham, Steve Butler, possibly Fan Chung, possibly others.
There is at least one sequence based on it in the OEIS.
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Wed, Jul 1, 2020 at 4:06 PM Michael Kleber <michael.kleber@gmail.com> wrote:
I just heard a delightful claim from a work colleague; so far I have no idea how to check or prove it.
The "additive persistence" of a number is how many times you need to apply the operation "n -> sum of the digits when you write n in base 10" before you get to a single digit. For example 199 has additive persistence 3, since 199 -> 1+9+9 = 19 -> 1+0 = 10 -> 1+0 = 1.
Sometimes you can get to a single digit more quickly if you're allowed to only insert + signs between *some* of the digits in the base-10 writing, rather than all of them. For example, if you're allowed to choose 199 -> 1+99 = 100, then you can get to a single digit in only 2 steps instead of 3.
Here's the remarkable claim: By appropriate choice of where to insert + signs, you can always reach a single digit in at most 4 steps!
It is extremely not obvious to me that any finite number of steps suffices, much less that it's 4. Right now I believe it only because the person I heard the problem from has a good record of relaying puzzles with correct solutions :-)
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Thank you, Neil! I did search a bit and found http://oeis.org/A031286, which is the sequence that is both "additive persistence" and "how many rounds it takes if you do things optimally" — since the two are the same up to 199! --Michael On Wed, Jul 1, 2020 at 7:17 PM Neil Sloane <njasloane@gmail.com> wrote:
Try
%H A293929 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 A321318 Steve Butler, Ron Graham, and Richard Stong, <a href=" http://www.math.ucsd.edu/~ronspubs/mis_17_bases.pdf">Collapsing numbers in bases 2, 3, and beyond</a>, in The Proceedings of the Gathering for Gardner 10 (2012). Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Wed, Jul 1, 2020 at 7:13 PM Neil Sloane <njasloane@gmail.com> wrote:
M.K., That result is the subject of a famous paper by Ron Graham, Steve Butler, possibly Fan Chung, possibly others.
There is at least one sequence based on it in the OEIS.
Best regards Neil
Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
On Wed, Jul 1, 2020 at 4:06 PM Michael Kleber <michael.kleber@gmail.com> wrote:
I just heard a delightful claim from a work colleague; so far I have no idea how to check or prove it.
The "additive persistence" of a number is how many times you need to apply the operation "n -> sum of the digits when you write n in base 10" before you get to a single digit. For example 199 has additive persistence 3, since 199 -> 1+9+9 = 19 -> 1+0 = 10 -> 1+0 = 1.
Sometimes you can get to a single digit more quickly if you're allowed to only insert + signs between *some* of the digits in the base-10 writing, rather than all of them. For example, if you're allowed to choose 199 -> 1+99 = 100, then you can get to a single digit in only 2 steps instead of 3.
Here's the remarkable claim: By appropriate choice of where to insert + signs, you can always reach a single digit in at most 4 steps!
It is extremely not obvious to me that any finite number of steps suffices, much less that it's 4. Right now I believe it only because the person I heard the problem from has a good record of relaying puzzles with correct solutions :-)
--Michael
-- Forewarned is worth an octopus in the bush. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
participants (2)
-
Michael Kleber -
Neil Sloane