Questions tagged [binary]
Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.
1,670
questions
-2
votes
0
answers
45
views
Need help on developing a algorithm for encoding a color with less than 24 bits.
The RGB encoding uses 3 8-bit numbers to encode any color , however I suspect that we may need even less than 24 bits.Here are my thoughts so far.The first number will tell the GCD of the values of ...
- 23
1
vote
1
answer
49
views
Confused about this proof of how set of finite binary strings is countable
I am reading a proof that the set of all binary strings is countable- it justifies this by mapping each binary string to the natural number it represents in binary. However, I am not seeing how this ...
- 1,597
0
votes
0
answers
72
views
Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
- 9
1
vote
1
answer
323
views
How to find the amount of binary sequences with at least one "0" in the middle of 2 "1"?
This is a sub problem that I found while trying to solve one question from the programming marathon (please don't give me the direct solution for that. I am having fun solving these sub problems)
If ...
4
votes
2
answers
106
views
Number of ways to write integers in balanced binary
Imagine a method of writing integers which is similar to balanced ternary, except as you write more digits, their value increases by a factor of 2, not 3. For the remainder of the post, I will call ...
- 160
2
votes
1
answer
49
views
Closed form or formula for the $n$-th binary number with m-bits that has at most k ones
Like the title suggests, I need the $n$-th number, not the number of numbers that answer that criterion.
For example, for $m=4$ and $k=2$ the formula should equal $0,1,2,3,4,5,6,8,9,10,12$ as $n$ ...
- 51
1
vote
1
answer
39
views
The number of binary digits is less than the value
I want a proof that the number of binary digits is less than the value. There is a log relationship $$base_{digits} = \log_2(value) + 1.$$ I can't seem to prove $base_{digits}<value$. Or perhaps ...
3
votes
0
answers
63
views
a lower bound for the number of $1$ in the binary representation of divisors of $2^n+1$
This year there was a question in the third round of the Iranian math olympiad:
if $a,b$ are two natural numbers such that $ab=2^n+1$ and $a,b$ has $l,m$ 1 in their binary representation prove that $...
- 2,095
5
votes
2
answers
408
views
Similarities in the digits of the powers of 2 and 5
Many may have noticed that the negative powers of 5 contain the same digits as the positive powers of 2:
This pattern intrigued me. I started to wonder if it exists in different number bases. I soon ...
- 87
5
votes
2
answers
166
views
Possible connection between prime numbers in binary and $\pi$
I just realized I asked a question with a very similar title a while back. This is not a duplicate. It is another conjecture though.
Conjecture: $\lim\limits_{x\to\infty}\mu \{ f(2), f(3), f(5), ... ,...
- 391
1
vote
1
answer
104
views
How does this algorithm for the Van der Corput sequence work?
For any natural number $n$ write its binary expansion as $n = \sum_{i=0}^{k(n)} n_i 2^i$. Then the $n$th entry of the binary Van der Corput sequence is defined to be the dyadic rational
$$V(n) = \sum_{...
- 33.9k
2
votes
1
answer
90
views
Binary sequence that follows constraints
Suppose I have a binary string of length $n$ with the only permissible characters $0$ and $1$. The string is supposed to follow the constraint that adjacent to every character must be a $0$, either to ...
3
votes
0
answers
57
views
Sums of powers of integers with a fixed number of binary transitions
The number of transitions in a binary sequence is the number of times the sequence switches from $0$ to $1$ or vice versa. For example, the sequence $00000000$ has $0$ transitions and the sequence $...
- 181
2
votes
2
answers
54
views
How do you split a binary number into two halves, excluding one of the digits? [closed]
I have the number 110111001 (441). I want to extract three numbers from it:
110100000 (416)
000010000 (16)
000001001 (9)
Is ...
- 33
0
votes
2
answers
37
views
Confused about how to find de Bruijn sequence from Eulerian tour
I am not following how wikipedia constructs a de Bruijn sequence from an Eulerian tour here. When our Eulerian tour visits vertices $000,000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101,...
- 1,597
1
vote
1
answer
46
views
Binary strings of length $3n$ such that for every $(c_1, c_2, c_3)$, there is $k \in [n]$ such that: $(c_1, c_2, c_3) = (a_{3k-2}, a_{3k-1}, a_{3k})$
Find the formula (can be in the form of a sum) expressing, for a fixed natural number $n \geq 1$, the number of all binary strings $(a_1, . . . , a_{3n})$ of length $3n$ such that for every ordered ...
- 1,047
3
votes
1
answer
85
views
Loops in a binary iterated function system
Take a function $f(x)$ which operates on numbers written in binary. It is a three step operation:
Split the number into digits in even- and odd-numbered places. (For example, the number $\underline{1}...
5
votes
1
answer
86
views
Strongly connected? Binary numbers of length n with bounded hamming weight
I am wondering if the following is true, and if yes how to prove it:
Construct a graph where the vertices are binary numbers of length $n$ and have a hamming weight (i.e. digit sum) between $a$ and $b$...
- 53
0
votes
1
answer
43
views
Occurrence of only 0, 2, 8, a, c in a sequence of hexadecimal representation of binary classification of prime numbers.
I recently began experimenting with prime numbers and made a quite interesting discovery. I stored 1 if a number is prime and 0 if the number is composite as shown in the table below.
15
14
13
12
11
...
- 3
3
votes
0
answers
39
views
Sufficient criterion for a binary string to have dense orbit
I was recently asked the following question: Does the map $$\mu : [0, 1) \rightarrow [0, 1)\\ \hspace{105px}x \hspace{5px}\rightarrow \hspace{5px}2x \mod 1$$
have some point, say $\alpha$, whose ...
- 96
0
votes
0
answers
21
views
Specialized algorithms for edge cases of binary arithmetic
I have several mathematical operations on binary numbers that are special cases of more general arithmetic operations. I am wondering whether there exist more specialized algorithms purpose-made for ...
1
vote
1
answer
43
views
Normalised binary exponential form
I am doing some mathematics, and I am currently stuck on something. I do not understand this part at all, expressing the result in normalized binary exponential form, the book also mentions ...
- 199
0
votes
0
answers
56
views
Decomposing binary matrices
Given a $2n \times 2n$ binary symplectic matrix$^1$ $M$, I need to decompose that into a product of matrices from the following set S. It is guaranteed that multiple such decompositions exist.
$S = \{ ...
- 97
1
vote
0
answers
32
views
Proportion of a digit in an algebraic number's binary expansion
We know that
A real number is rational if and only if it's binary (or base $n$ expansion, for all $n$) is eventually periodic. Therefore, the proportion of each digit (0 or 1 in the binary case) is a ...
- 7,061
0
votes
0
answers
49
views
Enumerate all possible binary numbers with fixed amount of 1 in ascending order
I'm quite stuck on finding a formula for computing the ordinal number for a binary number with fixed amount of 1 and fixed size (i.e. digits in total).
Let's say I'...
- 101
0
votes
0
answers
29
views
Logic function for $c=a-b$ where $a,b \in [0,31]$.
I need to create a switching function that performs the subtraction $c=a-b$ where $a,b \in [0,31]$.
Now, my workbook has realized $c=a+b, a,b \in [0,15]$ using two functions (each with three arguments)...
- 893
0
votes
2
answers
81
views
How can we argue that any binary number plus $1$ is a binary number?
I am working with the definition of a binary number $n$ to be $$
n=c_k \cdot 2^k+c_{k-1} \cdot 2^{k-1}+\cdots+c_1 \cdot 2^1+c_0 \cdot 2^0
$$
where $k \in \mathbb{N}$ and $c_i \in\{0,1\}$ for all $i \...
- 1,597
-1
votes
1
answer
46
views
How to concatenate binary numbers without using their decimal values? For example 3 and 4 -> 34
This question describes exactly what I need to do!
I am also doing this using electronic circuitry. The problem is, that the answer (which has been marked as a 'solution') only works for those two ...
1
vote
1
answer
50
views
Binary expansions of $\frac{1}{2}$
I was reading Elements of Set Theory by Herbert B. Enderton, and I saw there is written:
$$0.1000...=0.0111...=\frac{1}{2}$$
I don't understand how $0.0111...$ is a binary expansion of $\frac{1}{2}$. ...
- 149
0
votes
0
answers
21
views
How to handle the position of the decimal separator in the (binary) representation of a real number - Rudin $2.14$ - Cantor diagonal argument
Cantor diagonal argument's array seems to be with only numbers $\in [0,1]$, but Rudin (Principles of Mathematical Analysis, $2.14$), if I understood well, uses the argument with an array of numbers $\...
- 969
0
votes
0
answers
51
views
number of n length binary strings not containing specific factor [SOLVED]. [duplicate]
EDIT:
Thanks to RobPratt's insight, (https://oeis.org/A005251), I wrote a quick and dirty python program to generate the number of bin strings not containing a 3 length string;
...
- 1
2
votes
0
answers
56
views
A question on binary system.
Suppose there are $n$ zero's and $n$ one's. And you have arrange it in a $2n$ digit binary sequence such that if you took first $k$ numbers from starting then sum of digits of this $k$ digit numbers ...
- 467
1
vote
1
answer
134
views
Algorithm for Starting Nonograms
I'll readily admit that this likely isn't the right place to put this, but I figured it'd be most interesting to this community in particular. I noticed this pattern because of my background in ...
- 11
2
votes
2
answers
96
views
Is there a non-negative integer x that is not a palindrome but for which x == reverse_digits(x) due to an overflow?
I recently started solving some problems on LeetCode where I came across a question that asks to write a function that checks whether a non-negative integer x is a ...
- 175
1
vote
2
answers
67
views
Is there a reason that the binary byte sequence $2^{10n}$ and decimal byte sequence $10^{3n}$ are so closely related?
Computer storage is measured in decimal (base 10) or binary (base 2) notations of bytes.
IMB Spectrum - Data Storage Values
Series
Name
Symbol
Value (base-10)
Name
Symbol
Value (base-2)
kilo
K
$10^{...
5
votes
0
answers
278
views
Squaring the output of a frequency-time space conversion map
Let $\xi \in \{0, 1\}^n$ be a vector included into $\mathbb C^n$, and use $\mathcal F : \mathbb C^n \to \mathbb C^n$ to be any natural frequency-time space conversion map.
What can we say about
$$\...
- 607
1
vote
0
answers
66
views
A question regarding the construction of binary sequences
Suppose we want to find all binary sequences with a length $K$ that contain $N$ ones. We know that the number of such sequences is $P = K$ choose $N$.
As an example, for $K=4,N=2$ we get the following ...
1
vote
0
answers
120
views
Number of guesses binary search would take to reach number
Essentially, given a start of an inclusive integer range $s$, an end of the range $f$ such that $s \le f$, and an integer $n$ such that $s \le n \le f$, how many guesses would binary search take to ...
- 240
0
votes
0
answers
53
views
crc table lookup not giving the same result as basic implementation
The basic implementation of CRC uses XOR and left-shift operations to find the remainder. While the index of the leftmost bit of the remainder is greater than the degree of the generator polynomial, ...
- 13
3
votes
2
answers
154
views
How do I find the nth number that has two 1's in its binary representation?
I'm trying to find the a closed-form equation for the nth number that has exactly two 1's in its binary representation. The first few numbers are 3, 5, 6, 9, 10, 12, 17, 18, and so on.
My first ...
- 179
0
votes
1
answer
28
views
How to do $-(1100.1)_2 - (1.010)_2$ using 1's complement
Convert $A = (12.5)_{10}$ and $B= (1.45)_{16}$ into binary format employing 6 bits for the integer part and 3 for the fractional part, including the sign bit. Perform $- A - B$ using 1's complement
...
- 751
3
votes
2
answers
366
views
Division of binary numbers, confusing
I am trying my best to divide the following:
Perform the following computations in binary arithmetic (Show how you perform
the computations):
My attempt:
I watched:
https://www.youtube.com/watch?v=...
- 199
2
votes
1
answer
124
views
HMMT 2014 #9, how many times has Lucky performed the procedure when there are 20 tails-up coins?
There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero
point of the number line facing in the positive direction. Lucky performs the following procedure: ...
- 2,003
1
vote
0
answers
29
views
Doubt on complexity of multiplying two binary numbers.
In one of my lectures, it was stated that when we multiply two binary numbers (say $n$ and $m$) such that $n$ has $k$ bits and $m$ has $l$ bits we have a maximum of $kl$ bit operations.
I don't ...
- 1,474
1
vote
0
answers
45
views
If a binary number is greater or equal than another one, does it have the same or more number of digits?
This question came up to my mind while dealing with complexity of binary operations, speciffically with multiplication.
The question. Let's say we have two binary numbers $n$ and $m$, such that $n \...
- 1,474
1
vote
0
answers
27
views
Proof of convergence of binary gradient-projected stochastic gradient descent
I have an algorithm that I like to call stochastic binary projected-gradient descent, which looks like:
$$
W_{k+1}=\Pi\left(W_k-\alpha_k \Pi\left(\nabla_{W_k} E\left(W_k\right)\right)
\right)$$
where $...
- 752
7
votes
0
answers
117
views
Number of flips on a binary string to get m consecutive 1s
I am thinking about a deceptively simple problem, at least for my admittedly poor statistics standard.
A $k$ long binary string of all $0$s is given.
A random element is chosen, and flipped.
What is ...
- 2,538
2
votes
1
answer
102
views
Possible connection between binary numbers and $\pi$
Here is the Desmos if you want to follow along: https://www.desmos.com/calculator/b4vtzruupm
In messing around with binary numbers, I created a function $f(x)$ in Desmos that generated a list of ...
- 391
1
vote
1
answer
74
views
Prove that the sets $s_i := \{1\leq j \leq m: (i-1)\odot j = 1\}$ form a $\dfrac{1024}{2047}$-good subset of $T_{2047}$ of size $2048$.
Let $m$ be a positive integer, and let $T_m$ denote the set of all subsets of $\{1,\cdots, m\}$. Call a subset $S$ of $T$ $\delta$-good if for all $s_1, s_2\in S, s_1\neq s_2, |\Delta (s_1, s_2)| \ge \...
- 2,003
0
votes
0
answers
12
views
Binary Differencial Evolution Algorithm
I have a optimization problem at hand and I am using Evolution Algorithm to solve it. Problem looks like following:
max f(x), where x is a vector with 4 elements ...
- 125