Questions tagged [binary]

Questions related with (base 2) representation of numbers and their unique properties arising out of number representation.

Filter by
Sorted by
Tagged with
-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 ...
Cerise's user avatar
  • 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 ...
Shmuel's user avatar
  • 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 ...
Dave's user avatar
  • 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 ...
Rafael Guasselli's user avatar
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 ...
Iron filings's user avatar
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$ ...
Yair Derry's user avatar
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 ...
Harry Alvarado's user avatar
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 $...
ali's user avatar
  • 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 ...
Etienne's user avatar
  • 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), ... ,...
Dylan Levine's user avatar
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_{...
Calvin Khor's user avatar
  • 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 ...
Sahaj Satish Sharma's user avatar
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 $...
Mikhail Hogrefe's user avatar
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 ...
Blackhole927's user avatar
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,...
Shmuel's user avatar
  • 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 ...
thefool's user avatar
  • 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}...
Elliott Price's user avatar
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$...
Rio Joy's user avatar
  • 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 ...
Ivan's user avatar
  • 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 ...
CCC's user avatar
  • 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 ...
Kevin Stefanov's user avatar
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 ...
Alix Blaine's user avatar
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 = \{ ...
FDGod's user avatar
  • 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 ...
Ma Joad's user avatar
  • 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'...
jmizv's user avatar
  • 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)...
john doe's user avatar
  • 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 \...
Shmuel's user avatar
  • 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 ...
TheMatrixAgent22's user avatar
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}$. ...
4bolfazl's user avatar
  • 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 $\...
niobium's user avatar
  • 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; ...
noha's user avatar
  • 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 ...
Chesx's user avatar
  • 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 ...
raspberrychi's user avatar
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 ...
Alex R's user avatar
  • 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^{...
AuthorizedUser's user avatar
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 $$\...
Snared's user avatar
  • 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 ...
Shlomi Bouscher's user avatar
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 ...
Gigi Bayte 2's user avatar
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, ...
Sun864's user avatar
  • 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 ...
Timmy Diehl's user avatar
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 ...
user20194358's user avatar
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=...
Alix Blaine's user avatar
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: ...
user33096's user avatar
  • 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 ...
xyz's user avatar
  • 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 \...
xyz's user avatar
  • 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 $...
Tolga Birdal's user avatar
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 ...
An aedonist's user avatar
  • 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 ...
Dylan Levine's user avatar
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 \...
user33096's user avatar
  • 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 ...
oakca's user avatar
  • 125

1
2 3 4 5
34