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.
228
questions
6
votes
2answers
118 views
How can we count the number of pairs of coprime integers in an array of integers? (CSES)
For reference, I am trying to solve this CSES Problem.
The problem basically states that given up to $10^5$ positive integers in the range $[1, 10^6]$, find the number of pairs of those positive ...
0
votes
2answers
68 views
Proving $b_1! \cdots b_k! < (b_1 + \cdots + b_k+1)!$ [closed]
I can't figure out how to solve this problem:
Let $b_1,b_2,\ldots,b_k$ be positive integers with sum less than $n$. Prove that $$b_1!b_2! \cdots b_k! < n!.$$
0
votes
0answers
16 views
Calculating ring inequalities with fixed precision
Suppose we are given $n$ $M$-bit (the word size of the computer) integers $x_i$, and wish to calculate a linear or nonlinear inequality involving the numbers (an expression made up from the $x_i$, ...
1
vote
1answer
46 views
An algorithm that finds ord(a) in $O(\log n)$
Let $p$ be a Fermat prime ($p=2^m+1$) and $n=p2^k$ and $a∈Z^*_n$, I should suggest an algorithm that will find $\operatorname{ord}(a)$ in polynomial time (that is, in time polynomial in $\log n$).
I ...
1
vote
2answers
43 views
Half precision floating point question — smallest non-zero number
There's a floating point question that popped up and I'm confused about the solution. It states that
IEEE 754-2008 introduces half precision, which is a binary
floating-point representation that uses ...
1
vote
3answers
104 views
Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$
Prove that there are infinitely many primes that divide none of the elements of the integer sequence
$a_{n+1} =1+a_0 a_1 \cdots a_n$, with a starting point of $a_0 \geq 0$.
I thought about $$\log (...
14
votes
0answers
130 views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
1
vote
2answers
65 views
Sum duplicates in array problem
I get $n$ numbers, where every number is an integer between 1 and 1000. If within given numbers are duplicates, I sum all of them to one number. I repeat it until I have only distinct elements. As a ...
0
votes
0answers
86 views
Fast factorial computation
I'm trying to solve this problem - https://codeforces.com/problemset/problem/711/E
I've already found and proved that the result is equal to:
$$
1 - \frac{2^n (2^n - 1) \cdots (2 ^ n - k + 1)}{2^{...
0
votes
2answers
134 views
Find the minimum subset of a set of numbers with product divisible by a given integer
The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
...
0
votes
1answer
60 views
Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$
Hope you had a fantastic christmas break :)
I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express ...
1
vote
1answer
53 views
An algorithem for finding the number of primes of the form 4k+3 under some n
I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 ...
1
vote
1answer
32 views
Strengthening a given attack on discrete log
I am trying to prove the following claim:
Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume
there exists some adversary $A'$ of size
$T'=\frac{\left(T-O\left(\log m\right)\right)}{...
2
votes
2answers
78 views
How to iterate the Hardy-Ramanujan integers quickly
The Hardy-Ramanujan integers, A025487 - OEIS, are integers which when factorized, have their exponents for all the primes starting from 2, in decreasing (not strictly) order. The first few terms are:
$...
0
votes
0answers
24 views
Radix Economy of Complex Bases
If we extend the allowed bases for a numerical system to the complex numbers, is e still the most economic base? If not, what would it be?
There's the well-known formula for radix economy:
Where b is ...
1
vote
1answer
14 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
5
votes
2answers
322 views
Efficient Algorithm to Find the n-th Odious Number
An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script ...
2
votes
3answers
155 views
Shortest path in modular arithmetic
Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and ...
0
votes
0answers
55 views
Finding index of $p_{k}$ element in the original sorted array if elements were to be removed using a specific condition
Consider a sorted list of numbers $C_{0}=\{0,1,2,3,...,n-1\}$ from where one element will be eliminated at each step. We are also given a value $L$ in $[0, 1)$ and let the indexing start from $0$.
...
0
votes
1answer
58 views
Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?
Given arbitrary integers of $K$ and $M$, is $2^K$ + $M$ a prime?
...
-1
votes
1answer
80 views
Number of sequences of given type
Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
2
votes
2answers
120 views
Efficient way to reduce a binomial coefficient as a fraction
Here is the full problem.
You need to calculate Euler's totient function of a binomial coefficient $C_n^k$.
Input
The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$.
...
3
votes
1answer
62 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
54 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
54 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
23 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
36 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 ...
1
vote
0answers
41 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
21 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
84 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
88 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
96 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
49 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
76 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
33 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
110 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
144 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
44 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
48 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
23 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
53 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
86 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
86 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
106 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
34 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
25 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
71 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
53 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 ...
