Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-2
votes
0answers
33 views

What is the probability of two integers having identical values? [on hold]

There are two sets of 32 bit unsigned integer. Each set has 4000 numbers. Two sets could either be identical or they can different values. All 4000 numbers from each set are added and then the ...
2
votes
2answers
41 views

Algorithm for generate all solutions to a linear Diophantine equation

Consider the linear Diophantine equation of the form: $$\sum_{i=1}^{k}a_ix_i=n.$$ My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I ...
1
vote
1answer
39 views

Modular exponentiation in P

I need to prove that the following language is in $\mathsf{P}$: $$ L = \{\langle x,y,z,d \rangle : xˆy \equiv z \pmod{d}\}.$$ I'm assuming I just have to prove with an algorithm or negate that it's ...
2
votes
0answers
18 views

Is finding a sum of two squares representation for a number computationally assymptotically equivalent to integer factorization?

I have been wondering this question because given a number $n$ with prime factors of the form $4k+3$ when we square $n$ and find a sum of two squares which should reveal these types of factors (as ...
1
vote
1answer
87 views

Checking Divisibility Using Minimal Bits

Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$. a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log ...
1
vote
2answers
103 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))$. ...
1
vote
1answer
27 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 ...
3
votes
0answers
14 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}$ ...
1
vote
1answer
27 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?...
1
vote
3answers
62 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 ...
2
votes
1answer
57 views

How to estimate the average time complexity of greatest common divisor?

As we know, the time complexity of $\gcd(x,y)$ is $O(\log \min(x,y))$ by using Euclidean algorithm. Now we fix a constant $n$ and consider the average time complexity of $\gcd(x,n)$. Formally, let $f(...
0
votes
1answer
23 views

Maximum trailing zeros of the path

Problems: A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, ...
3
votes
2answers
65 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 ...
4
votes
2answers
110 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 ...
0
votes
1answer
68 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 ...
4
votes
0answers
68 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-...
0
votes
1answer
28 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 ...
6
votes
0answers
33 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) = ...
6
votes
0answers
155 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 ...
4
votes
2answers
80 views

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 ...
-2
votes
1answer
51 views

Symmetric difference of a set with an empty set [closed]

The definition of symmetric difference of two sets $\alpha $ and $\beta$, $\alpha \oplus \beta$ is defined as the set of all $x$ such that, $x \in (\alpha \cup \beta) - (\alpha \cap \beta)$. If, $\...
0
votes
1answer
6 views

Systematically altering functions

Let A and B be two integers, where their size is constrained to 2 bits in binary. There exists a function F, which outputs integers of the same size, where F(A) = F(B) = Y. For example, A = 01, B = 10,...
2
votes
1answer
577 views

Confusion in 2's complement of 00000000

