Questions tagged [number-theory]

Number theory is that branch of mathematics that investigates the properties of numbers, typically whole numbers.

number-theory
Filter by
Sorted by
Tagged with
0 votes
1 answer
186 views

How to efficiently calculate a^k mod m

How can I efficiently calculate ak mod m where a,k,m are very large numbers and k might be up to 109 or more, a might be up to 106. Here a is a prime but k and m might not be primes. Is my only option ...
Mike Reddington's user avatar
0 votes
1 answer
56 views

Hexadecimal Convention in Memory

a super stupid question: I have an integer in my code, which occupies 4 bytes ( of course ), this information in memory is represented as a pack of four hexadecimal of two digits, for example int x = ...
Evethir's user avatar
  • 41
1 vote
1 answer
158 views

How do I get the counter clockwise value using the modulo operator?

Let's say we have a 24 hour clock where all time is represented in minutes. That gives us 24 * 60 possible time points from 0 hours to 24 hours. The clockwise distance between two time points T1, T2 ...
Mutating Algorithm's user avatar
0 votes
1 answer
533 views

LeetCode 264. Ugly Number II - custom Ugly Number finding algorithm [duplicate]

I am trying to solve the LeetCode ugly number challenge II. I came up with an algorithm of my own, seems working in theory but does not. I want to know why. I implemented this in Java but I write in ...
Ghostpunk's user avatar
  • 197
1 vote
2 answers
303 views

Linear Diophantine Equation - Finding the number of solutions and the solutions in a given interval

I am learning Linear Diophantine Equation from cp algorithm. Overall I understood the theory. But I am facing problem in the implementation. Help me out by providing a test case where both ...
Manan's user avatar
  • 424
0 votes
1 answer
125 views

Can I calculate modulus of large number by taking modulus of each digit and taking sum?

The problem is, I got all digits of a very large number, I need to find whether it is divisible by 3. I tried my approach which I suppose is wrong but I don't know why This is my approach for example ...
Anandha Krishnan Aji's user avatar
1 vote
2 answers
1k views

Pisano Period length finding

Can 0 and 1 come together in other positions of the Pisano Period except the first two positions? I am trying to solve a problem where it’s needed to know the Pisano Period length. So I was thinking ...
Mubin Likhon's user avatar
0 votes
0 answers
62 views

number theory application on java

