0
votes
1answer
26 views

Is there a quick way to obtain $a,b$ in $ax+by = z$ where $x,y,z$ are fixed and $x+1 = y$?

Suppose that all numbers are postive integers. Let $x,y,z$ be fixed/given and $x+1=y$. Then would there be a quick way to find set of solutions $(a,b)$ that satisfy $ax+by=z$? "Quick" would be ...
0
votes
0answers
2k views

Minimum moves to reach destination [closed]

Moderator Note: This is a current contest question on codechef.com. Given that a person is standing at $(0,0)$ and initially look in direction of $X$-axis. Now he can walk only at right angle to ...
0
votes
0answers
42 views

Probability with dice sum K

Alice rolls a N faced die M times. she adds all the numbers she gets on all throws. What is the probability that she has a sum of K. A N faced die has all numbers from 1 to N written on it and each ...
0
votes
1answer
51 views

Count pairs with odd XOR

Given an array A1,A2...AN. We have to tell how many pairs (i, j) exist such that 1 ≤ i < j ≤ N and Ai XOR Aj is odd. Example : If N=3 and array is [1 2 3] then here answer is 2 as 1 XOR 2 is 3 ...
0
votes
0answers
56 views

2 player team knowing maximum moves

Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know. And also find out how ...
0
votes
2answers
347 views

Finding Coprime triplets

Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor. Example : Let N=4 ...
1
vote
3answers
71 views

Is there an algorithm help us to write each even number as sum of primes numbers? [closed]

1) Is there an algorithm help us to write each even number as sum of primes numbers : for example :$4=2+2$ $8=3+5$ where : $3,5,2$ are primes 2) why we couldn't writing all odd numbers as sum of ...
2
votes
0answers
31 views

Tau Summatory Function

It is well known that the divisor summatory function can be calculated in $O(x^{1/2})$ via $$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^{\lfloor \sqrt{x}\rfloor} \lfloor\frac{x}{k}\rfloor - \lfloor ...
0
votes
1answer
39 views

Minimum AND operation on subset

Given an array of size N . Let's create all the subsets of this array which contain at least 2 elements. Now, operate AND over the elements of each subset, and store the results in a new array. I ...
2
votes
0answers
203 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
33 views

Algorithms for finding the multiplicative order of an element in a group of integers mod m

What are some algorithms for finding the multiplicative order of an element in a group of integers mod m, besides the naive one?
1
vote
0answers
21 views

number set with non-adjacent digits

I'm not sure such thing exists, or even if I'm asking for a valid thing, but I'll do my best describing it. At least the thing I want is similar to Gray code, so should be valid. So, I want to know ...
0
votes
1answer
56 views

Even Odd counting

Given an integer $Q$ and an array $A$ of size $N$, can we figure out the answer to each of the $Q$ queries? Each query contains two integers $x$ and $y$, and we need to find whether the value ...
0
votes
1answer
34 views

What are the smallest numbers $n$ such that $\dfrac{d(n)}{\ln(n)} \geq k$ where $d(n) = \sigma_0(n)$ is the number-of-divisors function?

I have calculated $\dfrac{d(n)}{\ln(n)}$ on a few highly composite numbers up to 5040. Here is what I got: $\dfrac{d(120)}{\ln(120)} = 3.3420423$ $\dfrac{d(360)}{\ln(360)} = 4.0773999$ ...
1
vote
1answer
29 views

Generalization of Jacobi symbol for higher powers?

Let $n$ be an odd positive integer of unknown factorization, and let $x$ be relatively prime to $n$. The Jacobi symbol $\left(\frac{x}{n}\right)$ gives me partial information on whether $x$ is a ...
0
votes
4answers
75 views

Algorithm for Fundamental theorem of arithmetic

What is a good algorithm for decomposing a number into a product of primes? What would be its time complexity?
1
vote
1answer
30 views

Algorithm for checking Prime Power

Suppose we are given some arbitrary positive integer. How can we check whether the integer is a prime power? Brute force would be very inefficient in this case.
-11
votes
1answer
115 views

How many divisors do these big superior highly composite numbers have? [closed]

