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.
181
questions
1
vote
1answer
17 views
Use Fact to decompose a given number
Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\...
1
vote
1answer
41 views
How to count all integers less than a given integer and having two contigous digits as $y$?
Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
2
votes
1answer
44 views
How do I minimize the cost of some algorithm that performs some operation on a list?
I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
0
votes
1answer
47 views
Express a number with a combination of arithmetic operations and a single number
Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number using only a single number an any combination of arithmetic ...
3
votes
2answers
87 views
Proving that a set of operations can't generate one integer from a given one
Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?
Example: 335 can be deduced from 2000 using division by 2, ...
3
votes
4answers
116 views
How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?
For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
-1
votes
1answer
37 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 ...
0
votes
1answer
30 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$ ...
3
votes
2answers
122 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 ...
1
vote
2answers
31 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 ...
2
votes
1answer
56 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 ...
2
votes
1answer
45 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 ...
1
vote
1answer
96 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 ...
2
votes
2answers
27 views
An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$
Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}...
-2
votes
1answer
53 views
Number Theory Problem from Local Selection Contest EPFL | ETHZ
This was a question from the 2016 local (selection) contest in ETHZ, You have a high-precision alarm clock with three operations:
1) reset wake-up time to midnight (00:00:00.000000)
2) modify the ...
2
votes
2answers
78 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
73 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
22 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
102 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
135 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
30 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
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}$ ...
1
vote
1answer
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?...
1
vote
3answers
68 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
75 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
30 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
72 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
133 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
92 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
84 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
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 ...
6
votes
0answers
34 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
206 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
81 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
106 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
1k 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
192 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
47 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
120 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
294 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
50 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
193 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
24 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 ...
2
votes
1answer
90 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
35 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
377 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
86 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
870 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
54 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, ...
