2022 Developer Survey is open! Take survey.

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.

Filter by
Sorted by
Tagged with
1 vote
1 answer
23 views

Period of modulo exponentiation function from factors

The calculation of the period of the "modulo exponentiation" function: $$ f_a(r) = a^r (mod \ N) $$ is a step of the quantum algorithm for factorizing $N$, where $a$ is a number chosen with ...
user avatar
3 votes
1 answer
70 views

Computable Numbers and Cantor's Diagonal Method

We were given the following problem in our university: We will call $x \in (0; 1)$ computable iff there exists an algorithm (e.g. a programme in Python) which would compute the $n^{th}$ digit of $x$ (...
user avatar
1 vote
2 answers
72 views

Why does the hash function in Rabin—Karp produce unique hashes?

The Rabin–Karp algorithm uses a rolling hash function to find a substring matching a pattern: $$ H = c_1a^{k-1} + c_2 a^{k-2} + c_3 a^{k-3} + \cdots + c_k a^0, $$ where $a$ is a constant, $c_1\ldots ...
user avatar
1 vote
0 answers
23 views

Finding square root of a gram matrix over the integers [closed]

Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
user avatar
1 vote
1 answer
38 views

Where does each part of the $1 - (1 - 1/k)^k$ approximation for the Maximum Coverage problem come from?

A solution to an instance of the Maximum Coverage problem with a budget of k subsets can be approximated with a greedy algorithm that, at each iteration, picks one of the subsets that adds the most ...
user avatar
2 votes
1 answer
47 views

Is there a simplistic way of describing the proof to the undecidability of David Hilbert's 10th problem?

I recently have been reading a bunch about David Hilbert's famous 10th problem, and trying to understand its proof. I am currently in the process of reading through an explanation of the proof, given ...
user avatar
2 votes
1 answer
29 views

Why does this algorithm to calculate number of pronic numbers in an interval work?

I am given $A$ and $B$, where $A$ is less than or equal to $B$, and they are in the range of $[1, 100000000]$. I want to calculate the number of pronic numbers in that interval $[A, B]$. These numbers ...
user avatar
3 votes
1 answer
76 views

Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences

Given: a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V_i}$ given by $\cdots,\vec{{V_i}_{-1}},\vec{{V_i}_0},\vec{{V_i}_1},\cdots$ ...
user avatar
1 vote
1 answer
37 views

algorithm to check the existence of $b-1$ in $(n)_b$?

Given an integer number $n$ (in base 10) and a base $b$, determine whether the representation of $n$ in base $b$, $(n)_b$ has a coefficient with value of $b-1$. ...
user avatar
  • 173
0 votes
1 answer
54 views

How to get the numbers in the Sieve of Eratosthenes with wheel factorisation?

I'd like some help with figuring out the algorithm for the Sieve of Eratosthenes with wheel factorisation. Specifically, I need help figuring out if it's possible to convert between an index and the ...
user avatar
  • 111
0 votes
0 answers
29 views

Number partition subjected to the cardinality of subset

I hope someone can take some time to consider the following problem and welcome to discuss together. Number partition problem is one of well-known NP-hard problems. Now I am considering the hardness ...
user avatar
1 vote
1 answer
51 views

Why we get at most $N^2$ probe sequences using double hash function

Question:Given the following double hash function: $$h(k,i) = (h_1(k) + i\times h_2(k)) \bmod{N}$$, where $h_1(k): key \to \mathbb{Z}$. $h(k,i)$ can generate $N^2$ probe sequences at most and $h_2(k)$ ...
user avatar
  • 459
0 votes
0 answers
29 views

What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
user avatar
1 vote
0 answers
42 views

Computability of base-conversion for streams

With regular numbers it is always possible to convert them from one (integer) base to another. But what happens if we consider numbers for which their magnitude is not known in advance, or in other ...
user avatar
  • 41
1 vote
0 answers
56 views

Is it possible to find length of sum of two binary numbers without calculating sum?

I'm doing an assignment where I need to multiply two 16 bit numbers and store result as an 16 bit integer array. a is binary with length of ...
user avatar
0 votes
1 answer
29 views

Sharing a requested secret number not knowing which

Alice has a list of secret numbers. Alice wants to give Bob the opportunity to choose one of her secret numbers, and then Alice has to share that specific secret number, but in such a way that Alice ...
user avatar
6 votes
2 answers
919 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 ...
user avatar
0 votes
2 answers
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!.$$
user avatar
0 votes
0 answers
24 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$, ...
user avatar
1 vote
1 answer
48 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 ...
user avatar
  • 117
1 vote
2 answers
221 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 ...
user avatar
  • 13
1 vote
3 answers
108 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 (...
user avatar
14 votes
0 answers
154 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 ...
user avatar
  • 241
1 vote
2 answers
83 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 ...
user avatar
0 votes
0 answers
108 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^{...
user avatar
  • 101
0 votes
2 answers
142 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. ...
user avatar
0 votes
1 answer
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 ...
user avatar
1 vote
1 answer
74 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 ...
user avatar
1 vote
1 answer
35 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)}{...
user avatar
  • 163
2 votes
2 answers
117 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: $...
user avatar
  • 303
1 vote
1 answer
20 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 ...
user avatar
  • 3,728
5 votes
2 answers
383 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 ...
user avatar
  • 53
2 votes
3 answers
292 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 ...
user avatar
  • 202
0 votes
0 answers
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$. ...
user avatar
  • 11
0 votes
1 answer
60 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? ...
user avatar
-1 votes
1 answer
81 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\...
user avatar
2 votes
2 answers
166 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)$. ...
user avatar
4 votes
1 answer
89 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 ...
user avatar
1 vote
1 answer
69 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....
user avatar
1 vote
0 answers
57 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 ...
user avatar
  • 11
1 vote
2 answers
25 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-...
user avatar
  • 151
1 vote
0 answers
42 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 ...
user avatar
1 vote
0 answers
52 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: ...
user avatar
0 votes
0 answers
26 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 ...
user avatar
1 vote
1 answer
107 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{...
user avatar
3 votes
1 answer
93 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, ...
user avatar
  • 131
1 vote
0 answers
100 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 ...
user avatar
0 votes
1 answer
50 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 ...
user avatar
2 votes
0 answers
81 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 ...
user avatar
1 vote
0 answers
40 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 ...
user avatar
  • 5,722

1
2 3 4 5