The tag has no usage guidance.

learn more… | top users | synonyms

18
votes
2answers
288 views

How to find the element of the Digit Sum sequence efficiently?

Just out of interest I tried to solve a problem from "Recent" category of Project Euler ( Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as ...
5
votes
1answer
95 views

Sum of divisors summatory function with Erathosthenes' sieve

I ran across the following problem from an online problem bank: there are up to $~10^5~$ queries each of which asks to compute the sum $$\sum_{k = L}^{R} \sigma(k)$$ where $\sigma(k)$ is the sum of ...
2
votes
1answer
36 views

How does RAID-5 algorithm locate the right device?

Please consider the following diagram of a RAID-5 array (Ignore the gray background): Now, given a logical address, how can one return the device number (0-3)? For example, ...
2
votes
1answer
19 views

First Harshad number with given sum

How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits. I think that some kind of dynamic ...
0
votes
1answer
40 views

How to compute Jacobi symbol efficiently?

How do I compute the Jacobi symbol $(N|A)$ efficiently? In particular, for every odd $N, A$, define the Jacobi symbol $(A|N)$ as $\prod_i Q_{p_i}(A)$ where $p_1, \dots , p_k$ are all the (not ...
1
vote
1answer
25 views

Calculating product of totient functions

Suppose that i need to compute product $~\phi(1) \dots \phi(n)~$ modulo prime $500009$ as fast as possible. Memory limitations are rather tough: $64$ mb so i can't just keep all the values of totient ...
1
vote
1answer
20 views

Sieving to compute first values of totient function

What i want to do is to compute the first $n$ values of Euler's totient function effectively. As far as i know the best way to do it is to run a sieving algorithm and for each prime encountered to ...
1
vote
1answer
54 views

What is more efficient: gcd(x,y) or brute force, when x and y are a very big numbers

I implemented the quadratic sieve algorithm as it's described in wiki. Most of the work of the algorithm is to determine if some big integer $Y$ belongs to the vector $b[b_1,b_2,b_3,\ldots]$. So far ...
2
votes
2answers
36 views

Shortest path in divisors graph

There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. ...
6
votes
2answers
27 views

Is the following intuition valid for understanding $k$-wise independent hash functions?

I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable ...
3
votes
1answer
111 views

Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$

You are given $N$ $(1 \le N \le 10^6)$ positive integers $a_1, a_2, \ldots, a_N (1 \le a_i \le 10^6)$ and two positive integers $D$ $(1 \le D \le 10^6)$ and $M$ $(1 \le M \le 10^6)$ Find the longest ...
8
votes
2answers
130 views

Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square ...
4
votes
1answer
31 views

How does one find a non-quadratic residue modulo $p$?

I was wondering how one can find a non-quadratic residue modulo $p$ and what the runtime of this algorithm would be. I thought that one can use the Legendre Symbol $$ \left( \frac{a}{p} \right) = ...
2
votes
2answers
146 views

Number of special paths between two nodes

Consider a directed graph. Each node in this graph has an integer label. We want to count the number of special paths between source and ...
2
votes
3answers
245 views

Counting an integer's divisors without just enumerating them (or estimating if not possible)?

I'm trying to count the number of divisors an integer $n$ has. The simple way to do this is to just enumerate all integers from 1 to $\sqrt{n}$, and count how many integers evenly divide $n$. For ...
2
votes
0answers
89 views

Determining whether a number is a perfect square without computing its square root

One of the interesting results of Number Theory is the theory of quadratic reciprocity. One finds that it is possible to determine whether an equation $x^2 \equiv a \pmod p$ has a solution $x$ without ...
2
votes
1answer
88 views

How many operations at maximum needed to compute powering of a number, i.e. $N^k$?

Suppose $N$ is $L$-bit long and $k$ is also $L$-bit long. How to show that it takes at most O$(L^2)$ operations to compute it. For example $N = 1010$ and $k = 10$. Then $N^k = 6^2 = 100100$. But I ...
-1
votes
2answers
414 views

number of subsets where GCD equals to X

The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD ...
4
votes
1answer
80 views

Least Common Non-Divisor

Basically, the problem is: For a set $S$ of positive numbers, find a minimal number $d$ that is not a divisor of any element of $S$, i.e. $\forall x \in S,\ d \nmid x$. Denote $n = |S|$ and $C = ...
3
votes
2answers
136 views

Checking whether a number divides any of a set of other numbers

Consider a static set $S$ of positive numbers from range $[1..10^9]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | ...
2
votes
1answer
62 views

Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

What is the best algorithm for computing the number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization $n=p_1^{a_1}p_2^{a_2} \ldots p_i^{a_i}$? ...
3
votes
1answer
86 views

Determining if (infinite) binary language DFAs contain at least 1 prime?

This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. ...
5
votes
2answers
89 views

Finding the k-th smallest rational number efficiently

Consider the following set: $S := \left\{\frac{a}{b} \colon a \in \{1,\ldots,A\}, b \in \{1,\ldots,B\} \right\}$ $S$ is the set of all rational numbers that can be represented by two integers $a$ ...
3
votes
1answer
77 views

Devising an Algorithm for Linear Combination with Column Restrictions

Application: We intend to factor an integer $N$ using a variation of the rational sieve. This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ ...
-1
votes
1answer
26 views

How n (1+b) is not prime? [closed]

Here is the complete proof taken from this link How do I convince myself that n(1+b) is not prime when b>=1? Here is what I did: if n is 3 and b is 3. Then ...
3
votes
0answers
48 views

How is Chinese Remainder Theorem used in the proof of correctness for RSA

Question At the very end of (most) proofs of RSA's correctness we have something like $$m^{ed}\equiv m\pmod p$$ $$m^{ed}\equiv m\pmod q$$ Therefore by the Chinese Remainder Theorem (CRT) ...
1
vote
1answer
54 views

Quadratic Diophantine equation - Polynomial Time Cases

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete. The solution (x, y) are ...
2
votes
1answer
39 views

Efficient computation of traces of all primitive elements in field extensions of GF(2)

Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from ...
1
vote
0answers
22 views

Finding all “smooth” numbers up to 10^6 — problem with nested loops [duplicate]

A [smooth number] is one whose factors are all "small". For a computational problem, I would like all smooth numbers up to $10^8$. I think it's unfeasible to factor a billion numbers. Instead, I ...
5
votes
3answers
271 views

How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$? I've googled around a bit and found the sequence in OEIS, but I don't really see a ...
1
vote
1answer
58 views

Introduction to number theory [closed]

What is the best book for a beginner in Introduction to number theory? I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of ...
-1
votes
2answers
114 views

What is complexity of checking whether a natural number is a perfect square? [closed]

As the title says, what is complexity of checking whether a natural number is a perfect square?
1
vote
1answer
50 views

Smallest possible integer not obtained from sumset

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A) What is the best way of finding the ...
5
votes
1answer
49 views

Fast polynomial calculation over $\mathbb{Z}_{487}$

Given a polynomial $a(x)$ of degree at most $242$ over $\mathbb{Z}_{487}$, I'd like to choose distinct values $x_0, x_1, . . . , x_{242} ∈ \mathbb{Z}_{487}$, such that I'll be able to calculate $a(x_j ...
2
votes
2answers
55 views

Finding the values of x and y using base 8 [closed]

In finding the values of x and y, if (x567) + (2yx5) = (71yx) ( all in base 8) I proceeded as under. I assumed x=abc and ...
3
votes
1answer
96 views

Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$

I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$. ...
5
votes
1answer
918 views

What does the set {n | n is an integer and n = n + 1} represent?

I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This doesn't make any sense to me. I ...
6
votes
1answer
67 views

Runtime of Euclidean Algorithm

Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of ...
1
vote
1answer
26 views

A problem regarding Extended Euclidean Algorithm

Alex has some (say, n) marbles (small glass balls) and he has going to buy some boxes to store them. The boxes are of two types: Type 1: each box costs c1 Taka and can hold exactly n1 marbles Type ...
4
votes
1answer
68 views

Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form

As stated in the title: Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form. For example: when $p = 2$ and $q = 3$ Next of $2^2*3=12$ is ...
1
vote
2answers
107 views

Proving that $2^n$ does not divide $n!$ [closed]

How can prove that $2^n \nmid n!$ using binary representation for $n!$ and $2^n$.
0
votes
2answers
52 views

Algorithm for generation of Canonical represented integers [closed]

Is there a way to get canonical representation of an integer by algorithm? I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How ...
5
votes
1answer
133 views

Complexity of Pythagorean triples

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
1
vote
1answer
42 views

Number of nonnegative solutions of linear Diophantine inequality

Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it. Is there exists algorithm which ...
1
vote
1answer
94 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
4
votes
3answers
150 views

counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will ...
4
votes
1answer
398 views

Efficiently finding the maximum pairwise GCD of a set of natural numbers

Consider the following problem: Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers. Let $G = \{$ $gcd(s_i, s_j)$ | $s_i, s_j \in S,$ $ s_i \neq s_j \}$ where $gcd(x,y)$ is ...
2
votes
1answer
58 views

Checking whether a number is a square or higher power modulo n

Is there an algorithm to check whether an integer $x$ is a square modulo $n$, where $n$ is an integer whose factorization we do not know? Is the Jacobi symbol helpful? What about higher powers, ...
2
votes
2answers
267 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
55 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 ...