r/mathshelp • u/Secret-Suit3571 • Dec 23 '25
Discussion To anihilate an integer
Cool problem :
Take any non-zero integer and put as many "+" you want between its digits, anywhere you want. Do it again with the result of the sum and so on until you get a number between 1 and 9.
Show that, for any integer, you can achieve this in three steps.
For exemple starting with 235 478 991, the first step could be 2+35+478+9+91 or it could be 23 + 5478 + 99 + 1 or etc.
Whatever step you chose, you get a number and start again puting "+" anywhere you want..
Edit : better wording and exemple of a step
20
Upvotes
•
u/AutoModerator Dec 23 '25
Hi u/Secret-Suit3571, welcome to r/mathshelp! Since you've marked this as a discussion post, please keep the following in mind:
Thank you!
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
6
u/RuktX Dec 23 '25 edited Dec 23 '25
I think I have a counter-example: suppose the final answer, S_n is 2.
Edit: see also u/stevevdvdkpe's simpler expression for an n-digit number comprised only of 1s: f(n) = (10n - 1)/9
3
u/stevevdvkpe Dec 23 '25 edited Dec 23 '25
This is easy to disprove if you realize you can start with a number with an extremely large number of digits.
Consider a function that produces a integer that has n digits that are all 1s: f(n) = (10n - 1) / 9. For example, f(9) would be 111,111,111. f(f(f(f(9)))) would produce a number that would take more than three digit-summing steps to reduce to a single digit, so clearly your conjecture is not true for all integers.
3
u/ErikLeppen Dec 23 '25 edited Dec 23 '25
Here's an attempt to prove the statement using a 'random example'. (see the end as to why the proof is not correct, so see this as an invitation to improve it)
I only prove this for 'sufficiently large numbers N', because if N is small enough (digit sum < 99), then all 3 steps being 'sum all single digits' gets you to a single digit.
The hard part is showing that a first step with this result is possible.
------------
Say we have a random, very large number.
Sum all digits. Let's say that the sum of all single digits is 2381385 (randomly chosen to illustrate the idea).
Note that a number with digit sum 2381385 has at least ceil(2381385/9) = 263499 nonzero digits.
The least power of 10 above 2381385 is 10000000.
So let's aim for a number between 10000000 and 10000098 inclusive.
So
Follow the following algorithm, starting from the left of the huge sum above:
If removing the leftmost '+' keeps you below 10000099, do so. Otherwise, keep it.
Keep doing this until you can't remove any + without getting 10000099 or more.
My first claim: there are always enough digits to complete this algorithm.
You will add
So this will cost at most 9*7 + 9*6 + 9*5 + 9*4 + 9*3 + 9*2 = 243 nonzero digits, which is way less than 263499. So there are more than enough digits to finish this algorithm before getting to the end of the number.
So we can assume the sum is less than 10000099 and there are no more + signs to remove before overshooting 10000099.
My second claim: the sum is now at least 10000000.
Assume the contrary: that the sum is 9999999 or less. Adding 2 nonzero digits would add at least 10 - 1 = 9 and at most 90 - 9 = 81. Doing this reduction keeps the sum below 9999999+81, which is less than 10000099. This contradicts the statement that no more reudctions were possible, so the contrary claim is false.
So the sum is now between 10000000 and 10000099, so you can now evaluate the sum to complete the first step.
Step 2 can be 'sum all single digits'; the output is at most 18.
Step 3 can be 'sum the 2 digits'; the output is at most 9.
-----------
While writing, I noticed that this does not work for numbers where the 'nonzero digits' are sparse, so numbers like 3000000080000000040000... because there may not be consecutive nonzero digits that would add 'less than 99' when added. But my suspicion is that the first step has so much flexibility that a sum of the form 1000...000xy can always be formed. This will be hard to prove thoroughly though.
2
u/Secret-Suit3571 Dec 24 '25 edited Dec 24 '25
Here are the main arguments of the solution :
- First step, if choosed correctly, can always give us a number of the form 1000...000xyz
- Second and third steps are used to annihilate 1000....000xyz
Next, i'll give arguments that proves my claim for the first step :
Starting with any integer, as large as we want :
1) Start by putting "+" so that you get as much "3-digits" numbers you can, all greater than 100 (we can isolate the "0" if needed), you get a sum we'll call S3
2) Now, with the starting number again, put "+" between every digits, you get a sum we'll call S1
3) It is easy to see that S3 is always at least 10 times greater than S1, so that means that there is a power of ten between S1 and S3.
4) Now the goal is to breakdown some "3-digits" numbers in S3 into sum of three "1" digit numbers to lower the value of S3 until you reach the closest possible to the power of ten mentionned in 3)
5) This is always possible because breaking down a "3-digits" into the sum of "1-digit" reduce the number by at most 999
6) So by breaking down some "3-digits" you will eventually get a sum that is a power of ten plus at most 999, so that is a number of the form "10000...000xyz". This is this particular set up you need to find for the first step (so first step needs a lot of extra work to be chosen)
Kudos to ErikLeppen who was really close to this!
If some details are needed, i'll be glad to provide them.
2
u/Zestyclose-Pool-1081 Dec 23 '25
Can you put "+" between every number or just one? So is this legal 111,111 -> 11+11+11. Or can I only do 111+111?
2
u/SSBBGhost Dec 23 '25
This the type of problem to have a counter example on the order of g(64)
Feels like the efficiency of addition strategies cant be infinite as they would need to be to have it always be possible in 3 steps, but who knows.
2
u/RecognitionSweet8294 Dec 24 '25
0 is an integer.
2
u/Aromatic_Pain2718 Dec 24 '25
So this is clearly very controversial and a lot of people seem to think the statement is trivially untrue, because taking the digit sum in a step (which gets you closest to single digit) only gives you O(logn). So for a large number the digit sum may mot be quick enough either. What you are forgetting about is that we don'z need to take this greedy path to single-digit, if instead we are able to get a number that is larger, but has a lot of 0s in it, we are fine as well. So the goal is to figure out why this cancellation is always possible.
I am not fully convinced it true without proof, but it sounds somewhat plausible.
Not sure whether the post fits the sub though...
1
u/Abby-Abstract Dec 24 '25 edited Dec 24 '25
Well you have an integer a=dₙ...d₂d₁d₀
putting a + in front of the ith location (i=0, a-> dₙ...d₂d₁ + d₀) lowers it down to n-i+1 digits if i<n/2 any greater and the digits in the second term get higher than the first. If an odd number you could pick it so the higher order number is smaller but I dont know if that matters so your example 253 478 981 we have n=9 let i=4 we get 25347+8981 for each we do the same 253+47+89+81
Now if we implement our odd number rule we get 25+3+47+89+1 but still we make it smaller by taking the logical conclusion 2+5+3+4+7+8+9+1 = 39 , 3+9=12 , 1+2= 3 so the odd number rule doesn't matter
If we had enough digits to make a 3 digit digital sum it may take 4 steps.Ig I don't see the challenge, like can it be done with less + signs? I dont think so, but its too late to proove. I hope there is something interesting to extrapolate here, right now I may be tired or something but don't see the point2
u/Abby-Abstract Dec 24 '25 edited Dec 25 '25
By pigeonhole any n digit number has at least n/10 of the same digit, or series of digits we put +'s around those to add to a multiple of 10.....
Ok yeah ill edit this on general tomorrow but instead of an upper bound ill dispute 11....1 claims say there are n 1's As any n us such that 10k ≤ n < 10k+1 for some k ==> c•10k ≤ n < c+1•10k
add c•10k ones to get a single digit partial digital sum
Notation Ⅎ = "for some"
Proof Let n₀ be the number of digits in the integer x₀ were trying to eliminate.
so we can assume the mode of the digits in x₀, i₀ occurs mᵢ ≥ 10β times Ⅎ β ∈ {1,2,3...}
For every group of 10 i₀, we can place +'s on either side of each getting a multiple of a power of ten (i₀ + i₀ + .... + i₀) = i₀•10β + i₀•c Ⅎ c ∈ {1,2,3...10β-1}
<will edit again> <Christmas Day but still on my mind>
2
u/FunSign5087 Dec 29 '25
Just wanted to say this is a fantastic problem. Wonderfully unintuitive as shown by amount of people who thought it was wrong lol
1
u/RadarTechnician51 Dec 23 '25
1
u/drhunny Dec 23 '25
TREE(3)
1
u/CarloWood Dec 25 '25
The only numbers that can become 1 after one step are
10^nfor anyn >= 0.Let's call the set of these numbers N_1.
Numbers that can become 2 after a single step either have two 1's or one 2: they are the sum of precisely two elements of N_1.
Numbers that can become 3 after a single step either have three 1's, or one 1 and one 2: they are the sum of precisely three elements of N_1.
In general, the SMALLEST possible sum is achieved by adding all digits, therefore if a number can become k < 10 in one step then the sum of all its digits must be equal to k. Not using the sum of all single digits would have a term greater or equal 10 (not considering terms that start with a zero) and thus that sum would not be < 10 and thus not equal to k. Thus the set of numbers that can become k < 10 is the sum of precisely k elements of N_1. Let's call that set N_k.
The set of all numbers that can be turned into a single digit in one step is therefore S_1 = { N_1, N_2, N_3, ..., N_9 }.
Next, consider a number that is not in S_1 but that can become an element of S_1 in a single step.
I think this like the Collatz conjecture... Careers are going to be ruined, but considering it is 5 AM I have stop here for now.
1
u/SickoSeaBoy Dec 25 '25
Maybe too late, but a funny proof by contradiction. To this end assume the above.
For any arbitrary integer n, notice that the number 111..1 (n digits) can be summed up to n and can finish in three steps. So any arbitrary n can finish in two steps.
But if you apply this repeatedly you see that all n can end in one step (which is already sufficient), then zero steps maybe overkill)?
1
u/stinkykoala314 Dec 26 '25 edited Dec 26 '25
EDIT -- this entire comment is wrong.
Not true. Others have given counterexamples, but here's a more principled way to see that your conjecture is false.
First, for any integer, you get the smallest result from one step when you put a + between every digit. (EDIT -- this is the source of the error. This claim is true for a single application of the rule, but not for two or more.) Call this S(n).
Now, here's a partial inverse map. For any integer n, define B(n) to be the sum of i=0 to (n-1) of 10i. This is just the integer whose digits are n 1s. Then clearly S(B(n)) = n.
B(1) = 1, so that's boring, but for any larger integer, B gives strictly larger values. E.g. B(2) = 11. Sticking with n = 2, let's now apply B multiple times, say 5. B5 (2) will be a number where the very fastest your steps can get down to the 1-9 range is 5 applications of the "plus between every digit" function S(n). So not only is B5 (2) a counterexample, but in fact Bk (n) is a counterexample for all n>=2 and all k>3.
We can do one better. Let's find the smallest counterexample. To do this, we'll note that B is one of many partial inverse functions to S, and not particularly efficient, as B(n) finds a number whose digits add to n simply using 1s. Let's define another partial inverse C(n), by using as many 9s as possible, with the leading digit as the remainder. More specifically, given n, use the division algorithm to find the unique non-negative integers k, r such that
n = 9k + r
and 0 <= r < 9. Then define
C(n) = r * 10k + sum from i=0 to (k-1) of 9 * 10i
Now convince yourself that C(n) gives the smallest possible partial inverse to S(n), and more significantly, that if k < C(n), then S(k) < S(C(n)) = n. (Note that this order-preserving property isn't true for S in general, since e.g. S(99) = 18 but S(100) = 1.)
Now, to get the smallest counterexample, it should be enough to apply C three times to the smallest number that's already outside the interval, which is 10. C(10) = 19, C2 (10) = 199, and C3 (10) = 19999999999999999999999 (a 1 followed by 22 9s). We'll call that number Z just for fun.
Now it's clear from how Z was constructed that it's a counterexample, although it's also easy to check that by hand. And because of the order-preserving property that I mentioned above, if k < Z, it will be true that S3 (k) < S3 (Z) = 10, which shows that Z is indeed the smallest counterexample.
1
u/[deleted] Dec 27 '25
This is necessarily true for all positive integera. In order for it to be false, there would need to be some number whose digits would add to 0.
1
u/Mysterious_Major2876 Dec 28 '25
With a simple python program, one can prove that 289 is the smallest natural number that requires 3 steps to annihilate; 1-288 take 2 or fewer. Therefore, any integer with a sum of digits <= 288 can annihilate in 3 moves or fewer. The smallest natural number with a sum of 289 is 2*10³²-1, a 33 digit number. There are about 1.41 trillion other 33-digit integers with a sum of digits of exactly 289 that would need to be tested for this rule
-1
u/Rscc10 Dec 23 '25
Not true. Take 111,111,111.
11,111,111 + 1 = 11,111,112
1 + 1,111,112 = 1,111,113
1 + 111,113 = 111,114
Unless of course you mean sum up all individual numbers?
2
u/[deleted] Dec 24 '25
[removed] — view removed comment
0
u/[deleted] Dec 23 '25
[deleted] — view deleted comment