# Tagged Questions

47 views

### simple maths problem

N locations are numbered from 0 to N-1. Given a int[] containing N elements. The i-th (0-based index) element of array is the number of persons who live near location i.One car can move to one ...
124 views

### Numbers permutation

Given $n$ numbers and $k$ positions I want the total number of permutations of these n numbers on these $k$ positions if repetition is allowed and if the following two arrangements are considered ...
102 views

### The number 3211000 is 7-special

Define a positive integer $k$ to be $n$-special if it satisfies the following properties: It has $n$ digits (0, 1, ..., 9) The 1st digit is equal to the number of 0's in the decimal representation ...
125 views

### When do repeated intervals of time overlap?

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time. So each ...
119 views

### Identifying Ways of Dividing an Area into Merged Regions

Suppose an area is divided into N irregular regions. Unless N is very small there will be many ways in which a new division of the area can be obtained by merging adjacent regions. I want to ...
82 views

### Euclidean Algorithm Question

So I have been asked to find $d=(a,b)$ when $a=1109$ and $b=4999$ and express $d$ as a linear combination of $a$ and $b$ Well I have worked out that $d=1$ but I am struggling to express $d$ as a ...
75 views

### Smallest integer which cannot be derived from set of numbers

Let's assume that I have k number of ns (e.g. 6,6 , k = 2 , n = 6) I'd like to find the ...
65 views

### Count of numbers with the given prime factors in a range [duplicate]

Given two primes: $p$ and $q$, $p \neq q$ and $n \in N$ find count of numbers $u$, so that $u \leq n$ and $u = p^k q^l$; $k, l \in N$. If we'd given with just one prime $p$ this count would be ...
59 views

### pair wise AND operation between two set of elements

I have two sets of size say $m$ and $n$. I wanted to find the sum of all pair-wise AND operation between the elements of both the sets. Suppose, if set $A=\{1,2,3\}$ and set $B=\{8,9\}$. I want to ...
42 views

### Calculating modular inverses with limited multiplication

Question Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications ...
85 views

### Bound on total divisions of Euclid's Algorithm.

Question Suppose $\lambda$ is a positive integer and I want to show that there exists integers $a,b$ such that $a > b > 0$, $\lambda \geq \log_2b/\log_2\phi$, and Euclid's Algorithm on $a,b$ ...
200 views

### Find an algorithm to compute $(1! \cdot 2! \cdot3!\cdots n! ) \,\%\, x$.

You need to find the product of first n factorials $1! \cdot 2! \cdots n!$ modulo $109546051211.$ $1 \le n \le 10^7$. I need a fast algorithm for this.
54 views

### Improving Montgomery product

