2
$\begingroup$

Consider a three dimensional discrete coordinate system $(x,y,z)$, where $x,y,z\in$ natural numbers.

The number of digits describing an integer coordinate for each dimension is $l_c=\lfloor log(c) \rfloor+1$, where $c$ is $x$, $y$ or $z$.

The total number of digits describing a point in the space is $l=\lfloor log(x) \rfloor+\lfloor log(y) \rfloor+\lfloor log(z) \rfloor+3$.

I am looking for a formula to describe how many points each total coordinate digit length can describe.

Any suggestions?

Example:

As one digit for each dimension can describe a total of $(10)(10)(10)$ points, the total coordinate length $3$ can describe a total of $10^3$ points in the space.

Two digits for any of the dimensions and one digit for the rest gives a total number of points possible to describe as $(3)(10^2-10)(10)(10)$. In other words, a total of four digits can describe a maximum of $27000$ points in the space.

A total of five coordinate digits can describe a maximum of $$(3)(10^3-10^2)(10)(10)+(3)(10^2-10)^2(10)=513000$$ points in the space.

Six digits can describe a total number of $$(3)(10^4-10^3)(10)(10)+(6)(10^3-10^2)(10^2-10)(10)+(10^2-10)^3=8289000$$ points in the space.

And so on.

Any suggestions on how to produce a formula are greatly appreciated.

$\endgroup$
2
$\begingroup$

OPs approach is fine and in fact the examples already present all possible different variants of the number of digits $k_1,k_2,k_3$ of the three dimensions with $k_1+k_2+k_3=n$ digits.

  • All three dimensions are equal: $\qquad\qquad\ k_1=k_2=k_3$

  • Two are equal, the third is different: $\qquad\ k_1=k_2, k_1\ne k_3$

  • All three are pairwise different: $\qquad\qquad\; k_1\ne k_2, k_1\ne k_3, k_2\ne k_3$

As there are some different cases to distinguish we conveniently use Iverson brackets.

Let $n\ge 3$. We start with \begin{align*} \sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} &\left\{\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3[[k_1=k_2=k_3]]\right.\tag{1}\\ &\qquad+3\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad\qquad\cdot[[k_1=k_2,k_1\ne k_3]]\\ &\qquad+3\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\tag{2}\\ &\qquad\qquad\cdot[[k_1\ne k_2,k_2= k_3]]\\ &\qquad\left.+6\prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)[[k_1\ne k_2,k_1\ne k_3,k_2\ne k_3]]\right\}\tag{3} \end{align*}

We can simplify the three summands (1), (2) and (3) somewhat.

Case 1: All three dimensions are equal

We obtain \begin{align*} \sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}}&\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3[[k_1=k_2=k_3]]\\ &=\sum_{{1\leq k_1= k_2= k_3\leq n}\atop{k_1+k_2+k_3=n}}\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^3\\ &\,\,\color{blue}{=\left(10^{\frac{n}{3}}-10^{\frac{n}{3}-1}[[n>3]]\right)^3[[3|n]]}\tag{4} \end{align*}

Since $k_1=k_2=k_3$ we have only one case to consider, namely $3k_1=n$ resp. $k_1=\left\lfloor\frac{n}{3}\right\rfloor$. This implies that $n$ has to be a multiple of $3$ which is asserted by $[[3|n]]$, otherwise the sum is zero.

Case 2: Two are equal, the third is different

We obtain \begin{align*} &3\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad\qquad\cdot[[k_1=k_2,k_1\ne k_3]]\\ &\qquad+3\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\\ &\qquad\qquad\qquad\cdot[[k_1\ne k_2,k_2= k_3]]\\ &\quad=3\sum_{{1\leq k_1= k_2< k_3\leq n}\atop{2k_1+k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)\\ &\qquad+3\sum_{{1\leq k_1< k_2= k_3\leq n}\atop{k_1+2k_3=n}} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_3}-10^{k_3-1}[[k_3>1]]\right)^2\\ &\quad\,\,\color{blue}{=3\sum_{k_1=1}^{\left\lfloor\frac{n-1}{3}\right\rfloor} \left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)^2\left(10^{n-2k_1}-10^{n-2k_1-1}\right)}\\ &\qquad\,\,\color{blue}{+3\sum_{k_3=\left\lceil\frac{n+1}{3}\right\rceil}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \left(10^{n-2k_3}-10^{n-2k_3-1}[[n-2k_3>1]]\right)\left(10^{k_3}-10^{k_3-1}\right)^2}\tag{5} \end{align*}

