# Questions tagged [number-theory]

number theory is the branch of mathematics concerning the mathematical properties of numbers and the relationships between various types of numbers. This tag should be used with questions regarding computer science topics which are presented from a number theory perspective or may involve number theory or whose answer could be or should be couched in number theory terms.

190 questions
Filter by
Sorted by
Tagged with
38 views

### Quick calculation for $x^y \bmod 2^d$

I need to calculate $x^y \bmod 2^d$ in $O(d)$ summations/bitwise operations and $1$ multiplication by $y$. $x$ is restricted to be odd, $d\geq 3$. $a$-bit arithmetic (for any $a$) is allowed, as this ...
35 views
+200

### Branch and scope globally unique identifiers

Say we are working with a Prolog-like system where variables are dynamically created in different branch contexts and scopes, yet these variables are also globally viewable by the system regardless of ...
17 views

### Array manipulation and number theory [closed]

How do I rearrange a given array such that the GCD of all the adjacent elements is always 1?
21 views

### Prove that x and y in extended Euclid's algorithm won't overflow an Integer (If a,b <= 1e8, ax+by=gcd(a,b))

We are given a and b <= 1e8. The extended Euclid's algorithm always finds a solution for ax+by=gcd(a,b) (assuming it exists) which can always be stored in an Int. How to prove the x and y won't ...
38 views

### Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5) [closed]

I want to prove, $a^2+b^2=c^2$,there exists only 1 case such that a,b,c are consecutive non-negative integers(3,4,5). I have no clue to prove this lemma. Please help me to prove this lemma.
81 views

### Given $n=pq=a^2+b^2$, can we factor $n$?

Just to be clear, $a$ and $b$ are known, while $p$ and $q$ are unknown prime numbers, both congruent to $1$ modulo $4$. Can we design an efficient algorithm to retrieve $p$ and $q$? It is a known ...
50 views

### Guess the number from its different base representations

Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or ...
95 views

### How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an ...
30 views

### Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
23 views

46 views

### I want to find the number of steps it takes to find the GCD by Euclidean Algorithm

Let's say I have two numbers a and b. I want to find the number of steps it takes to find the GCD by Euclidean Algorithm by a closed formula which includes parameter a and b. If I go by this ...
31 views

### Coprimes satisfying a pair

We know that number of coprimes less than a number can be found using Euler's totient function. But if there are two numbers $p$ and $q$ and we need to find number of numbers less than $q$ ...
125 views

### How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
38 views

### Running time complexity of finding maximal power of divisor that divides natural number

Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
60 views

### Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences

Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea ...
66 views

### Bertrand's ballot theorem

I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem. it is this If i number of people voted for A and j number of people voted ...
134 views

### Carpet into Box

Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or ...
27 views

152 views

### Randomly Choosing a N-Bit Prime

I've been studying some number theory, and I came across this problem: Lagrange’s prime number theorem states that as N increases, the number of primes less than $N$ is $Θ(N/ log(N))$. ...
31 views

### How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...
16 views

### Base-k representations of polynomials: state of art [closed]

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ ...
35 views

### Two's complement max with a different base

Working with fixed size integer representations, use a number system with b-complement notation, base b = 9 and n = 4 digits. What is the smallest number that can be represented in this number system?...
70 views

### Determining number of elements divisible by at least one prime of set

I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the ...
85 views

75 views

### Count numbers less than $x$ co-prime to $p$

We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$. I know that we can solve the problem in $O(x\log x)$ with iterating over all ...
157 views

### Which is the fastest method for calculating exact square root of a integer of 200-500 digit number?

I wanted to know is there any algorithm / function / process through which I can calculate square root of a very large integer number. I wants to know current state of the research in this field. No ...
107 views

### What is the most compact (space efficient) method of storing an array of distinct integers?

I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must ...
102 views

### Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
35 views

### How hexadecimal representation is more compact and intelligible for documentation?

My textbook says, "Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as ...
38 views

### Level sums, displacements: how to determine their effect efficiently?

Let $R =\mathbb{Z}/N \mathbb{Z}$. Let $f:R\to \mathbb{R}$, $\rho:R\to \lbrack 0,1\rbrack$. We assume that it takes trivial time to compute any given value $f(m)$ or $\rho(m)$. Define S(\delta,m) = ...
218 views

### Testing algorithm for a modified sieve of Eratosthenes

Context: I am looking at a modified version of the sieve of Eratosthenes. I started by generalising Eratosthenes' sieve, like so: Choose some starting "root", $n_0\in\mathbb{N}$, a sieve limit (the ...
### Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular
We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can ...