The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
73 views

Breaking up sum of power of 2s

I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays. I encountered a sub-problem that requires me to break up sums of numbers which are power of ...
1
vote
1answer
37 views

Reversing Key Algorithm

I have to craft up a number made of 19 digits so that, after some mathematical operations made 11 times, the resulting sum of the remainders of the first ten operations is equal to the the remainder ...
4
votes
2answers
65 views

Quick calculation for $(x^y) \bmod z$

What are the possible ways to calculate $(x^y) \bmod z$ quickly for very large integers? Integers $x,y \lt 10^{10000}$ and $z \lt 10^6$.
1
vote
0answers
32 views

Computing n! modulo p [closed]

I found an intersting problem. I have to compute n! modulo p and can't figure out a way of doing this. For small ns I can ...
1
vote
1answer
61 views

Why don't people use Fermat's little theorem to check if number is prime?

There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula $\qquad a^{p-1} \equiv 1 \pmod p$, to check if a number ...
1
vote
1answer
75 views

Number of K-sets [closed]

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
3
votes
2answers
105 views

Implement Mathematica's capability of rationalizing machine reals

If I have a variable x bound to a machine precision real in Mathematica, I can use y = FromDigits[RealDigits[x]] then y is ...
2
votes
1answer
62 views

Are there pseudorandom number generators (PRNG) with no finite period?

The typical and widely used PRNG, the linear congruential generator always has a finite (though possibly "long") period. Are there PRNGs that have no finite period? For this question it is not ...
0
votes
1answer
44 views

What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$. So I need to know what growth the $\psi(m)$ has.
3
votes
1answer
46 views

2SUM with a weight

Suppose we have a $n\times n$ symmetric matrix $\mathbf A$. I want to know if there exists two elements of a vector $\mathbf x$, let's call them $x_i,x_j,i\ne j$, such that $x_i +x_j+[A]_{i,j}\ge y$ ...
3
votes
1answer
446 views

Shift-and-or multiplication operation

Continuing in the same vein as Carry-free multiplication operation, a followup question is as follows (differences in bold): Let $r = p \oplus q$ be an operation similar to multiplication, but ...
3
votes
2answers
128 views

Carry-free multiplication operation

In long-multiplication, you shift and add, once for each $1$ bit in the lower number. Let $r = p \otimes q$ be an operation similar to multiplication, but slightly simpler: when expressed via ...
3
votes
0answers
204 views

Best complexity of parity/comparison in the Residue Number System

Let: $\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers, $M=\prod_{i=1}^{k} m_i$ $X$ be a natural integer, such that $X < M$ Then $X$ can be expressed in the Residue Number ...
2
votes
1answer
54 views

Finding number of numbers dividing n^m exactly p times

Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times. ...
3
votes
1answer
104 views

integer factoring using Fermat's method

Reading an article on integer factorization I implemented the following - rather inefficient - factorization method: Every odd composite can be factored as a difference of squares: $$ ab = ...
4
votes
1answer
126 views

How hard is factoring a complex number?

Given complex number $C=a+ib$, I want to find two complex numbers $C_1=x+iy$ and $C_2=z+iw$ such that $C=C_1*C_2$ (a,b,x,y, z and w are all non zero integers). This problem is at least as hard as ...
3
votes
0answers
189 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
1
vote
1answer
278 views

Recursive definition of sum of two numbers in terms of the successor function

This is a question from the book Data structures using C and C++ by Tenenbaum. Not a homework problem but self-study. Recursive definition of a+b, where a and b ...
4
votes
2answers
64 views

Remove divisors from a set of integers

I have a set $S$ of integers. I want to remove all elements of $S$ that are divisors of another element of $S$. In other words, I want to compute $T = \{y \in S : \forall d \in S . d \nmid y \}$. ...
3
votes
2answers
405 views

Find out the largest LCM of the partitions of n

I want to find out an algorithm to find out the largest least common multiple (LCM) of the partitions of an integer $n$. Example: $5 = 1 + 4$, $5 = 2 + 3$, since $\mathrm{LCM}(1,4) < ...
11
votes
1answer
127 views

Complexity of taking mod

This seems like a question that should have an easy answer, but I don't have a definitive one: If I have two $n$ bit numbers $a, p$, what is the complexity of computing $a\bmod p$ ? Merely ...
6
votes
0answers
132 views

The length of the smallest co-prime chain between any two integers

I found a variant of this problem in one of the recent algorithms competitions. Given any two integers ($A,B, A \lt B$), find the least number, $L$, of integers between $A$ and $B$ ($N_i, 1 \lt i ...
2
votes
1answer
49 views

Faster Algorithm for Computing Norm

Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function: $$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$
10
votes
2answers
445 views

Finding the size of the smallest subset with GCD = 1

This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this ...
10
votes
0answers
230 views

Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 ...
6
votes
1answer
144 views

Quadratic residue and integer factoring

I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime). I am looking at the ...
9
votes
1answer
193 views

Algorithmic consequences of algebraic formula for partition function?

Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic ...
5
votes
1answer
315 views

In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test: It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for ...
2
votes
0answers
140 views

Reduction from knapsack problem to Integer relation that equals one

My question is related to the Integer Relation Detection Problem which can be formulated as: $\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$ Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land ...
2
votes
1answer
49 views

Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits

I was solving this equation: $$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$ Given $$ 1,000,000,000 < a, n, m \; < 5,000,000,000, $$ $$ a, m \text{ are coprime}. $$ I solved it ...
15
votes
0answers
202 views

Subset sum problem with many divisibility conditions

Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let $\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
6
votes
2answers
741 views

How fast can we find all Four-Square combinations that sum to N?

A question was asked at Stack Overflow (here): Given an integer $N$, print out all possible combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$. ...
1
vote
0answers
170 views

Finding a sequence of numbers where every product of two mod k is unique

I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$. Now I want the product of any pair of two numbers in the sequence modulo ...
8
votes
2answers
206 views

Complexity of computing $n^{n^2}$

What is the complexity of computing $n^{n^2},\;n \in \mathbb{N}$?
7
votes
1answer
118 views

Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c ...