# 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.

237 questions
Filter by
Sorted by
Tagged with
19 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 ...
73 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$ ...
36 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$. ...
51 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 ...
27 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 ...
44 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)$ ...
28 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 ...
31 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 ...
42 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 ...
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 ...
567 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 ...
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!.$$
23 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$, ...
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 ...
116 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 ...
106 views

138 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. ...
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 ...
54 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 ...
32 views

17 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 ...
360 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 ...
194 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 ...
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$. ...
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? ...
81 views

89 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, ...
97 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 ...
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 ...
80 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 ...
37 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 ...
116 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 ...
72 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 ...
205 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. ...
54 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 ...
### 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 ...