# Tagged Questions

Questions about properties of, working with and algorithms on integers.

1answer
44 views

### Algorithm to determine if a number is perfect on a Turing Machine

I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it ...
3answers
104 views

### What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
1answer
12 views

### VAR autoincrement with constant space consumption for super large tables

Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs ...
1answer
108 views

### Algorithm to return largest subset of non-intersecting intervals

I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals. i.e. Given a set of intervals $I = \{I_1, I_2, \ldots, I_n\}$ ...
1answer
51 views

### Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

I'm trying to solve exercise 6.5 on page 309 from Richard Crandall's "Prime numbers - A computational perspective". It basically asks for an algorithm to factor integers in randomized polynomial time ...
3answers
114 views

### How to guess the value of $j$ at the end of the loop?

for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ; All variables are integers.(i.e. if decimal values occur, consider their floor value) Let ...
1answer
87 views

### Shifting subset sum solution by constant positive integer

While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the ...
3answers
283 views

### Comparing rational numbers

Given $a,b,c,d \in \mathbb N$ and $b,d \notin \{0\}$, $$\begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*}$$ My questions are: Given $a,b,c,d$ Assuming we can ...
1answer
131 views

### Calculate storage requirements for a data set

I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading. I'm writing a bunch of integers to disk. Lot's of them. Starting ...
1answer
257 views

### Fastest square root method with exact integer result?

I am dealing with the problem of computing $s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, ...
4answers
157 views

### Get specified bit in addition of two large binary numbers

I am performing an addition operation on two large binary numbers that have an equal number of bits. Both numbers are stored in an array of length $N$, which is rather large. At first I tried running ...
3answers
271 views

### Converting function to bitwise only?

I have a function to count upper bits of a 32 bit value. So if a number is 11100011111..., the result is 3 as there are 3 ones in the most significant place before a 0 is hit. I need to convert the ...
1answer
149 views

### How to compute linear recurrence using matrix with fraction coefficients?

What I'm trying to do is generate Motzkin numbers mod a large number $10^{14} + 7$ (not prime), and it needs to compute the $n$th Motzkin number as fast as possible. From Wikipedia, the formula for ...
1answer
70 views

### Run time of product of polynomially bounded numbers

Let $M$ denote a set of $n$ positive integers, each less than $n^c$. What is the runtime of computing $\prod_{m \in M} m$ with a deterministic Turing machine?
2answers
196 views

### Complexity of computing $n^{n^2}$

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?
2answers
363 views

### Algorithm to find optimal currency denominations

Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The ...
2answers
323 views

### Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
4answers
656 views

### Most efficient algorithm to print 1-100 using a given random number generator

We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50. We may use only this random number generator to ...
3answers
229 views

### How can I find minimum number required to add to sequence such that their xor becomes zero

Given a sequence of natural numbers, you can add any natural number to any number in the sequence such that their xor becomes zero. My goal is to minimize the sum of added numbers. Consider the ...
3answers
304 views

### What is the bitwise xor of an interval?

Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval. What is a fast algorithm to find \$\{ k\oplus x\mid x\in ...
2answers
429 views

### Representing Negative and Complex Numbers Using Lambda Calculus

Most tutorials on Lambda Calculus provide example where Positive Integers and Booleans can be represented by Functions. What about -1 and i?
3answers
408 views

### Determine missing number in data stream

We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$. How can I determine the missing number with an algorithm that reads the stream once and uses a memory ...
2answers
120 views

### From FACTOR To KNAPSACK

If there were an algorithm that factored in polynomial time by means of examining each possible factor of a complex number efficiently, could one not also use this algorithm to solve unbounded ...
1answer
822 views

### What is the most efficient way to compute factorials modulo a prime?

Do you know any algorithm that calculates the factorial after modulus efficiently? For example, I want to program: ...
1answer
147 views

### Detecting overflow in summation

Suppose I am given an array of $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$. I want to compute the sum $S = a_1 + \ldots + a_n$ on a machine with 2's ...
1answer
144 views

### Overflow safe summation

Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$. ...
3answers
148 views

### Language of the graph of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ ...
5answers
355 views

### Language of the values of an affine function

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let $a$ and $b$ be integers, with $a > 0$. Consider the language of multiples of $a$ plus a ...
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 42, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8950849175453186, "perplexity_flag": "middle"}