The upper limit $\left\lfloor\frac{n-1}{3}\right\rfloor$ of the left-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1=k_2<k_3\leq n\\ &2k_1+k_3=n\qquad\qquad\qquad\to\qquad k_3=n-2k_1>k_1\qquad\to\qquad k_1<\frac{n}{3}\\ \end{align*}

The lower limit $\left\lceil\frac{n+1}{3}\right\rceil$ of the right-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1<k_2=k_3\leq n\\ &k_1+2k_3=n\qquad\qquad\qquad\to\qquad k_1=n-2k_3<k_3\qquad\to\qquad k_3>\frac{n}{3}\\ \end{align*}

The upper limit $\left\lfloor\frac{n-1}{2}\right\rfloor$ of the right-hand sum in (5) follows from the index region \begin{align*} &1\leq k_1<k_2=k_3\leq n\\ &k_1+2k_3=n\qquad\qquad\qquad\to\qquad n-2k_3\geq 1\qquad\to\qquad k_3\leq \frac{n-1}{2}\\ \end{align*}

Case 3: All three are pairwise different

We obtain \begin{align*} &6\sum_{{1\leq k_1\leq k_2\leq k_3\leq n}\atop{k_1+k_2+k_3=n}} \prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)[[k_1\ne k_2,k_1\ne k_3,k_2\ne k_3]]\\ &\qquad=6\sum_{{1\leq k_1< k_2< k_3\leq n}\atop{k_1+k_2+k_3=n}} \prod_{j=1}^3\left(10^{k_j}-10^{k_j-1}[[k_j>1]]\right)\\ &\qquad\,\,\color{blue}{=6\sum_{k_1=1}^{n-2}\sum_{k_2=k_1+1}^{\left\lfloor\frac{n-k_1-1}{2}\right\rfloor}\left(10^{k_1}-10^{k_1-1}[[k_1>1]]\right)\left(10^{k_2}-10^{k_2-1}\right)}\\ &\qquad\qquad\qquad\qquad\qquad\color{blue}{\cdot\left(10^{n-k_1-k_2}-10^{n-k_1-k_2-1}\right)}\tag{6} \end{align*}

Putting (4) - (6) together gives a simplified formula of (1) - (3).

The upper limit $\left\lfloor\frac{n-k_1-1}{2}\right\rfloor$ of the sum in (6) follows from the index region \begin{align*} &1\leq k_1< k_2< k_3\leq n\\ &k_1+k_2+k_3=n\qquad\qquad\to\qquad k_3=n-k_1-k_2>k_2\qquad\to\qquad k_2<\frac{n-k_1}{2}\\ \end{align*}

$\endgroup$
  • $\begingroup$ Very nice answer. Many thanks. However, when entering (6) for n=6 into WolframAlpha (link) it gives a funny answer (49680000). Do you think there might be a way to express the sums without Iverson brackets? Kind regards $\endgroup$ – ijaubgiaugf Dec 1 '19 at 13:52
  • 1
    $\begingroup$ @ijaubgiaugf: You're welcome. Thanks for pointing at the mistake. I've revised and corrected the answer accordingly. A nice aspect is the number of Iverson brackets could be reduced. In order to completely avoid the Iverson brackets we would have to write the different cases $k_1=1$ and $k_1>1$ separately. $\endgroup$ – Markus Scheuer Dec 1 '19 at 18:17
  • 1
    $\begingroup$ @ijaubgiaugf: Fixed and hopefully corrected. Review is welcome. $\endgroup$ – Markus Scheuer Dec 1 '19 at 22:05
  • 1
    $\begingroup$ @ijaubgiaugf: You're welcome. Good to see that it works fine now. :-) $\endgroup$ – Markus Scheuer Dec 2 '19 at 19:40
  • 1
    $\begingroup$ @ijaubgiaugf: I don't think that it is difficult. But it is presumably somewhat more cumbersome to derive a formula. $\endgroup$ – Markus Scheuer Dec 5 '19 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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