I am reading the paper "A Cryptographic Library for the Motorola DSP56000" (http://link.springer.com/content/pdf/10.1007%2F3-540-46877-3_21.pdf) which describes a trick to speed-up calculation of the ...
43 views

### $n$-Bit Strings Not Containing $010$

So, I am asked to consider the number of $n$-bit strings that don't contain $010$ by considering the following $m$-leading-zero cases for $m\geq 0$, where $m\in \mathbb{N}$: $1\cdots$ $01\cdots$ ...
90 views

### Paths Within a Lattice

So, I'm reading this proof: Lemma 4.2. The SchrÃ¶der numbers $(r(n):n\geq0))$ satisfy $$r(n)=r(n-1)+\sum_{k=0}^{n-1}r(k)r(n-1-k)\text{ for }n\geq1,\text{ with } r(0)=1$$ Proof. The SchrÃ¶der number ...
86 views

### Is the extended Euclidean algorithm optimal for computing modular inverses?

Is there an algorithm that can compute modular inverses in less than $O(n^{2})$? If not, is the Euclidean algorithm provably optimal?
104 views

### Minimum number of moves to equalize a list

Given a list of $n$ integers. In one move we can either decrease exactly one element by $1,2$ or $5$. What is the minimum number of moves required to equalize the list? For example: If the list is ...
268 views

154 views

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ... 1answer 78 views ### How quickly can we detect if a digit is in a number? If we suppose that we have a number n in base b, represented as a power series:$$n = d_0 b^0 + d_1 b^1 + d_2 b^2 + \dots$$...where the d_k's are the digits, how quickly can we determine if ... 1answer 149 views ### Computing RSA Algorithm Modulus N=247; encryption exponent r=7 Encrypt 100; Decrypt 120. Solution: Encryption of 100 is 35. Decryption exponent of is 31. Decryption of 120 is 42. For a discrete math ... 1answer 175 views ### Does there exist a positive integer n such that it will be twice of n when its digits are reversed? Does there exist a positive integer n such that it will be twice of n when its digits are reversed? We define f(n)=m where the digits of m and n are reverse. Such as ... 2answers 78 views ### most efficient way to convert a number into a fraction supposing I have a decimal like$$ 0.30000000000000027$$What would be the best way to know the same number but in a fraction way like we know \dfrac{1}{3} > 0.30 > \dfrac{1}{4} because ... 2answers 51 views ### Having A_1=a+b+c,A_2=a^2+b^2+c^2, A_3=a^3+b^3+c^3 - how to get a,b,c? Perhaps I'm just a bit dense at the moment - I've re-read some of my notes from monthes ago concerning elementary symmetric polynomials, and I find that I've no idea how to approach the "inverse" ... 5answers 195 views ### How can I find the value of a^n+b^n, given the value of a+b, ab, and n? I have been given the value of a+b , ab and n. I've to calculate the value of a^n+b^n. How can I do it? I would like to find out a general solution. Because the value of n , a+b and ab ... 1answer 130 views ### Does the difficulty of discrete logarithm depend on the difficulty of integer factorization? The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ... 1answer 320 views ### How to show that Eratosthenes sieve algorithm has a complexity of O(n\log n) I know this is a loose upper bound, but I am in an entry level CS course that is just trying to get us used to evaluating algorithms. Any pointers on how to move forward on this problem? 2answers 113 views ### proving algorithm to check if two strings are anagrams- I have this idea (using C language) for checking for two string if they are anagrams- if the length of the strings is the same (its only a-z and A-Z). sum of ASCII value of all chars in a string is ... 4answers 272 views ### Determining the next Twin Prime? A really simple I question I guess. Is there an algorithm or method such that given an integer N there is a way to determine the next twin prime pair greater than N? If yes then could you please ... 1answer 161 views ### Running time of Modular Exponentiation I am trying to understand why the modular exponentiation algorithm has a running time of about \log(n) where n is the exponent. Here is the algorithm: ... 2answers 60 views ### Show that: t_{n-1}+t_n=n^2 How to can prove that :$$ t_{n-1}+t_n=n^2.$$where t_n is number of points with integers coordinates in a square isosceles triangle of side n: http://i45.tinypic.com/ndse9.jpg 2answers 564 views ### Change-making problem - counterexample for greedy algorithm Let D be set of denominations and m the largest element of D. We say c is counterexample if greedy algorithm is giving answer different from optimal one. I found statement that if for given set ... 7answers 148 views ### is there a relation between divisors(n) and divisors(n^2)? Can we generate divisors(n^2) in case that we already have divisors(n) ? or at least can we predict how many integers are in divisors(n^2) ? while divisors(n) is the list of integers (not ... 0answers 39 views ### Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ... 3answers 134 views ### Pattern in Fermat Factorization I have the Fermat Factorizations of n = pq where p and q are primes. I am trying to find a formula/pattern for the number of cycles required to perform the factorization in terms of n, p, q. ... 2answers 172 views ### Running Time for Fermat's Factorization Algorithm Let p and q be odd primes s.t. p<q and n= pq. How many cycles will Fermat's Factorization produce for n = pq? Here is some sample data I iterated: (I am having trouble solving for an ... 2answers 517 views ### Expressing a Non Negative Integer as Sums of Two Squares I'm writing a code in C that returns the number of times a non negative integer can be expressed as sums of perfect squares of two non negative integers. ... 1answer 59 views ### Show that we can compute the product n = \Pi_in_i in time O(len(n)^2) for given integers n_1,…n_k with each n_i> 1. Show that we can compute the product n = \Pi_i\ n_i in time O(len(n)^2) for given integers n_1,...n_k with each n_i> 1. I know that we can compute ab in time O(len(a)len(b)) courtesy ... 2answers 85 views ### Find y=\sqrt{x} where x and y positive integers in polynomial time? Let x be a positive integer and let y be a real number such that$$y=\sqrt{x}$$Objectives: If y is an integer, find it in polynomial time. If y is not an integer, prove that there is no ... 1answer 330 views ### Modular Multiplicative Inverse & Modular Exponentiation Equation I was solving a problem containing that equation.$$key=(\sum_{K=0}^n\frac{1}{a^K})\mod m$$Given: 1 \le a \le 2,000,000,000 0 \le n \le 2,000,000,000 2 \le m \le 2,000,000,000 a and m ... 0answers 102 views ### Serret's algorithm and Fermat's theorem on sums of two squares Serret's algorithm(1848) proved Fermat's theorem on sums of two squares as follows: p\equiv1\pmod4, u^2+1=kp, 1\leqslant u<\frac{p}2 r_0=p, r_1=u, then Euclidean Algorithm$$r_0=q_1r_1+r_2$$... 1answer 54 views ### Determing if two k subsets are disjoint given the product of their elements Consider the following problem (phrased with the use of a black box). You choose n numbers X = \{x_1,\ldots,x_n\} and pass it to a black box that returns a list Y = \{y_1,\ldots,y_m\} where ... 2answers 236 views ### Why does the 2's and 1's complement subtraction works? The algorithm for 2's complement and 1's complement subtraction is tad simple: 1. Find the 1's or 2's complement of the subtrahend. 2. Add it with minuend. 3. If there is ... 0answers 86 views ### Does the shifting square root method work for non-integer bases? Under "methods of computing square roots", Wikipedia states that the digit-by-digit calculation method, of which the shifting n^{th} root algorithm is a generalization, works for all bases, but the ... 0answers 49 views ### Minimal fractional representation in \Bbb Z/p\Bbb Z I arrived to needing an algorithm for the following subproblem while solving a more complex problem. It seems it should be a very standard algorithm, but my number theory isn't too fresh so I haven't ... 1answer 197 views ### Finding the radical of an integer Given a number x = p_1^{e_1}\cdots p_n^{e_n} with different primes p_i and exponents e_i \ge 1, is there an efficient way to find p_1\cdots p_n? I ask this because for polynomials it's ... 1answer 194 views ### \alpha x^2+\beta y^2=\gamma solvable over \mathbb Q iff ax^2+by^2=z^2 solvable over \mathbb Z with coprime x,y,z? I want to understand an algorithm from [1] to solve$$\alpha x^2+\beta y^2=\gamma \text{ over } \mathbb{Q} with $\alpha, \beta, \gamma\in\mathbb{Q}$. As far is I understood the process the ...
Let $P(x)$ be the total number of digits '$4$' in the number $x$. For instance: $X= 19$: $P(19)=0$ since $19$ does not contain any digit $4$ $X=1234$: $P(1243)=1$ $X=441240$: $P(441270)=3$ ...