1
vote
0answers
31 views

Does a generalization of the Teichmuller-character for non-prime arguments exist?

Rereading an older article on Fermat-quotients in which I'd applied some p-adic-rationale I find now, that my method for the representation of bases $b$ which allow high fermat-quotients ...
0
votes
1answer
84 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
1
vote
1answer
41 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
-1
votes
1answer
244 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
0
votes
1answer
46 views

Count ways to make K joules of energy [closed]

A scientist of NASA has discovered a secret formula, according to which if a bottle of chemical A occurs to the immediate left of a bottle of chemical B in a straight line arrangement, they produce 1 ...
4
votes
0answers
104 views

Will this algorithm stop before time?

For every $n \in \mathbb N$, let's define $a_0 = 0$, $$\begin{cases} a_{i+1} = 2a_i + 1 \pmod {2^n}, &\text{if it never appeared before} \\ a_{i+1} = 2a_i \pmod {2^n},& ...
-1
votes
0answers
39 views

Find ways to make sum N from K type of coins

Given K type of coins with each denominations between 1 to 15. Also K <=15 and now we need to make sum N with help of these coins provided each of given denomination coins are infinite in number. ...
1
vote
0answers
33 views

Divisible 4 for every different number?

My formula is for ABC 3 digits number; 100A + x*B + y*C. What should coefficient of B and C be for everytime different result for different number? (Result number ) mod 4 has to be zero. For ...
0
votes
0answers
47 views

How can we find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits?

If $n$ and $m$ extremely large (1000 digits) and $1 <\frac{2^m}{e^n} < e$, how can we create an effective algorithm to find $\frac{2^m}{e^n}$ with an accuracy of $10$ decimal digits (10 digits ...
-2
votes
2answers
135 views

How to find sum of 4th power of n numbers mod m [closed]

How can i calculate $1^{4} + 2^{4} + 3^{4} + 4^{4} .....+n^{4} \pmod m$ where $1 \le m \le 10^5$ and $1\le n \le 10^{20}$. I can't use the formula here because it will Overflow the limit of long long ...
2
votes
1answer
53 views

Count ways to make total coin value [closed]

For any non-negative integer K, suppose we have exactly two coins of value 2^K (i.e., two to the power of K). Now we are given a long N. We need to find the number of different ways we can represent ...
2
votes
0answers
50 views

Minimise total cost and count ways [closed]

A country has a + b cities located in a row, which are uniformly placed. There are two large telecommunication operators in this country. The first operator will ...
1
vote
1answer
49 views

Residue class of a huge repunit modulus a huge number

Given a number with only 1: X = 1111...1 (N times 1 in total), and another number M, I want ...
0
votes
1answer
61 views

Count numbers with prime digit

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) in it. Now N can be upto 10^18.What is the best approach to solve this problem. Example : Let ...
0
votes
2answers
103 views

Modulus of large powers

Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$. We need to find if $X \mid ...
1
vote
0answers
59 views

Integer partitions without rotated solutions?

I'm searching for an algorithm to determine a list of all integer partitions of a number $n$ into a fixed number $m$ of summands (say $n=6$ and $m=4$), for instance to be stored into a list of ...
1
vote
0answers
50 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 ...
3
votes
2answers
106 views
3
votes
1answer
283 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
4answers
148 views

The fastest way to count prime number that smaller or equal N

I want to count all prime numbers that existing in N but I don't know how to count. Can any one tell me how to count prime numbers that are smaller than or equal to N in mathematics formal?
1
vote
1answer
37 views

Digit wise modulo for calculating power function for very very large positive integers

I am writing a code to calculate $P^Q$ where $P$, $Q$ are positive integers which can have number of digits up to $100000$. I want the result as $r = P^Q \pmod{10^9+7}$, where $10^9+7$ is a prime ...
4
votes
1answer
55 views

How to check if $\text{position}\left(\frac{a + b} 2\right )$ is in range $\text{position}\left(a\right )$ and $\text{position}\left(b\right )$

Given a permutation of $n$ number $1, 2, 3,\dots,n$. How to check if it is exist $a,\ b$ with the same parity such that $\frac {a + b} 2$ is between $a, b$. How to solve this problem efficiently ? ...
0
votes
0answers
284 views

Cleaning minimum tables

John has been newly hired to clean tables at his restaurant. So whenever a customer wants a table, he must clean it. But John happens to be a lazy boy. So in the morning, when the restaurant is ...
0
votes
0answers
579 views

Count arrangment such that each person wear different tshirt

Few friends are going to a party. Each person has his own collection of T-Shirts. There are 100 different kind of T-Shirts. Each T-Shirt has a unique id between 1 and 100. No person has two T-Shirts ...
2
votes
1answer
69 views

Finding an $n$ such that $n^2 \equiv -1 \mod p$

What is an efficient algorithm to find the first number $n$ such that $n^2 \equiv -1 \mod p$ for a prime $p$, if such an $n$ exists? Is there anything better than the brute-force approach up to $p-1 ...
2
votes
2answers
37 views

Flip cards to get maximum sum

Given N cards where if ith card has number x on its front side then it will have -x on back side and a single operation that can be done only once that is to flip any number of cards in consecutive ...
1
vote
1answer
46 views

Find extra work done by Bob

Alice has challenegd Bob game of N puzzle.N puzzle is played on N*N grid with each cell containing distinct numbered tile from 1 to N*N-1 Except one which is empty cell and represented as 0. Move ...
0
votes
2answers
115 views

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

Given a large integer $n$ (could be as large as $10^{18}$), how can I find all possible pairs of integers $(a,b)$ such that $$a^b=n.$$ A fast algorithm is preferable. The question How to quickly ...
2
votes
1answer
52 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
66 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
42 views

Who will be last [closed]

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
42 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
186 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
47 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
50 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
51 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
32 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 ...
1
vote
1answer
82 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
58 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
380 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
144 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
46 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
44 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
219 views

Count swap permutations

Given an array A = [1, 2, 3, ..., n]: ...
0
votes
1answer
53 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
26 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
61 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
39 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
35 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 ...