1
$\begingroup$

I'm looking for a formula that produces numbers in base-$8$ of length $k$, that contain no $0$'s, except for the most significant digit. All numbers are padded with leading zeros. For example, with $k = 1$ we have $\lbrace 0,1,2,3,4,5,6,7\rbrace$. For $k=2$, we skip $00$ and have $\lbrace 01,02,\ldots,07,(\text{skip }10),11,12,\dots,17,(\text{skip }20), 21,\ldots, 75, 76,77\rbrace$. For $k=3$, we skip $000$ through $010$, so the first element in this set is $011$, and proceed as above for the remaining values through $077$, then (skipping $100$ through $110$) on to $111$, $112$, etc., all the way to $777$.

With such a formula I would be able to have a function like f($k$, $a$, $b$) that outputs all such numbers of length $k$ in the decimal range ($a$,$b$). Is such a formula possible?

$\endgroup$
  • $\begingroup$ I've extended your example to make it a little bit clearer what (I think) you're after; if this doesn't match your goal then please feel free to re-edit. $\endgroup$ – Steven Stadnicki Jun 2 '13 at 17:00
  • $\begingroup$ Functions don't "output" things. Do you want a function from $\mathbb N$ to $\mathcal P(\mathbb N)$? If so, you've already defined it! $\endgroup$ – dfeuer Jun 2 '13 at 18:31
1
$\begingroup$

You want $k$ base-$8$ digits of which the first is allowed to be anything and the others must be $1$ to $7$. For any choice of the first digit there are $7^{k-1}$ choices for the others. If you want an explicit "formula" to generate these: note that the $m$'th base-$b$ digit from the end of positive integer $x$ is $$f(b,m,x) = \lfloor x/b^{m-1} \rfloor \mod b$$
So consider $$F(x) = \lfloor x/7^k \rfloor 8^k + \sum_{m=0}^{k-1} ((\lfloor x/7^m \rfloor \mod 7)+1) 8^m$$ which will enumerate your desired numbers for $x$ from $0$ to $8 \times 7^{k-1} - 1$.

$\endgroup$
  • $\begingroup$ Thank you, Robert: f[x_, k_] := Floor[x/7^k]*8^k + Sum[(Mod[Floor[x/7^m], 7] + 1)*8^m, {m, 0, k - 1}]; For[lst = {}; i = 0, i < 100, i++, AppendTo[lst, {f[i, 1], BaseForm[f[i, 1], 8]}]; ]; lst EDIT: did I get that right? I get 1033 -> 2011 $\endgroup$ – jnthn Jun 2 '13 at 20:30
  • $\begingroup$ Nevermind. I still had k=1 when I tried 1033. Works perfectly. $\endgroup$ – jnthn Jun 2 '13 at 20:40
4
$\begingroup$

It looks from the examples that you allow one leading $0$, but no more than that, and no non-leading $0$'s. There are $8$ choices for the lead "digit," and for each such choice there are $7^{k-1}$ ways to choose the rest, for a total of $8\cdot 7^{k-1}$.

$\endgroup$
  • $\begingroup$ Yes, the leading zero is allowed, but nowhere else. I'm hoping for an answer like f(k,a,b) -> all such non-zero base-8 numbers in range a to b of length k, but maybe that isn't possible. $\endgroup$ – jnthn Jun 2 '13 at 17:20
  • $\begingroup$ There is nothing that sounds impossible here. However, your description of what you are after is incomplete. It looked as if you were looking for a count. But perhaps you are recoding integers from $0$ to ?? by using codewords of length $k$, where the codewords are restricted as in your post. Or perhaps you are looking for something else. You will get answers that best fit your needs by making what you need very clear. It may require another question. $\endgroup$ – André Nicolas Jun 2 '13 at 17:32
  • $\begingroup$ Sorry. I thought "produce numbers" was clear. I'll edit. P.S. I up-voted your answer. $\endgroup$ – jnthn Jun 2 '13 at 17:46
2
$\begingroup$

Let $i$ iterate from $1$ to $k$, and generate all strings of length $i$ from $\{1,\ldots,7\}$, and then append 0s at the beginning. There will be $7+7^2+\cdots+7^k=\frac{7^{k+1}-7}{6}$ such strings.

$\endgroup$
  • $\begingroup$ This doesn't quite meet OP's original request that there be at most one leading 0, I think. $\endgroup$ – Steven Stadnicki Jun 2 '13 at 17:02
  • $\begingroup$ @Steven Ah right. Well I'll leave it as it is and let Andre's answer be more on task. $\endgroup$ – alex.jordan Jun 2 '13 at 17:04

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.