1

I was wondering if there is mathematical formula or a way to get the nth binary number where n is given. Obviously, this is a very easy problem for a programmer and I can construct a program (using loops) to find it but am interested in a mathematical way to obtain it.

To give an example if we assume 0 is the 0th binary number, and 1 is the first, I would like to get 1001 when I ask about the 9th number. Another way to put this is, does a fast way exist to convert decimal numbers into binary.

What about the general case? Does a formula exist that can quickly convert a number from a numerical system in base x to one in base y?

Thank you in advance!

Seraph
  • 51
  • Yeah, you just manually do a for loop. – xxxxxxxxx Nov 13 '20 at 17:03
  • 2
    There is a "divide by two, check remainder" method, e.g. $10\to5\to2\to1$ with remainders $0,1,0,1$, so the binary representation of $10$ is $1010_2$. – player3236 Nov 13 '20 at 17:04
  • Yeah, I have heard about this method. What concerns me is that there is not a concrete number with respect to n as of how much times one should repeat the operation. – Seraph Nov 13 '20 at 17:07
  • 1
    The number of times to repeat the operation is basically $\log_2 n$ – peter.petrov Nov 13 '20 at 17:09
  • Oh, guess I didn't notice that :) thank you! – Seraph Nov 13 '20 at 17:09
  • @AtanasIliev Take the number of (base ten) digits of $n$, and multiply by $3.3$, and you'll have a rough estimate. – Arthur Nov 13 '20 at 17:10
  • Well, if you want a number as the result of your "mathematical formula", it would be $f(n)=n$. If you want the binary representation, i.e. a finite sequence of $0$ and $1$, that would be different. However, it would be a recursive definition, and thus not much different from what a lowly programmer might suggest. –  Nov 13 '20 at 17:53

2 Answers2

0

The $n$-th binary number is just the number $n$ written in the binary number system.
And then... there is a well-known algorithm how to obtain the binary representation of $n$.

But OK... if you mean if there's a formula for the binary digits of $n$, given $n$ itself - no, not a good/easy one at least. So you just need to keep dividing by $2$ (in a loop), and keep collecting the remainders (i.e. the binary digits).

The number of times to repeat the operation (dividing by $2$ and getting the remainder) is basically $\log_2 n$. Because each natural number $n$ has about $log_b\ n$ digits in a number system with base $b$.

peter.petrov
  • 12,568
0

$$\sum_{n=-\infty}^{\lceil\log_{b}\left(x\right)\rceil}\left(\lfloor\frac{x}{b^{n}}\bmod b\rfloor10^{n}\right)$$$x$ is the integer you want to convert, and $b$ is the desired base. Unfortunately, this doesn't work past base 10.

HyperBeast43
  • 3
EL19
  • 1