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
    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...2012-04-14
  • 0
    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?2012-04-14
  • 0
    Well I use $f$ to represent the function I'm looking for. So $f(5) = 12,345$ would mean the function that takes `5` as the input, and outputs `12345`. I may have worded it wrong. I should have said, "output an $x$-digit number such that...". Also, I only intend to use this up to 9 digits ($f(9) = 123,456,789$).2012-04-14
  • 0
    TerranRich, let me explain further to you. We have $f(1) = 1,$ $f(2) = 12,$ $f(3) = 123,$ $f(4) = 1234,$ $f(5) = 12345,$ $f(6) = 123456,$ $f(7) = 1234567,$ $f(8) = 12345678,$ $f(9) = 12345679.$ Now, the question is: what do you expect for $f(10)$? Do you expect $f(10) = 012345678910$ and $f(11) = 01234567891011$?2012-04-14
  • 0
    Ops. I missed your last comment. So $f$ has the domain: $\{0, 1, \ldots, 9\}.$2012-04-14
  • 0
    The thing is, I don't know. I'm not planning on going beyond $x=9$. I'm sorry if that's not much help. Maybe there isn't a simple formula that does this? (Actually, $f$ would have the domain **{1, 2, ..., 9}**).2012-04-14
  • 0
    @Terran: What I don't understand is: the statement asks you to find a **number**, you seem to be trying to find a **function**. And what do you mean by "finding a function"? You can define a function by specifying what its values are. You don't need a formula that you plug the input into. If you simply **say** that $f$ is given by $f(1)=1$, $f(2)=12,\ldots,f(9)=123456789$, then you **have** given the function. If you are just "looking for a function" that does that, the description above *gives* such a function.2012-04-14
  • 2
    There's a closed form of the formula you gave: [Wolphram|Alpha](http://www.wolframalpha.com/input/?i=sum+10%5Ei+*+%28n+-+i%29+from+i+%3D0+to+n-1): $$ \displaystyle\sum_{i=0}^{n-1} 10^i(n-i) = \frac{1}{81}(-10 - 9n + 10^{n+1}).$$2012-04-14
  • 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."2012-04-14
  • 0
    That's it, J.D.! That's exactly what I was looking for! I didn't realize it was called a "closed form" of the summation formula I already had. And, yes, I got my terminology mixed up, Arturo. I was looking for a **formula**, not a function. Sorry about the confusion! J.D.: Could you give that formula as an official answer, so I can give you credit?2012-04-14
  • 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.2012-04-14
  • 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
    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.2012-04-14
  • 0
    $f(n)=\sum_{i=0}^{n-1}10^i(n-i)$ is the sum of an arithmetic geometric series.2012-04-14
  • 0
    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.2012-04-14
  • 0
    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.2012-04-14
  • 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
    Sorry, I should have specified, the number of digits only goes up to 9.2012-04-14
  • 0
    @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.2012-04-14
  • 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
    $$\dfrac{10^{n+1}-9n-10}{81}$$ is way simpler...2012-04-14
  • 0
    Yes. You are right. But, the calculation of the expression is difficult for n≥3.2012-04-14
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