448806242393308800 18401055938125660800 791245405339403414400 37188534050951960476800 185942670254759802384000 9854961523502269526352000 581442729886633902054768000 1162885459773267804109536000 ...
1
vote
1answer
84 views

How many regulars do the primorials 223092870 and 6469693230 have?

Regulars = Divisors + Semidivisors http://global.britannica.com/EBchecked/topic/496213/regular-number So for example: 6 has 5 regulars: 1, 2, 3, 4, 6. 8 has 4 regulars: 1, 2, 4, 8. 9 has 3 ...
3
votes
1answer
36 views

Number of ways to color such that one color always leads

There are n boxes drawn out in a line. We have two colors, blue and red. We start coloring boxes from left to right. At any instant we want to color the boxes in such a way that number of boxes ...
1
vote
1answer
44 views

Efficient factorization of numbers with unique prime factors

I need a factorization algorithm for numbers of the form $n = p_{1}p_{2}\cdots p_{k}$ with $p_i \neq p_j$ for $i \neq j$ and $p_j \in \{p : p \mbox{ is a prime and } p \leq P_s\}$, where $P_s$ is the ...
0
votes
1answer
35 views

Number Triangle pattern

I have a number triangle as follows: $$\begin{array}{|c|c|c|} \hline 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline 0 ...
8
votes
3answers
198 views

Finding 1000th 5-smooth number

A number is 5-smooth if its only prime factors are $2,3$ or $5$. Example: $$1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots$$ Interesting thing is that as they become larger and larger, they are ...
1
vote
0answers
26 views

Using $ \gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$ for GCD?

It should be true that $\gcd(a,b) = \gcd(b,r) $ if $ a \equiv r \pmod b$. But: How can I use this equality to compute the GCD of $a$ and $b$? It seems as if $r$ is of the form $r = k\cdot b + s$ ...
0
votes
2answers
350 views

Game of cards and GCD

Alice and Bob play the game. The rules are as follows: Initially, there are n cards on the table, each card has a positive integer written on it. At the beginning Alice writes down the number 0 on ...
1
vote
1answer
23 views

Integer-handling alg0rithms

anyone has a good reference (books, websites) on optimised algorithms for integer handling - i am thinking about factorisation, primality, and number-theoretical function related problems. Optimised ...
1
vote
2answers
123 views

Shortest path between three nodes in a graph

I know Dijkstra's algorithm to find the shortest way between 2 nodes, but is there a way to find the shortest path between 3 nodes among $n$ nodes? Here are the details: I have $n$ nodes, some of ...
9
votes
0answers
74 views

Algorithm to find primes up to $n$ in $O\left(\frac{n}{\log n}\right)$?

Consider the problem of given an integer $n$, generating a list of the primes not greater than $n$. An optimized version of the Sieve of Eratosthenes can do such task in $O(n)$, while the more modern ...
2
votes
1answer
38 views

How to know if the mth root of n is an integer?

If n can be represented in binary as a x bit integer, is there any algorithm such that we can determine if the mth root of n is an integer in time polynomial of x ?
0
votes
1answer
78 views

Count Integers satisfying the conditions

Given some constraints ,I need to find possible ways that these conditions are satisfied. I need to find four POSITIVE integers a,b,c,d such that ad-bc > 0 and also a+d=N for a given value of N. How ...
14
votes
2answers
235 views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
7
votes
1answer
470 views

Count expressions with 1s and 2s

Moderator's note (20.03.2014) This question is from on on-going contest. Per usual protocol the question will be locked and current answers hidden until the contest ends. Given atmost X number ...
1
vote
1answer
36 views

Reducing simultaneously a pair of fractions $\frac{a^2}{b},\frac{ a^3}{c}$ using only gcds