I'm solving the end of the chapter problems of Morris Mano's Digital Design (4th Edition, if that's relevant). In one of the problems, it is asked to simply find the 1's and 2's complement of 00000000....
2
votes
2answers
92 views

Pumping lemma: the set of strings of 0s and 1s such that when interpreted as an integer, that integer is prime

In the section of my textbook covering the pumping lemma, there are practice questions asking us to prove a given language is not regular. I have not been able to solve this one: The set of ...
1
vote
0answers
34 views

System of congruences with non-pairwise coprime moduli

I have a set of congruences x ≡ a1 (mod n) ... x ≡ ak (mod nk) And I want to find x, this can be solved by the Chinese ...
2
votes
3answers
106 views

Closest divisors in array

Given an array $A[1],\ldots,A[n]$ of natural numbers, we have to construct a new array $B[1],\ldots,B[n]$, where $B[i]$ is equal to $A[j]$ for the minimal $j > i$ such that $A[j]$ divides $A[i]$, ...
2
votes
2answers
134 views

How can I find a number whose sum of digits' cube is equal to n

I'm given a number $n$ and I have to find the smallest number possible whose sum of digits' cube is equal to $n$. For example $n=9$ then output should be $12$, because $1^3 + 2^3=9$.
1
vote
1answer
41 views

Is there any bitwise multiplication algorithm that is sub O(n^2)?

The following program implements a simple algorithm for binary multiplication: ...
0
votes
1answer
108 views

Find n-th number in a number system with only 3 and 4

Given a number system with only 3 and 4. Find the nth number in the number system. There is a solution given here but its very vague without explaining the mathematics/ concept behind it. Can someone ...
0
votes
1answer
21 views

Higher Residuocity Problem w.r.t. a composite Modulus

An integer $q$ is called a quadratic residue modulo $N$ if it is congruent to a perfect square modulo $N$; i.e., if there exists an integer $x$ such that: $x^2≡q\ (mod\ n)$. Otherwise, $q$ is called ...
3
votes
1answer
86 views

Calculating $\sum_{i=1}^a \lfloor a/i \rfloor i^2$

I have a sum: $$S = \sum_{i=1}^n{\lfloor a/i \rfloor i^2},$$ where $a$ is a constant. Is there a way to speed this up? That is, can we avoid iterating overl all $i$s, possibly calculating it in ...
3
votes
0answers
33 views

How hard is it to find the length of multiplicative 2-partition?

Some terminology at first: Multiplicative 2-partition for number $N$ - a pair of numbers $\{A, B\}$ such that $AB=N$. Minimal multiplicative 2-partition length (denoted $l$) - minimal total number of ...
3
votes
1answer
356 views

Computation of discrete logarithm

I know that an equation $$a^x \equiv b \pmod{p}$$ can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as ...
1
vote
0answers
77 views

Algorythm for creating Number-Rows

Given is a list of numbers. Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is ...
-1
votes
1answer
648 views

Calculating mod of n^k mod p in O(log k)

Given $n>0$, $k>0$, and a prime number $p$, compute: $$n^k\mod p$$ in $O(\log k)$ time. Here $x \mod y$ means the remainder for $x$ being divided by $y$. For example, $2^3\mod 7 = 1$. You assume ...
1
vote
0answers
47 views

How does this last step in Shor's algorithm work?

Page 854 of The Nature of Computation states the following (This discussion has made the simplifying assumption that $M/r$ is an integer): If each of the observations gives us a random harmonic, ...
1
vote
1answer
44 views

Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven'...
1
vote
0answers
32 views

eVoting with Damgard-Jurik-Cryptosystem

I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible ...
1
vote
1answer
27 views

Generate a unique number for a set of sequences of letters

A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I ...
0
votes
2answers
57 views

Find the first integer with exactly $n$ divisors

For given positive integer $n$ find the first number $x$ with exactly $n$ divisors. For simplicity of the problem we can assume that $x$ will always fit in integer size and $n \leq 1000$. Example ...
1
vote
0answers
33 views

Reducing integer-rooted polynomial to natural-rooted polynomials

First of all, let me define $Dioph(M)$, where $M$ is a set of numbers: $$Dioph({M})=\{p \mid \text{ $p$ is a polynomial with integer coefficients and the zeros of $p$ are in ${M}$}\}.$$ Let $p \in ...
5
votes
1answer
131 views

Can the semantics of a numeric hierarchy be faithfully represented in Haskell?

I am trying to represent a fragment of a number hierarchy using the Haskell concepts of value, type, and type class. I would like the Haskell code to reflect the mathematical semantics $\vdash ((x \in ...
1
vote
1answer
55 views

Finding solutions to $n m\equiv x \mod n$

Given a modulus $n\in\mathbb{N}$ and another natural number $0<x<n$, what's an efficient algorithm to enumerate all pairs of natural numbers $(a,b)\in\mathbb{N}^2$ such that both $a$ and $b$ are ...
1
vote
1answer
109 views

Is there an online algorithm for radix conversion?

Suppose I have $P$, which is the base-$p$ representation of an integer $n$ and I want to calculate it base-$q$ representation $Q$. The obvious algorithm is: interpret $P$ to obtain $n$, then ...
3
votes
1answer
70 views

Smallest multiple of a number that gives a specific remainder modulo another number

Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$. I can obviously try values of $k$ from $1$ and higher, until I find the ...
1
vote
2answers
727 views

In how many steps Euclidean Algorithm will find the GCD for two integers

I'm trying to solve this problem for big numbers (up to $10^9$). Namely, let's define $$GCD(a,b) = GCD(a-b, b)$$ We define GCD as function that returns greates common divisor of two numbers. In case ...
0
votes
2answers
197 views

Tight bound on the number of divisors of n

The inner loop of this pseudocode runs only for the divisors of n for i=1 to n: if(n%i==0): for j=1 to n: Do something in constant time If I ...
-1
votes
1answer
664 views

Calculating greatest common divisor and least common multiple modulo prime number

I'm trying to solve pretty complex problem with number theory and set of numbers. To make the problem more clear we are going to define $GCD(a, b)$ as the greates number that divides both $a$ and $b$...
3
votes
2answers
74 views

How to find the closest N to the power of X to the given number?

Let's say we have number 4920 and we want to find the closest $n^x$ to 4920 2 ^ 12 = 4096 but it's not the closest possible $n^x$, for example 17 ^ 3 = 4913 is closer to 4920 The question is, how do ...
-1
votes
1answer
52 views

How to compute (n^(n-1)^(n-2)^(n - 3)^(…)^2^1) mod m efficiently?

I'm trying to solve this problem (https://open.kattis.com/problems/exponial) by using fast-exponentiation but I'm getting time limit exicted. How can I compute it efficiently?