Skip to main content

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
1 vote
1 answer
58 views

Generate Max Number of Sequences Separated by Hamming Distance of 3

I'm interested in whether there is an algorithm for generating the maximum possible number of DNA sequences that are $7$ nucleotides long that differ by at least $3$...
Reed Trende's user avatar
4 votes
1 answer
75 views

Efficient computation of number of partitions into powers of 2

Consider the function $a(n)$ defined as the number of partitions of $n$ into powers of $2$. The sequence is given at OEIS. I am trying to calculate $a(n)$ modulo some fixed prime, for large $n$ and ...
user2784016's user avatar
-2 votes
1 answer
48 views

Generate set of numbers containing 3 consecutive 1, but without the elements of the previous set [closed]

So I have this specific problem that I couldn't figure out. I want to create a set $F_n$ containing all bitstrings that has 3 consecutive 1s, but not those that are already contained in all the ...
Kim Dong's user avatar
  • 713
1 vote
2 answers
59 views

Sierpinski Gasket coordinate description

I was reading Gerald Edgar's "Measure, Topology, and Fractal Geometry" when I came across this exercise Let coordinates $(u,v)$ be defined in the plane with origin at one corner of the ...
Rubén Sales Castellar's user avatar
1 vote
1 answer
101 views

On $(0,1)$-strings and counting

Consider a binary string of length $n$ that starts with a $1$ and ends in a $0$. Clearly there are $2^{n-2}$ such bit strings. I would like to condition these sequences by insisting that the number of ...
T. Amdeberhan's user avatar
3 votes
2 answers
114 views

high school math: summands

Let's say we have a question that asks you to find the amount of all possible integers adding up to a random number, lets just say 1287. However, the possible integers is restricted to explicitly 1's ...
jackhammer's user avatar
0 votes
0 answers
25 views

Gray code permutation notation

I 'm trying to understand the notation of the Gray code permutation but since I only know 2-row matrix notation for permutations, I would like an explanation for the notations below . I understand the ...
user159729's user avatar
3 votes
3 answers
498 views

2009th smallest number in base 10 whose binary representation contains even number of 1's

HMMT 2009 Problem 20 : A positive integer is called Jubilant if the number of 1’s in its binary representation is even. For example, $6=110_2$ is a Jubilant number. What is the $2009$th smallest ...
Aashita's user avatar
  • 69
0 votes
0 answers
38 views

Converting a Quartic Term into Quadratic Form in QUBO for Prime Factorization

I'm trying to embed the prime factorization problem into the form of a QUBO. To do so, let $p$ and $q$ be two real positive numbers. We can represent these two numbers as binary numbers, which itself ...
Amirhossein Rezaei's user avatar
13 votes
2 answers
528 views

Counting ones in binary representation: When is the product multiplicative?

Question: For $n \in \mathbb{Z}^+$, define $Z(n)$ to be the number of ones in the binary expression of $n$. For fixed positive integer $a$, how does one describe the set of $b$ such that $Z(ab) = Z(a)...
Benjamin Dickman's user avatar
0 votes
1 answer
25 views

Binary combination - find individual parts from sum

Lets say we are having 4 "N" bit values, and in each of them there is exactly 1 10-bit pattern of "1000000001" somewhere (x can be 0 or 1, and it will be exactly N-10) - ...
Dave's user avatar
  • 13
0 votes
0 answers
32 views

Binary combinations with special criteria

