1
$\begingroup$

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)?

  • 0
    Raskolnikov: That's what I ended up doing in my code. But I still want to give credit to J.D. for his closed form of the summation formula I had in my original post, since it technically answered my question.2012-04-14

5 Answers 5

2

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)$

  • 0
    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!2012-04-14
1

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$.

0

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?

  • 0
    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. :)2012-04-14
0

$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$

  • 0
    Yes. You are right. But, the calculation of the expression is difficult for n≥3.2019-02-26
0

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