0
votes
2answers
65 views

Finding all possible pairs of integers $(a,b)$ such that $a^b=n$. [duplicate]

Given an integer $n$, how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable.
2
votes
1answer
49 views

need help in number theory problem

Given a number $n$. I need to find the largest $q$ such that $q^2$ divides $n$. I need the fastest method to find $q$. $q$ can be any number prime or composite. At present I am factorizing the number ...
1
vote
1answer
51 views

Maximise the smallest piece of grid

Given a big rectangular chocolate bar that consists of n × m unit squares. We wants to cut this bar exactly k times. Each cut must meet the following requirements: ...
-1
votes
1answer
32 views

Who will be last [on hold]

There are n children in school and teacher is going to give some candies to them. Let's number all the children from 1 to n. The i-th child wants to get at least a[i] candies. Teacher asks children ...
3
votes
1answer
37 views

Partial sums of Pillai's function

Pillai’s arithmetical function (gcd-sum function) is defined by $$ P(n) = \sum_{k=1}^n\gcd(k,n) $$ Let $\sum_{n\leq x}P(n)$ be summation of all values of P for all $n$ up to given $x$. I dervied that ...
-1
votes
1answer
176 views

Number of ways to win chocolate game

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
0answers
46 views

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ primes. What are the first values of $U(n)$?

$U(n) =$ the smallest strictly positive integer $k$ such that $2^k-1$ is divisible by the first $n$ prime numbers (except for the first prime number: $2$). What are the first values of $U(n)$ up to ...
0
votes
1answer
35 views

Parity of number of factors up to a bound?

Consider $b,n\in\mathbb{N}$ where $b\leq n$. We want to find the parity (ie. odd or even) of the number of divisors of $n$ that are $\leq b$. The question is to find a fast algorithm to find that ...
1
vote
1answer
43 views

Normal number generator with digit extraction algorithm?

Are there any known ways to define an absolutely normal number (or very likely normal) number, which posses digits that can be extract via algorithm? I want to find numbers like pi that are normal and ...
0
votes
1answer
27 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
3answers
2k views

Minimum moves to reach destination [closed]

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 previous move. Like if he has to go to $(3,3)$ then $6$ moves are ...
0
votes
0answers
50 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 ...
1
vote
1answer
64 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
57 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
354 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
96 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
35 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
205 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
34 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
22 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
60 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
38 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
31 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
3answers
84 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
32 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.
1
vote
1answer
85 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
36 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
206 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
356 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
134 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
76 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
243 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
471 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
123 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
335 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
152 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 ...