I want to simplify fractionals in an efficient way by using number theory. How to propose an efficient approach to simplify the numbers? int gcd = 1; for (int i = 1; i <= a &&...
stardust's user avatar
0 votes
1 answer
65 views

How to generate distinct combinations from a given array such that every digit in sequence is also distinct

I am trying to generate a sequence of length "k" from a given array of "n" elements such that every token/digit in "k" appears only once. For Eg. if my input array is {1,2,3,4,5} and "k=4" then using ...
Anand's user avatar
  • 371
1 vote
1 answer
136 views

Why is my algorithm about Fermat primality test so slow?

I am learning Number theory. Now, I want to write a program that perform Fermat primality test. First, I write a modular square algorithm: #modular_square.py def modular_square(a, n, m): res = 1 ...
Land's user avatar
  • 191
1 vote
0 answers
219 views

How to compute a/b mod P, P is a prime number?

I have been searching an answer for this question on various sites. I can understand all the basic rules of modular arithmetic until this bad guy comes in. Recently I have been suggested this page for ...
Hemanth Varma S's user avatar
1 vote
1 answer
564 views

Finding the number of even perfect square proper divisors of a given number N

I tried to solve a question on HackerRank (Problem Link: https://www.hackerrank.com/challenges/mehta-and-his-laziness/problem) which involves calculating the number of even perfect square proper ...
user299560's user avatar
0 votes
1 answer
52 views

Floating point exception: 8 on Smith number check

So I have written a code to check if a long int number is Smith, but I keep getting Floating point exception: 8, no matter what size do I fix my variables in. Not quite sure what I am missing. #...
Anđela Todorović's user avatar
0 votes
2 answers
263 views

For a given value of n and m, find fib(n) mod m where n is very huge. (Pisano Period)

Input Integers 'n' (up to 10^14) and 'm'(up to 10^3) Output Fib(n) modulo m Sample Cases Input: 239 1000 Output: 161 Input: 2816213588 239 Output: 151 Hint given in Question As it is not ...
hack3r-0m's user avatar
  • 740
0 votes
0 answers
99 views

The Two Water Jug Puzzle

I am trying to solve the two WATER JUG PUZZLE using euclidean algorithm and Diophantine equation. let gcd(m,n) = g using euclidean aldortihm we get X' and Y' such that mX' + nY' = g for mX + nY = d ...
keemahs's user avatar
  • 908
0 votes
0 answers
38 views

Fast integer power of nine

I need to calculate 9^n where n is a natural number. I used binary exponentiation, but addition chain is not optimal. Also there exists an optimal solution, but it's proven to be NP-complete and is ...
Joshua Jakowlew's user avatar
0 votes
0 answers
278 views

Given two integers N and M. How to check if N can be expressed as the sum of M raised to different integer powers?

I have two integers N and M. I have to check if N can be expressed as the sum of M raised to some distinct non-negative integer powers. Example: If N = 10 and M = 3, then answer is YES. Because, 10 ...
Yeasin Mollik's user avatar
4 votes
1 answer
481 views

Is there a way to optimize this code for finding the divisors of a number?

I've written a program in Julia to compute the divisors of a number n efficiently. The algorithm is original (as far as I know), and is loosely based on the Sieve of Eratosthenes. It essentially works ...
Art's user avatar
  • 183
-4 votes
2 answers
2k views

Is there an integer A such that it has exactly X positive integer divisors and exactly K of them are prime numbers?

I need to determine whether there is an integer A such that it has exactly X positive integer divisors and exactly K of them are prime numbers. We will be given T testcases. e.g T = 1, X = 4 and K =...
Harry Potter's user avatar
-1 votes
1 answer
225 views

How do I calculate a number if its number of factors (N) and number of prime factors (K) are given?

How do I calculate a number if its number of factors (N) and number of prime factors (K) are given? Example: if N = 4 and K = 2 is given then the only possible value will be 6 Explanation : of the ...
Alex Ed's user avatar
  • 41
1 vote
1 answer
167 views

How to find the product of all the possible subarrays in an array in linear time?

Suppose I have an array A[4] = {5,6,2,4} The sub-arrays are: {{5}, {6}, {2}, {4}, {5, 6}, {6, 2}, {2, 4}, {5, 6, 2}, {6, 2, 4}, {5, 6, 2, 4}} I need the array containing product of each sub-array as ...
Mohil Khare's user avatar
2 votes
2 answers
66 views

Trouble with modular exponentiation

I am trying to solve a problem where we have to output the the last digit of the given number n^p. int modularExponentiation(int n, long long p, int m){ if(p == 0) return 1; if(p & 1) ...
Pranav Venkata's user avatar
0 votes
2 answers
625 views

Find four factors of a number such that their product is maximum and their sum is the original number

Given number of test cases T and an integer N, you need to find four integers A,B,C,D , such that they're all factors of N(A|N,B|N,C|N,D|N), and N=A+B+C+D. Goal is to maximize A * B * C * D. If it's ...
dark_prince's user avatar
0 votes
1 answer
164 views

Time and Space Complexity for PCP and Halting Problem

So PCP is semi-decidable and undecidable and Halting Problem is undecidable. Is it even possible to name a time complexity for them, like NP or expTime? And what about space Complexity: are they in ...
user avatar
1 vote
1 answer
33 views

Trying to find cause of possible overflow in my approach when trying to solve

I am solving a question Find total numbers which are less than equal to A and are divisible by both B and C. I have written following function to compute the same public int solve(int A, int ...
Rishi Prakash's user avatar
-4 votes
1 answer
877 views

Asking ideas of a codeforces problem (Problem-483A Counterexample)

Problem link: http://codeforces.com/problemset/problem/483/A You need to find three numbers (a, b, c), such that l ≤ a < b < c ≤ r, pairs (a, b) and (b, c) are coprime, and pair (a, c) is not ...
toukir_ahmed's user avatar
0 votes
2 answers
495 views

Armstrong numbers. Fails for 153

A C++ program to compute and display all Armstrong numbers (numbers such that the sum of each of the digits raised to the power of the number of digits equals the number) between 100 and 999. The ...
Al2110's user avatar
  • 576
1 vote
1 answer
208 views

Formula for reliably (over-)estimating the number of primes in interval [m, n]?

For quite a while now I've successfully used a simple function that reliably (over-)estimates the number of primes up to a given n, for example for allocating space to hold the primes. Now I'm looking ...
DarthGizka's user avatar
  • 4,497
4 votes
2 answers
3k views

Finding Bezout coefficients via Extended Euclidean Algorithm on Array of Arbitrary Length

What I want, big picture: I want to know how to mimic Mathematica's ExtendedGCD[...] functionality in Java. Info about that function can be found here, but I'll describe it briefly for completeness. ...
cstover's user avatar
  • 171
1 vote
0 answers
59 views

fast powering algorithm is slower than native powering - python

I've been trying to implement the fast powering algorithm into python code, but it turned out to be slower than the native approach, where's the problem? import timeit test = """ def Power(base, ...
Boud Math's user avatar
1 vote
3 answers
850 views

minimum greater number with different adjacent digits

We are a given number n 1<=n<= 10^18, and we have to find minimal number that's greater than n and also it's adjacent digits are different, for example for 1000, answer is 1010, for 99, answer ...
user avatar
0 votes
0 answers
138 views

how to find coefficients of a polynomial with roots 1 to n

I have a polynomial with roots 1,...,n. I want to find all its coefficients or the sum of products of all combinations taking i at a time for i in 1,...,n first n natural numbers. I'm not able to get ...
Deepesh Thakur's user avatar
0 votes
1 answer
664 views

Printing Carmichael numbers in a given limit

I'm trying to list all of the Carmichael numbers under 10000, however, I think I have issue with the print_carmichael function. For some reason, it does not print all of the n values when the ...
lowlypalace's user avatar
2 votes
1 answer
260 views

Is there a method/Algorithm to generate unique integers from prime factors of a given number?

I'm trying to solve the following question https://open.kattis.com/problems/listgame2 and I am successfully able to generate all the prime factors of a given number but the problem demands that I need ...
Sharan Magavi's user avatar
0 votes
1 answer
79 views

In PARI/GP in function FACTOR the -1 is a bug or means somthing else?

First run the function b(n): ? b(n) = lcm(vector(n, i, i))/n After function c(n): ? c(n)=sum(j=1,n,sum(i=1,n,(-1)^(i+j)/(i+j-1))) Last run d(n): ? d(n)=factor(denominator(c(n))/b(n))~ and test ...
Dimitris Valianatos's user avatar
-1 votes
1 answer
228 views

miller-rabin test don't work for 252097800623

I'm trying to write miller-rabin test. I found few codes such as: https://www.sanfoundry.com/cpp-program-implement-miller-rabin-primality-test/ https://www.geeksforgeeks.org/primality-test-set-3-...
Roman Kwaśniewski's user avatar
0 votes
1 answer
356 views

Schonhage-Strassen Multiplication implementation error

I am attempting to implement the Schonhage-Strassen multiplication algorithm using NTT, and am running into a problem where the final resulting vector is not actually equal to what it should be. For ...
user2649681's user avatar
0 votes
1 answer
190 views

Finding smallest number N, having k trailing zeroes in factorial of N

I got a problem about finding the smallest N, where N! contains exactly k trailing zeros. I've got an idea of finding it through binary search from here - Finding natural numbers having n Trailing ...
fardinabir's user avatar
0 votes
0 answers
250 views

RSA Prime Generation using Provable vs Probable Prime Construction

I am trying to implement RSA prime generation for P and Q based on FIP186-4 specification. The specification describes two different implementations: Section 3.2 Provable Prime Construction vs. ...
user avatar
-1 votes
2 answers
2k views

How to get all the prime numbers from 2 to 10^9? [sieve of eratosthenes is not working since the range is too long]

I am working on a program which prints the number of pairs of prime numbers (within a range L and R) whose difference is 6, where 2 <= L < R <= 10^9. eg., L=2 R=20 Ans: 4 Explanation: 4 ...
Sannidhya Raj Chauhan's user avatar
-3 votes
1 answer
69 views

How to count all integers less than a given integer and having two contigous digits as y?

Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
user avatar
0 votes
1 answer
152 views

Project Euler #23 Optimization

Non-abundant sums Problem 23 A number n is called abundant if the sum of its proper divisors exceeds n. Find the sum of all the positive integers which cannot be written as the sum of two abundant ...
Heedy_A.'s user avatar
-2 votes
1 answer
81 views

What is the fastest way to determine n^m = m^n if m != n?

It's one of the questions from the practice section in hackerearth. We need to determine whether m^n = n^m. It is trivial when n = m, so we focus on m != n. 1 <= m, n <= 10^10000 What I have ...
chelsea's user avatar
  • 185
0 votes
0 answers
82 views

I don't understand the how prime numbers are calculated and modPow function is working in the following code

A Magic Fraction for N is one that has the following properties: It is a proper fraction (The value is < 1) It cannot be reduced further (The GCD of the numerator and the denominator is 1) The ...
divyajyotiuk's user avatar
-4 votes
2 answers
95 views

Why is this failing for just a corner case? Question link-https://www.hackerearth.com/problem/algorithm/chandu-and-his-interns/description/#c190148

Why is this failing for just a corner case? Question link-https://www.hackerearth.com/problem/algorithm/chandu-and-his-interns/description/#c190148 It ran fine for all the other cases. I took all the ...
Reetik Raj's user avatar
1 vote
3 answers
2k views

Is it possible to test whether a number is prime or not in O(logn)?

I have been reading a competitive programming book for one month. The book is written by one of the world finalists of our country (Bangladesh). Point to be noted, the book is written in our native ...
Kazi Ziaul Hassan's user avatar
1 vote
3 answers
870 views

Counting distinct digits

Is there any efficient way to find out the count of distinct digits from a given number in constant time or O(Logn)? Suppose n = 1234 the count should be 4 (As there are 4 distinct digits) if n = ...
akhil's user avatar
  • 1,769
-1 votes
1 answer
3k views

Split Array in two parts such that sum of gcd of both parts is maximum

Split a array into two non empty parts such that sum of gcd of first part and second part is maximum I put largest element in first part and second largest in second part and then starting from the ...
FlyingBeast's user avatar
5 votes
0 answers
516 views

Algorithm for finding largest square divisor

Given a positive integer n, find largest integer a such that a*a divides n. If you know the factorization of n, it's fairly trivial. The question is, can it be done asymptotically faster than ...
priner's user avatar
  • 51
0 votes
2 answers
68 views

Algorithms for only compressing static data?

What algorithms are designed to compress static data? For example, I have a input string of "Hello world!" I want to make a library that will JIT compile a set of compression and decompression ...
Taylor Sasser's user avatar

1 2
3
4 5
10