number-theory Questions
3
Solved
I have to compute efficiently a^^b mod m for large values of a,b,m<2^32
where ^^ is the tetration operator: 2^^4=2^(2^(2^2))
m is not a prime number and not a power of ten.
Can you help?
Moss asked 8/6, 2015 at 15:46
7
Solved
Given positive integers b, c, m where (b < m) is True it is to find a positive integer e such that
(b**e % m == c) is True
where ** is exponentiation (e.g. in Ruby, Python or ^ in some other ...
Etoile asked 2/12, 2009 at 12:27
10
I am trying to find an efficient way to compute Euler's totient function.
What is wrong with this code? It doesn't seem to be working.
def isPrime(a):
return not ( a < 2 or any(a % i == 0 for...
Morehead asked 7/8, 2013 at 21:27
4
Solved
I have a long integer number, but it is stored not in decimal form, but as set of remainders.
So, I have not the N number, but set of such remainders:
r_1 = N % 2147483743
r_2 = N % 2147483713
r...
Waistcoat asked 13/3, 2011 at 1:53
6
I'd like to take the modular inverse of a matrix like [[1,2],[3,4]] mod 7 in Python. I've looked at numpy (which does matrix inversion but not modular matrix inversion) and I saw a few number theor...
Fermium asked 26/11, 2010 at 18:28
10
Solved
One way to get that is for the natural numbers (1,..,n) we factorise each and see if they have any repeated prime factors, but that would take a lot of time for large n. So is there any better way ...
Crossed asked 15/3, 2011 at 14:32
2
Note: This may involve a good deal of number theory, but the formula I found online is only an approximation, so I believe an exact solution requires some sort of iterative calculation by a compute...
Winniewinnifred asked 30/4, 2021 at 21:43
1
I have been working on code to iteratively partition integers and use previous results to fully partition the numbers, with the idea that using previous partitions can increase speed. So far, I hav...
Airfield asked 24/3, 2016 at 4:37
3
Solved
I'm solving some classic problems in Haskell to develop my functional
skills and I have a problem to implement an optimization suggested at this "Programming Praxis" site:
I have three solutions...
Chesty asked 4/10, 2010 at 4:4
4
I am trying this problem for a while but getting wrong answer again and again.
number can be very large <=2^2014.
22086. Prime Power Test
Explanation about my algorithm:
For a Given number I ...
Visceral asked 10/1, 2015 at 15:58
8
Solved
I have a function that tells me the nth number in a Fibonacci sequence. The problem is it becomes very slow when trying to find larger numbers in the Fibonacci sequence does anyone know how I can f...
Carbineer asked 9/11, 2014 at 14:24
4
Solved
Is there any algorithm to calculate (1^x + 2^x + 3^x + ... + n^x) mod 1000000007?
Note: a^b is the b-th power of a.
The constraints are 1 <= n <= 10^16, 1 <= x <= 1000. So the value o...
Giddings asked 17/1, 2017 at 10:56
6
Lets N be a number (10<=N<=10^5).
I have to break it into 3 numbers (x,y,z) such that it validates the following conditions.
1. x<=y<=z
2. x^2+y^2=z^2-1;
3. x+y+z<=N
I have to f...
Venlo asked 9/1, 2019 at 12:53
2
Solved
I am looking to implement a simple pseudorandom number generator (PRNG) that has a specified period and guaranteed no collisions for the duration of that period. After doing some research I came ac...
Internuncial asked 23/8, 2012 at 16:33
13
Solved
I had an interview with a hedge fund company in New York a few months ago and unfortunately, I did not get the internship offer as a data/software engineer. (They also asked the solution to be in P...
Vestryman asked 30/11, 2017 at 19:37
7
Solved
I coded up a program in C# to find perfect numbers within a certain range as part of a programming challenge . However, I realized it is very slow when calculating perfect numbers upwards of 10000....
Execration asked 16/4, 2010 at 8:25
2
Solved
I am having difficulty trying to solve the following problem:
For Q queries, Q <= 1e6, where each query is a positive integer N, N <= 1e18, find the number of integers in [1,N] that cannot...
Lectionary asked 15/11, 2017 at 2:48
4
Solved
For a given integers n and m, determine that coefficient of x^m term in (x^2+x+1)^n is even or odd?
For example, if n=3 and m=4, (x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1, so coef...
Dismember asked 29/4, 2017 at 9:46
2
Solved
What's the most efficient algorithm anyone can think of that, given a natural number n, returns the least natural number x with n positive divisors (including 1 and x)? For example, given 4 the alg...
Cronus asked 14/1, 2012 at 11:45
4
Solved
I have a series
S = i^(m) + i^(2m) + ............... + i^(km) (mod m)
0 <= i < m, k may be very large (up to 100,000,000), m <= 300000
I want to find the sum. I cannot apply the Geom...
Uninterested asked 5/10, 2009 at 22:53
3
Write a program that takes an integer and prints out all ways to multiply smaller integers that equal the original number, without repeating sets of factors. In other words, if your output contains...
Pokorny asked 15/8, 2016 at 3:5
2
Solved
I'm starting learning Prolog and I want a program that given a integer P gives to integers A and B such that P = A² + B². If there aren't values of A and B that satisfy this equation, false should ...
Snippet asked 20/7, 2016 at 12:25
4
Solved
I right away give an example,
now suppose I have 3 arrays a,b,c such as
a = c(3,5)
b = c(6,1,8,7)
c = c(4,2,9)
I must be able to extract consecutive triplets among them i,e.,
c(1,2,3),c(4,5,6)
...
Duppy asked 24/6, 2016 at 14:36
5
Solved
The code snippet below checks whether a given number is a prime number. Can someone explain to me why this works? This code was on a study guide given to us for a Java exam.
public static void mai...
Excipient asked 22/10, 2013 at 10:0
3
Solved
A vampire number is defined here https://en.wikipedia.org/wiki/Vampire_number. A number V is a vampire number if:
It can be expressed as X*Y such that X and Y have N/2 digits each where N is the...
Inly asked 11/4, 2016 at 22:43
1 Next >
© 2022 - 2024 — McMap. All rights reserved.