Let there be a binary value of "n" bits which consists of only "0"s and "1"s. If we pick exactly "r" "1"s of them (and the rest "n-r" are &...
Dave's user avatar
  • 13
0 votes
1 answer
28 views

Binary combinations - rank and unrank [closed]

Let's consider a binary value of "n" bits (which consists of only "0"s and "1"s). We want to pick exactly "r" "1"s of them (and the rest "n-r&...
Dave's user avatar
  • 13
-1 votes
1 answer
39 views

calculate the terms of a function using base 2, number theory

I have the following problem from the book Teoria dos Numeros:um passeio com primos e outros numeros familiares pelo mundo inteiro. Let $f : \mathbb{N} >0 → \mathbb{N}$ be a defined function of the ...
amkpm90's user avatar
  • 352
1 vote
0 answers
37 views

Binary subset rank and unrank [closed]

Let there be N=5 bits. We want to rank and un-rank a specific subset of bits based on the following criteria - ...
Dave's user avatar
  • 13
2 votes
0 answers
48 views

The number of $1$-s in the binary form of $10^k$ is always more than $k$ when $k>87$?

I originally guessed that it's correct for all natural number $k$ - I verified the case when $k\le 11$ by myself. Then I asked for a proof in another website. Some users there found $4$ counter-...
yummy's user avatar
  • 358
4 votes
2 answers
319 views

Finding a sequence of tangent circles with integer radii

I asked this over in the puzzling SE and it has since been solved there. The question is best asked with a visual: I am looking to find a sequence (of any length) of strictly decreasing (strictly ...
Brandan's user avatar
  • 124
0 votes
0 answers
15 views

Find a generating subset of a set of binary vectors such that the number of even sums of generators in the set is minimised.

More precisely: Let $S\in \mathbb{F}_2^n$ be a set of $n$-dimensional binary vectors, find a generating subset $G\subseteq S$ such that the number of elements of $S$ expressible as a sum of an even ...
DeafIdiotGod's user avatar
0 votes
3 answers
116 views

Functions or formulas for Base-10 to Base-n (1<n<10)

Trying to find an answer to this question I was able to find a formula for the conversion of decimal numbers to their binary representations in Base-10 $D(x)$: $$ D(x) = C_0 $$ $$ C_o = (C_{o+1} \cdot ...
PageSteiner's user avatar
8 votes
1 answer
337 views

Binary digital sum (Hamming weight) of Arithmetic Progression

Context I was recently going through the Putnam 2023 problems and the topic of this post is question $\text{B2}$ from there. For each positive integer $n$, let $k(n)$ be the number of ones in the ...
Soham Saha's user avatar
  • 1,392
4 votes
2 answers
308 views

Find the number of pairs of two consecutive zeros

the problem We call a binary sequence of length $n$ a string with $n$ digits of $0$ or $1$. For such a sequence, $A$, of finite length,$f(A)$ represents a transformation where every 1 in $A$ becomes $...
IONELA BUCIU's user avatar
2 votes
1 answer
125 views

Solve $10^k\equiv 2^k\pmod{2^{k+1}}$ & $10^j+10^k\equiv 2^j+2^k\pmod{2^{k+1}}.\,$ Binary digits ends with its decimal digits (with at most two 1's)

Find all positive integers $n$ such that the binary representation of $n$ ends with its decimal digits and contains at most two 1's in its decimal representation. Here is my current approach: $$ n_{...
SpungLung's user avatar
2 votes
0 answers
86 views

Is there a name for this set-theoretical definition of natural numbers, or has it been invented?

I'll call it the binary encoding with sets. I think it's nice and trivial, should have been discovered by many genius brains, but i can't find it by searching with efforts. Prior arts are Zermelo's ...
Farter Yang's user avatar
0 votes
0 answers
16 views

$A(n,d)$ ... set of all binary codes $C$ of length $n$ with $\delta(C)=d$ and $M(n,d)$ ... maximum cardinality of $|C|$ over all $C \in A(n,d)$

Let $A(n,d)$ denote the set of all binary codes $C$ of length $n$ with $\delta(C)=d$. Define $M(n,d)$ as the maximum cardinality of $|C|$ over all $C \in A(n,d)$. Prove the following: (a) $M(n,2d-1) \...
user avatar
0 votes
0 answers
31 views

Number of binary solutions to an underdetermined linear system

I don't know if the answer to the following question is trivial, to me it's not. Suppose that X is an $m\times n$ matrix, with $n>m$, and assume it is a realization from some continuous ...
Asaf's user avatar
  • 1
2 votes
2 answers
147 views

Can someone please explain the below and if it means that if x=m/2^n and if m is odd then x can be represented in binary in two ways?

Reference image containing the statement Can someone please explain the below text and what it means in simple words? From what I understood it means that if x=m/2^n and if m is odd then x can be ...
さまVipul's user avatar
1 vote
1 answer
64 views

Faster methods for finding binary reciprocals by hand

Are there any faster methods than long division for finding the binary expansion of a reciprocal by hand? I've noticed some patterns, such as $\frac{1}{2^n-1} = 0.\overline{[n - 1\text{ 0s}]1}$ and $\...
LostXOR's user avatar
  • 111
0 votes
0 answers
21 views

Proving that the language Lq = {x.y : x and y are binary strings and [x.y]2 ≤ q} is not regular if q is irrational

I have this assignment on finite automatas and tried to solve it but I have a question on the string s to use for the pumping lemma. I have the intuition that for q = square root of 2, I might want to ...
BonelessAnt's user avatar
2 votes
2 answers
142 views

Why do k arithmetic right/left bit shifts divide by $2^k$/multiply by $2^k$ in two's complement, rigorously?

I want to understand the semantics of rights bit shifts x>>k in two's complement properly, in particular why do right bit shifts of size $k$ approximately ...
Charlie Parker's user avatar
0 votes
0 answers
25 views

How one can calculate $s_2(p)$

Let us define the integer $p$ as follow: $$p= \sum_{i=1}^{m}(2^{k+2})^{i}-r2^{k+2}-2w+1+3a$$ How one can calculate $s_2(p)$ the sum of binary digits of $p$. Here all the arguments are integers.
Safwane's user avatar
  • 3,854
-1 votes
1 answer
62 views

Count the number of binary representations that have the given number of occurrences. [closed]

How many binary representation exists that each has five "00", three "01", three "10" and three "11" in it ?!
FrOZEn_FurY's user avatar
1 vote
1 answer
77 views

Error Propagation in calculating Binary logarithm by hand

I am interested in the idea of arithmetic performed in binary done without electronics. In particular, I’d like to try calculating the binary logarithm of x (where 10 > x >= 1) using the square/...
MMLgamer's user avatar
1 vote
0 answers
81 views

what math concept would this be called?

Assume that I am trying to use reference values to evaluate an analysis of an unknown sample in order to determine what the nature of the sample is and the attribute value is an 8-bit string of binary ...
Sam Levi's user avatar
4 votes
1 answer
81 views

Does $\exists\ n$ such that the first $2n$ digits of Thue Morse, $X_{2n},$ is the concatenated sequence $X_n X_n?$ If not then why not?

Background: The Thue–Morse sequence is the binary sequence (an infinite sequence of $0$s and $1$s) obtained by starting with $0$ and successively appending the Boolean complement of the sequence ...
Adam Rubinson's user avatar
2 votes
3 answers
82 views

Is there a measure on $\mathbb{Z}$ giving integers independent binary digits?

An integer $x\in\mathbb{Z}$ can be identified with its binary expansion, $x = \ldots b_3 b_2 b_1b_0$ where $b_i \in \{0,1\}$ for each $i\geq 0$ and $b_i = 0$ for all sufficiently large $i$. Fixing a ...
Rob's user avatar
  • 7,252
2 votes
1 answer
72 views

Number of orderings of a binary tree such that parent comes before children

I am currently making a research project on ILP based optimal unpacking of CHs and can not figure out a specific question. To compare my approach, I would like to know the total amount of possible ...
Florian Bauer's user avatar
0 votes
0 answers
10 views

Dummy variable with multiple criteria - how to

Dummy variable is simple when it is true or false. What happens if the 'true' has multiple criteria that needs to be met? For example, there are 4 criteria in total. And 3 out of 4 must be true for ...
MLux's user avatar
  • 1
0 votes
0 answers
25 views

Fair Bandwidth Allocation

This is a question that sounds simple but I can't figure out a proper solution. The question is as follows. Say you have a binary tree of 3 levels(8 leaves). Let's say this represents a network where ...
oshan yalegama's user avatar
0 votes
2 answers
208 views

Number of 8-bit binary strings with at least two consecutive 0’s or two consecutive 1’s?

Saw this question while going through Combinatorics, here's my understanding: For an 8-bit string, $2^8 = 256$ combinations are possible. Out of these, only two: ...
Manan's user avatar
  • 103
2 votes
0 answers
56 views

Can there be a Nim j, k which generalizes Nim k?

In Nim, players must remove objects from exactly $1$ heap, and the winning strategy involves converting all heap sizes to base $2$, and removing objects to manipulate to $0$ the digital sum in base $2$...
user10478's user avatar
  • 1,922
2 votes
3 answers
123 views

Is there a general formula for the AND and OR bitwise operators?

The bitwise operators AND and OR work as follows: "a AND b" is true if both A and B are true, and "a OR b" is false if both A and B are false. However, you can also preform these ...
The_Animator's user avatar
4 votes
1 answer
256 views

How can I win Moore's Nim k?

Nim is a game where there are several heaps of pebbles. Players take turns selecting a heap, then removing any nonzero number of pebbles from that heap. Whoever takes the last pebble wins. In Nim, the ...
user10478's user avatar
  • 1,922
3 votes
1 answer
145 views

Do the normal numbers form a Borel set?

Normal numbers have a 'random' expansion. For example, in base 10 it means that all digits $0,1,\dots,9$ occur 'equally often' in its decimal expansion. A longstanding open problem is: is $\pi$ a ...
Riemann's user avatar
  • 727
0 votes
0 answers
10 views

Number of elementary binary operations (EBO's) required for Long multiplication in binary

How do they get the total of $≤2kl$ EBOs? Shouldn't it require $kl+k(l-1)=2kl-k$ EBOs? And where does the upper bounding "$≤$" come from?
Holland Davis's user avatar
0 votes
0 answers
32 views

The number of bits of a product of two decimal numbers

Theorem. Let us have two numbers $m,n\in\mathbb Z^+$ with $k$ and $l$ bits respectively where $k≥l$. Then $m\cdot n$ has either $k+l-1$ or $k+l$ bits. Proof. Trivially follows from exponent rules. $$2^...
Holland Davis's user avatar
1 vote
1 answer
47 views

Help understanding the solution to this problem

Here is the problem: There are sixteen different ways of writing four-digit strings using 1s and Os. Three of these strings are 1010, 0100 and 1001. These three can be found as substrings of 101001. ...
mathisdagoat's user avatar
1 vote
1 answer
68 views

Vector specifying the number of $1$’s in the binary representations of $1,...,k$

For a fixed integer $k$, I am interested in a closed-form expression for the vector $\textbf{a}$, where $\textbf{a}[i]$ is the number of integers in $\{1,...,k\}$ that have $i$ $1$’s in their binary ...
Sander's user avatar
  • 383
3 votes
2 answers
87 views

Proof that $\frac 1{10}$ has no finite binary float representation

I am supposed to prove that $\frac 1{10}$ is not representable as a finite binary float. I tried proving this via induction but that did not seem to work, now I am out of ideas. Thank you
trapaholicsmixtapes's user avatar
5 votes
2 answers
229 views

Why does $(1 + x)(1 + x^2)(1 + x^4)(1+x^8) \cdots = 1 + x + x^2 + x^3 + \cdots$?

Is there an intuitive explanation as to why $$(1 + x)(1 + x^2)(1 + x^4)(1+x^8) \cdots = 1 + x + x^2 + x^3 + \cdots$$ for $ |{x}| < 1?$ Of course, we can show that each side of the equation is equal ...
cherrytree's user avatar
1 vote
0 answers
198 views

Finding two' s complement of a fractional binary number

I want to find out 2's complement of binary number (00101101.1100) To find the 2's complement of a binary number, invert all bits (change 0s to 1s and 1s to 0s) and then add 1 to the result. For the ...
Dinesh Katoch's user avatar

1
2 3 4 5
35