New answers tagged

1

We have $2017=2^{11}-2^5+2^0$. You want $2017^n\equiv1\bmod2^{11}$. Since $$ 2017^n\equiv\left(2^{11}-2^5+2^0\right)^n\equiv\left(-2^5+2^0\right)^n\equiv1-n\cdot2^5+n(n-1)\cdot2^9\mod2^{11}\;, $$ we need $\left(2^4(n-1)-1\right)n\equiv0\bmod2^6$. Since the first factor is odd, all $6$ factors of $2$ must be in $n$, so this first happens for $n=2^6=64$.


0

I am adding another answer and not adding on to my previous one, as they are different... As an "extension" to the question... what numbers will end with 10 1's in a row written in binary? $a^k$ Where k $\in \mathbb Z, k >0$ and $a \in \mathbb Z, a >0$ The following general equation will return 10 1's in a row written in binary: $((1024 *q)-1)^{2p-...


0

Generalizing this a bit. Assume that the binary representation of an integer $n$ ends with $\ldots011\ldots1$, in other words there are $k$ ones at the end preceded by a $0$. I claim that the $k+1$ last bits in the binary representation of $n^\ell$ behave as follows: if $\ell$ is even we have $\ldots000\ldots01$ - a single one preceded by $k$ zeros, and ...


1

First of all, I would like to start off with saying that this is a very interesting question, and I would like to know what possibly caused you to think about this. This is a "brute-force" method, but it sometimes helps identify patterns. I wrote a simple Java program to find the value of $2015^k$ Where k $\in \mathbb Z, k >0$, convert it to binary, and ...


0

$2015 = (2^{11}-2^5-1)$. You want $n$ such that $2015^n = k2^{10}-1$ for some integer $k$. Working modulo $2^{10}$, this reduces to finding $n$ such that $(-2^5-1)^n \equiv -1 \mod 2^{10}$. $$(-2^5-1)^n = (-1)^n \sum_{k=0}^n \binom{n}{k} 2^{5k} \equiv (-1)^n (n 2^5 + 1) \mod 2^{10}$$ When $n$ is odd we need $n2^5 + 1 \equiv 1 \mod 2^{10}$ which is ...


2

the smallest number ending in 10 1's in binary is $2^{10} - 1$ find $k$ such that: $2015^k \equiv -1 \pmod{2^{10}}\\ 2015\equiv -33 \pmod{2^{10}}\\ (-32-1)^{32} = 1 + 32\cdot 32\cdots \equiv 1 \pmod{1024}\\ 2015^{32}\equiv 1 \pmod{1024}$ Check $k=16$, $(-33)^{16}$ either equals $1, -1$ or something else. If it equals $1$, then we check $k=8$. If it equals ...


2

Here is one way to do it. Generate the list of $N$ numbers $$\lfloor 0.5\rfloor, \lfloor x+0.5\rfloor, \lfloor 2x+0.5\rfloor,\dots,\lfloor (N-1)x+0.5\rfloor,$$ where $\lfloor\cdot\rfloor$ is the greatest integer function. Then “fill” box $k$ when $\lfloor kx+0.5\rfloor>\lfloor (k-1)x+0.5\rfloor$. Note that this is equivalent to drawing the straight line ...


2

Let $p$ be the proportion that you want filled, i.e., $p = \frac{N_{occupied}}N$. Leave the first space empty if $p<1$; otherwise, fill it. Now let $f(k) = \lfloor pk \rfloor - \lfloor p(k-1) \rfloor$ and observe that if $k \in \mathbb Z$, then $f(k) \in \{0,1\}$. Use $f(k)$ as an indicator for filling the spaces for $k>1$; that is, fill the $k$th ...


2

The symmetric group $S_n$ operates on the set of boolean functions that depend on every input by permuting the inputs. Functions are in the same orbit of this operation exactly when you call them equivalent. The equivalence classes have different sizes, what you really want to know is how many of them there are. Generally, the number of orbits of a group ...


1

You can reverse your process for binary integers. I'm using a smaller number as an example: $0.101011_2$ Start from the least significant bit and work towards. $(0+1)\div2=0.5$ $(0.5+1)\div2=0.75$ $(0.75+0)\div2=0.375$ $(0.375+1)\div2=0.6875$ $(0.6875+0)\div2=0.34375$ $(0.34375+1)\div2=0.671875$ EDIT: How it works: $$0.671875=\frac{43}{64}=\frac{1}{64}...


1

In base $10$, $0.392 = \dfrac{392}{10^3}$. Similarly, if you work in base $2$, $0.01011_2 = \dfrac{01011_2}{2^5} = \dfrac{11}{32}$ (if you want your final answer expressed as a fraction using integers in base $10$), if you have a good algorithm for converting integers from base $2$ to base $10$. ADDED after OP clarified he meant a mixed periodic fraction: ...


3

Yes, you can do that. Note that this is not often how it's done in practice, because it depends on doing most of the arithmetic on base-ten representations, which is awkward and slow on most computer architectures. Instead one might, for example, start by multiplying by an appropriate power of ten (corresponding to how many decimals after the point you ...


1

Binary is another way of expressing numbers, but the numbers available are the same as decimal. Sometimes it can make informal proofs easier because there is a pattern in the digits or it can make patterns that interest us which we later prove. An example in base $10$ is $$7^2=49\\67^2=4489\\667^2=444889\\6667^2=44448889$$ This would not be so interesting ...


1

Many other theorems can be proved this way, or insight gained into them. For example in the Collatz conjecture every odd number leading directly to an odd number of the form $x01$ is a member of the set $\{x01, x0101, x010101,...\}$. The proof of Fermat's last theorem uses p-adic number system, which are numbers arranged in prime bases, of which base 2 is ...


1

The four bit two's complement representation of $-4$ is $1100$, which you get by bit complementing $0100$ to get $1011$ then adding one to get $1100$. You are correct that in three bit two's complement notation $100$ is $-4$ decimal. You will get proper truncation any time the high order bits are the same down to the first bit you keep, as is the case here....


1

You are correct, either they truncated from a signed number to an unsigned number or they forgot a minus sign.


1

A binary matrix contains a permutation matrix (in the sense illustrated by your example) if and only if its permanent is non-zero. The permanent can be computed in $O(2^nn)$ time.


2

Take for instance the number $2132$ (base $4$). I can convert it to base $10$ the following way: $2*4^3 + 1*4^2 + 3*4^1 + 2*4^0 = 158$ So that means $2132$ (base $4$) = $158$ (base $10$). Now what if I want to convert the same number, $2132$ (base $4$) to base $6$? Why can't I do the same method? Example: $2*4^3 + 1*4^2 + 3*4^1 + 2*4^0 = ...


1

You got the number to decimal, which is good. Now just take it into base $6$. $6^3 = 216$ is greater than $158$ so we need just three digits. $6^2 \times 4$ is $144$, leaving $14$. $6 \times 2$ is $12$, leaving $2$, and we're done: $$2132_4 = 158_{10} = 422_6.$$ Now, if you wanted to work in base $6$, you could, but then you're just converting each ...


2

I think each single digit in base 4 corresponds to 2 digits in base 2 (possibly 0-filled): $$(1123)_4 = (\underbrace{01}_1 \underbrace{01}_1 \underbrace{10}_2 \underbrace{11}_3)_2$$ One usually omits leading zeroes in the final result, so you have $(1011011)_2$.


1

there is a method to calculate decimal places of root2, probably that could help find a pattern with it. Although this is not a very obvious one, it probably could (very loosely) help to find a pattern. The method works a bit like dividing, so you have to calculate the next decimal place, then the next. It does not work on approximations by the way. http://...


0

For a bijection, each element of X must be paired with at least one element of Y, and each element of Y must be paired with at least one element of X, $M(\underline{a}) $ always maps to an element in the other partition no element of X may be paired with more than one element of Y, and no element of Y may be paired with more than one element of X. $M(...


1

A simple search turns up this: https://en.wikipedia.org/wiki/Offset_binary To quote: "Offset binary,[1] also referred to as excess-K,[1] excess-N, excess code or biased representation, is a digital coding scheme where all-zero corresponds to the minimal negative value and all-one to the maximal positive value. There is no standard for offset binary, but ...



Top 50 recent answers are included