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.
207
questions
3
votes
1answer
40 views
Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials
Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
1
vote
1answer
37 views
Must a decision problem in $NP$ have a complement in $Co-NP$, if I can verify the solutions to in polynomial-time?
Goldbach's Conjecture says every even integer $>$ $2$ can be expressed as the sum of two primes.
Let's say $N$ is our input and its $10$. Which is an integer > 2 and is not odd.
Algorithm
1....
1
vote
0answers
47 views
Evaluating functions related by Mobius inversion formula
Problem
Consider two functions $f: \mathbb{N} \rightarrow \mathbb{N}$ and $g: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(k) = \sum_{d | k} g(d)$ for all $k \in \mathbb{N}$. So, the questions ...
1
vote
2answers
19 views
Relation/use of irrational or transcedental numbers in computer science?
I'm wodering about the relationship between the theory that studies irrational/transcendental numbers and computer science. For example, I found this paper (but was unable to get the full text)
Pseudo-...
1
vote
0answers
31 views
Decidability of equality of expressions involving exponentiation
Let's have expressions that are finite-sized trees, with elements of $\mathbb N$ as leaf nodes and the operations {$+,\times,-,/$, ^} with their usual semantics as the internal nodes, with the special ...
0
votes
0answers
14 views
Which branches of computer science make use of algebraic number theory?
There was similar question about Analytic Number Theory: https://cstheory.stackexchange.com/questions/46555/analytic-number-theory-in-tcs
1
vote
0answers
15 views
Rabin Karp algorithm that uses bitwise AND
I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here.
Here's the gist of it:
...
0
votes
0answers
19 views
Need help optimizing an algorithm that's supposed to maximize the greatest common divisor of n elements by removing at most one element
Alright, first here's the text of the problem:
You're given n bags of candies where the i-th bag contains a[i] candies and all numbers a[i] are in the segment [1,m]. You can choose a natural ...
1
vote
1answer
52 views
Finding the smallest number that scales a set of irrational numbers to integers
Say we have a set $S$ of $n$ irrational numbers $\left\{a_1, ..., a_n\right\}$.
Are there any known algorithms that can determine a scaling factor $s \in \mathcal{R}$ such that $s * a_i \in \mathcal{...
3
votes
1answer
82 views
How to Generate Münchhausen Numbers in High Radices?
A MĆ¼nchhausen number is a whole number equal to the sum of its digits raised to powers of themselves. For the purpose of such calculations, the convention is that $0^0 = 1$. For example, in radix 10, ...
1
vote
0answers
90 views
how did the authors of the AKS-Paper come up with the upper bound for r? and what does the multiplicative order have to do with anything?
I have been recently reading the paper "PRIMES is in P", but unfortunately a lot the steps were skipped, which led to confusion. My main problem is with the upper bound on r which was not explained at ...
0
votes
1answer
43 views
Given a set of integers $D$ and a positive value$P$, find an algorithm to find set of integers satisfying a condition
Given a set of positive integers :
$ \\ D = \{ D_1, D_2, ..., D_n\}$
and a non-negative integer $P$, where $P$ is divisible by every element in $D$, then find ...
2
votes
0answers
59 views
Counting triplets from three arrays satisfying the equation x^2 = yz
Let's say I have three arrays of positive integers X, Y and Z. You can assume that each of ...
1
vote
0answers
20 views
Circuit depth of computing the continued fractions of a rational number
If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input?
I was reading through some notes which ...
3
votes
1answer
63 views
Efficiently prime factorising an integer with an oracle
Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns ...
1
vote
1answer
70 views
Finding a winner in a “long list”
This is from betting domain which has something that is called a long list: a list of a "home team win/draw/away team win" markets for 13 games.
A punter can select any combination of the possible ...
3
votes
1answer
60 views
Number of ways n can be written as sum of at least two positive integers
I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. ...
2
votes
1answer
40 views
What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?
Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are ...
3
votes
0answers
45 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 ...
1
vote
0answers
47 views
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 ...
0
votes
0answers
22 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 ...
0
votes
1answer
44 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.
5
votes
0answers
82 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 ...
0
votes
1answer
65 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 ...
0
votes
1answer
101 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 ...
1
vote
1answer
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 ...
1
vote
1answer
23 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 $\...
0
votes
1answer
68 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
51 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
62 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
95 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
149 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
65 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
33 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
140 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
46 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
79 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
80 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
162 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
28 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
70 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
117 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
134 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
123 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
198 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
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 ...
3
votes
0answers
17 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
38 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
78 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 ...
