# What is the largest positive integer such that each digit is at least the sum of all the digits to its left?

What is the largest positive integer such that each digit is at least the sum of all the digits to its left?

Can someone point me in the right direction with this problem? Don't give me the answer, please. I don't know where to start, the wording confuses me.

• Do all the digits have to be non-zero? Otherwise, I can create arbitrarily large numbers that satisfy the condition. – Johanna Dec 27 '14 at 20:26
• I'm sorry, I have no idea. – John Dec 27 '14 at 20:31
• @Johanna how is it possible to get arbitrarily large integers satisfying the given condition? – Jacob Dec 27 '14 at 20:33
• Start with the fact that the leftmost non-zero digit must be at least $1$. Then see how many digits you can cram into such a number. After you play around with this for a bit, it will be easy to prove that you can't have more than 5 non-zero digits. – JimmyK4542 Dec 27 '14 at 20:34
• @Johanna but $0<1$ – Edward Jiang Dec 27 '14 at 20:34

The largest such number is

$11259$

(i) If the first digit were $\ge 2$, we could profitably replace it by $11$. So the first digit is $1$.

(ii) If the second digit were $\ge 2$, then the next two digits would be at least $3$ and $6$, ruling out a 5-digit number.

(iii) If the third digit were $\ge 3$, then the next digit would be at least $5$, ruling out a 5-digit number.

A 6-digit number is clearly impossible: minimum digits are $11248$. So $11259$ is the best we can do.

• ‘Don't give me the answer, please.’ – Brian M. Scott Dec 27 '14 at 22:29
• @Brian: Yes, but just look at the other two answers -- they are worthless. This question is impossible to answer in the abstract. – TonyK Dec 27 '14 at 22:43
• I don’t agree that Jacob’s answer is worthless. And you could perfectly well have offered your (i) and then suggested that the OP try to extend the same kind of reasoning to complete the solution. Or even your (i) and (ii), if you thought (i) alone too obscure. – Brian M. Scott Dec 27 '14 at 22:48

The left most digit has to be 1,the smallest possible, because you want to have a number with maximum possible length, so the smallest possible for the next position has to be a 1 again because having a 2 you get a number with lesser digits.. Continue to play with digits to get a number whose slight modification will give you the result..

Assume that all the digits have to be non-zero. Start working backwards. You know that the last digit has to be $9$, right? Now you want a number with as many digits as possible, that add up to at most $9$. So you start with a $1$. Then what is the smallest thing that the second digit can be? The third? and so on, until the sum of the digits is at least $9$. Then the number terminates. (Hint, consider the Fibonacci sequence).

• The Fibonacci sequence is not involved in this problem. – Edward Jiang Dec 27 '14 at 20:49
• @EdwardJiang It gives a first estimate for the first digits. They can then be adjusted up slightly to give the final answer. – Johanna Dec 27 '14 at 20:51
• Yes, but don't you think it would be more beneficial to say "powers of 2" rather than "Fibonacci numbers"? In any case, I'm not arguing with you. I'm just saying it might mislead the OP. – Edward Jiang Dec 27 '14 at 20:53
• @Edward: I agree -- Fibonacci numbers are irrelevant here, even as a hint. – TonyK Dec 27 '14 at 20:59
• @EdwardJiang Using the powers of $2$ will give a shorter string than using the Fibbonacci numbers. – Johanna Dec 27 '14 at 21:12