Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given number of digits required, $x$, find an $x$-digit number such that $f(1) = 1$, $f(2) = 12$, $f(3) = 123$, $f(4) = 1,234$, and so forth.

I'm banging my head against the wall trying to logically figure out what kind of formula would give such results. I'm using this for a web app I'm developing, and I'd rather find a formula than use a for or while loop.

Can anybody help? Thanks!

P.S.: Not sure if this will help, but so far I've got this:

$$f(n) = \displaystyle\sum_{i=0}^{n-1} 10^i(n-i)$$

But is there a formula that I could easily use in code (basic algebra, so summation notation)?

share|improve this question
    
What should the value of $f(10)$ be? One could always use the Champernowne constant, multiply by an appropriate power of ten, and truncate accordingly... –  J. M. Apr 14 '12 at 4:04
    
Sorry... The problem says something about "find an $x$-digit number", and then takes a function $f$. But what does $f$ have to do with the putative $x$-digit number, and what does the $x$-digit number have to satisfy? –  Arturo Magidin Apr 14 '12 at 4:05
1  
There's a closed form of the formula you gave: Wolphram|Alpha: $$ \displaystyle\sum_{i=0}^{n-1} 10^i(n-i) = \frac{1}{81}(-10 - 9n + 10^{n+1}).$$ –  user2468 Apr 14 '12 at 4:24
1  
@ArturoMagidin my bet is that OP is confused about terminology, and probably meant "finding a formula for the number $12\cdots n$ where $0<n<10$." –  user2468 Apr 14 '12 at 4:25
1  
If $f$ only has domain $\{1,2,\ldots,9\}$, using a formula to compute $f$ is extremely wasteful. Just store the $9$ values of $f$. It's much easier. –  Raskolnikov Apr 14 '12 at 6:08

5 Answers 5

up vote 2 down vote accepted

Hint: Do you know how to sum an arithmetic geometric series?

You want to sum up $f(n)=\sum_{i=0}^{n-1}10^i(n-i) $.

Now $10f(n)=\sum_{i=0}^{n-1}10^{i+1}(n-i)= \sum_{i=1}^{n} 10^{i}(n-i+1)$. Subtracting, $9f(n)=-n+ \sum_{i=1}^{n-1} 10^i + 10^n = -n+\frac{10}{9}(10^{n-1} -1) + 10^n$. So, $f(n)=\frac{1}{81}(10^{n+1}-9n-10)$

share|improve this answer
    
I'm a math amateur... I'm sure I knew how to do so at one time, but I'm struggling to see how arithmetic/geometric series sums would help here. –  TerranRich Apr 14 '12 at 4:18
    
$f(n)=\sum_{i=0}^{n-1}10^i(n-i)$ is the sum of an arithmetic geometric series. –  Shitikanth Apr 14 '12 at 4:53
    
Yep, that's what I added to my original post awhile ago. I got that far, but wanted a non-summation method of doing it. I instead used a fixed array, since this was for a programming project. –  TerranRich Apr 14 '12 at 5:46
    
Well I am not suggesting you actually sum up the series. There is an easy way to sum up series like these and I expected that you would know it. I am updating my answer to include what i meant. –  Shitikanth Apr 14 '12 at 5:53
    
Ohh, I get it now. See, I didn't know how to get from the summation formula to the closed form. Thank you for your help! –  TerranRich Apr 14 '12 at 6:10

Given a finite number of values, you can always compute a polynomial using Lagrange Interpolation that will take precisely those values at those points. That is, given $n+1$ distinct points $a_0,a_1,\ldots,a_n$ and $n$ values $b_0,\ldots,b_n$ (not necessarily distincct), Lagrange Interpolation will product a polynomial $p(x)$ of degree at most $n$ such that $p(a_i) = b_i$ for $i=0,\ldots,n$.

You could do this here with $a_0=1$, $a_1=2,\ldots,a_8=9$, and $b_0=1$, $b_1=12,\ldots,b_8=123456789$, which will give you a polynomial of degree at most $8$ with the desired values.

Note that (i) such a polynomial is not the only "possible" function, though it will be the only polynomial of degree at most $n$ with those values; and (ii) it may result in "surprising" values for other points. For example, if you use Lagrange Interpolation to find a polynomial $p(x)$ such that $p(0)=1$, $p(1)=2$, $p(2)=4$, $p(3)=8$, and $p(4)=16$, (so that $f(x)=2^x$ gives you a function with those values), the polynomial you find will give $p(5)=31$.

share|improve this answer

Do you want the Champernowne constant, $0.12345678910111213\ldots $? Generally a number doesn't give a function. If I give you $x=2158384378923$ what is $f(1)$? In your case, what is $f(13)$-you have not specified what happens with carries?

share|improve this answer
    
Sorry, I should have specified, the number of digits only goes up to 9. –  TerranRich Apr 14 '12 at 4:10
    
@TerranRich: If you have a finite domain, you can just list the function. The first sentence of J.D.'s comment does exactly that. What more do you need? In computer code, you can just make an array of the values and use the input as the index. That will be faster. –  Ross Millikan Apr 14 '12 at 4:14
    
I suppose you're right about using a fixed array (1 => 1, 2 => 12, 3 => 123, etc.). I guess I tend to over-complicate things by figuring out a "trick" or something I can use to avoid doing something simple like that. :) –  TerranRich Apr 14 '12 at 4:19

$f(n) = \displaystyle \sum_{i=1}^n 10^{i-1}(n-i+1)$

or

$f(n) = \displaystyle \sum_{i=1}^n 10^{n-i}i$

share|improve this answer
    
$$\dfrac{10^{n+1}-9n-10}{81}$$ is way simpler... –  J. M. Apr 14 '12 at 6:03
    
Yes. You are right. But, the calculation of the expression is difficult for n≥3. –  Prasad G Apr 14 '12 at 6:23

The formula to get what you want is:

sum{i=1 to n} i*10^{n-i} , using wolfram alpha , give the result below:

f(n) = (10^(n+1) - 9*n - 10) / 81

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.