I don't think I can put this into a formula (I'll reply back if I can come up with a simple one), but the way I would solve a problem like this is to just think it through.
Let's take $10$ as an example. Here are all the possible combinations of single digit, positive integers that add up to $10$:
- $1, 9$
- $2, 8$
- $3, 7$
- $4, 6$
- $5, 5$
Remember that each set of digits could be joined in two ways to make two numbers, so all of the possible two digit numbers are as follows:
- $1, 9 \Rightarrow 19, 91$
- $2, 8 \Rightarrow 28, 82$
- $3, 7 \Rightarrow 37, 73$
- $4, 6 \Rightarrow 46, 64$
- $5, 5 \Rightarrow 55$
Technically, we could list many more numbers of 3-10 digits (i.e. 127, 523), but if we have two digit possibilities, then there's no reason to check three digits and up since we're looking for the smallest number.
From the list of numbers above, you can see that $19$ is the smallest. However, we could have found this without exhausting all of the two digit options. Unfortunately, I am suggesting a guess-and-check method, but a strategical/informed version. In this case, we check if 1 could be a possible first digit, since we're looking for the smallest possible number. $10-1 = 9$, so $19$ is a valid result and we can not find a smaller answer (since there is no one-digit number that would equal $10$ and there are no other two digit numbers in the 10s that would add up to $10$.
Now, let me take 16 to show you the proper approach. You don't just want to start with $16-1$ and then $16-2$ since these return a two-digit number ($1+15 = 16$, etc.), so you want to make an informed guess to try and find the lowest pair of single digit numbers that add up to $16$. Since $6+10 = 16$, anything $\le 6$ would have a two-digit partner, so we try $7$ and find that $7+9 = 16$, so $79$ is our smallest value that adds up to 16.
Let's do another example that is $< 20$: $15$. Since $5+10 = 15$, try $6$ since this should be the first with another single digit (since you're technically adding $1$ to $5$ and subtracting $1$ from $10$, so you find $6$ and $9$, or $69$.
Once you get to $19$, it's not possible to find a two-digit answer that adds up to $20$, so we need to move up to 3 digits. Try using $1$ as the first digit (this only works for $19$ by the way, just like it only worked for $10$ for 2 digits), so $19-1 = 18$ and now we need to find two one digits that will add up to $18$, which is $9+9$, so $1+9+9 = 19$, so our answer is $199$.
One-digit answers will only get you as far as $9$,
Two-digit answers will only get you as far as $9+9=18$,
Three-digits will only go up to $9+9+9=27$,
and so on.
Sorry there isn't a formula that I can think of to solve this quickly, but with some informed tries, you should be able to find the answer rather quickly.
Best Answer
I am not answering the question but the post asks for clues so here it is a couple of ideas.
If $a_0,a_1,a_2, \cdots , a_{477} $ are the decimal digits of $3^{1000}$ then the numbers $$b_i=a_{6i}+a_{6i+1}\cdot 10+a_{6i+2}\cdot 10^2+a_{6i+3}\cdot 10^3+a_{6i+4}\cdot 10^4+a_{6i+5}\cdot 10^5$$ for $i=0,1,2,\cdots, 79$ are the digits of $3^{1000}$ in base $10^6$ ($80$ is the nearest integer above $477 \div 6$ so there are $80$ digits numbered $0,1,2,\cdots,79$)
In other words: $$ 3^{1000} = b_0 + b_1 \cdot 10^6+ \cdots + b_{79} \cdot (10^6)^{79}$$
Now, if we resort to modular arithmetic we see that $$ 3^0=1, 3^1=3 , 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 $$ (all the equalities taken modulo $7$).
Also $$3^{1000}=(3^6)^{166}\cdot 3^4= 1 \cdot 4 = 4$$(all the equalities taken modulo $7$).
Now if we note that $10^6=1$ (modulo 7) the expression of $3^{1000}$ in base $10^6$ reads (modulo 7) $$ 4=b_0+b_1+ \cdots +b_{79}$$
So we can assert that the sum of digits of $3^{1000}$ in base one milion gives a remainder of $4$ when divided by $7$.
Another partial result comes from the decimal expansion read modulo 7:
$$3^{1000}= a_0+ a_1 \cdot 10 + \cdots +a_{477} \cdot 10^{477} =1 = a_0+3 a_1+ 2a_2 + 6 a_3 + 4 a_4 + 5 a_ 5 + \cdots $$
So, given that $a_0=1$ we can say that this particular linear combination of the remaining digits is divisible by $7$.