Given three positive integers $a,b,c$ and I want to find the smallest positive integers $a', b', c'$ such that $$ \frac{a^2}{b} = \frac{a'^2}{b'} \quad \text{and} \quad \frac{a^3}{c} = ...
7
votes
3answers
122 views

Knight move variant: Can it move from $A$ to $B$

Given a $N\times N$ "chess" board (Let $N = 10^{100}$) and a knight at $(0,0)$. Can the knight go to the position $(x, y)$ with jump $[a, b]$ moves ? jump $[a, b]$ mean: the knight on ...
0
votes
1answer
161 views

Maximum Number with this condition satisified

Given an array $A$ of $N$ elements $A[1],A[2],A[3]...A[n]$, I need to find maximum element in the array such that $GCD(G,A[i]) > 1$ for given $G$ and $1\leq i\leq N$. Example : Let we have $N=6$ ...
1
vote
3answers
286 views

Finding set of non recurring non terminating decimals

I need to find a set of two Integers P and Q such that ...
1
vote
0answers
25 views

Minimum moves to find the Ball in the Large Grid

Given N*M grid in which one cell contains a ball and all other cells are empty in all other boxes i am provided with one of these 8 directions towards the right position of ball.These are : ...
0
votes
1answer
31 views

Check if condition holds

I am given a equation 2^i - 2^(i-j) = q/p I need to tell if this equation is satisfied for given q and p for any value of i and j . Like if q=3 and p=1 then the answer would be "YES" as for ...
1
vote
1answer
52 views

Check if a series can be made or not

Given an infinite geometric sequence $S=\{1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots \}$. I need to tell whether for given fraction $p⁄q$, we can select an infinite geometric sequence $R$, such ...
-2
votes
2answers
145 views

Even or Odd for factorial

Moderator Note: This is a current contest question on codechef.com. Given $N$ and $M$ I need to tell whether $\left\lfloor \large\frac{N!}{M} \right\rfloor$ is even or odd.How to do this ...
0
votes
1answer
47 views

Number of ways to make grid

I need to construct a L x 3 grid as shown below But i can use only two shapes to make it which are : Here L is the number of small square boxes in each row. I can rotate the shapes as I want. I ...
2
votes
0answers
51 views

Expected error due to the tablemakers' dilemma

[note: to me, this does not seem like a question for m.se, but on mathoverflow it has been retroactively closed, with very little indication of why or what might be corrected... and waiting for ...
3
votes
2answers
238 views

Existence of algorithm for determining if a given number is rational or not

As far as I understand, it is not necessarily a easy thing to prove that a real number is rational or not. For example, according to http://mathworld.wolfram.com/e.html "$e+\pi \in \mathbb{Q}$?" is ...
1
vote
1answer
35 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
0
votes
1answer
22 views

Check if sum is possible

Given a range $[L,R]$ I need to find weather a sum $S$ can be made by taking any number between this range i.e $L, L+1, L+2,\dotsc, R$ any number of times EXAMPLE: If $S=5$ and $L=2$ and $R=3$ then ...
0
votes
1answer
32 views

How many $Xs$ that makes $\gcd(X,N)\ge M$

I get two integers, $X$ and $N$, ($1\le X \le N$). Let $\gcd(X,N)$ be the greatest common divisor of $X$ and $N$. Given an integer $M$, how many $Xs$ that make $\gcd(X,N)\ge M$? Are there any ...
0
votes
2answers
143 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
3
votes
1answer
92 views

Expected Value of this function

Let’s consider a random permutation p1, p2, …, pN of numbers 1, 2, …, N and Function F is calculated as F=(X[2]+…+X[N-1])^K, where ...
0
votes
2answers
62 views

Find $n$ and $k$ such that maximum element is minimum

Given $a_1, a_2, a_3, \ldots, a_m \in \mathbb {Z}$. How do I find $n \in \mathbb Z, k \in \mathbb N$ such that $$\max \{|n - a_1|, |n+k-a_2|, |n+2k-a_3|,...\}$$ is minimum? The original problem was ...
0
votes
1answer
85 views

Show that $gcd(x,y)$ and $z = lcm(x,y)$ is primitive recursive

For the $gcd(x,y)$ we note: $gcd(x,0) = x$ $gcd(x,succ(y)) = gcd(succ(y),mod(x,succ(y)))$ $succ(x)$ and $mod(x,y)$ are both primitive recursive, so $gcd(x,y)$ must be as well. $z = lcm(x,y)$ if ...