Questions tagged [diophantine]
48 questions
10
votes
3 answers
Project Euler Problem 233
I've decided to tackle Project Euler problem 233 next but I'm having some major problems! I've done some analysis and have made some quite nice progress but I've become stuck now. Here's my working:
Lemma 1:
Since the circle goes through the 4…
PythonPower
9
votes
3 answers
Finding Integers With A Certain Property - Project Euler Problem 221
I've become very addicted to Project Euler recently and am trying to do this one next! I've started some analysis on it and have reduced the problem down substantially already. Here's my working:
A = pqr and
1/A = 1/p + 1/q + 1/r so pqr/A =
…
PythonPower
6
votes
1 answer
Algorithms to compute Frobenius Numbers of a set of positive integers
Frobenius numbers of a set exist iff the gcd of the numbers of the set is 1. Given a set of positive integers with at most 10 elements such that the gcd of all the elements is 1, how can we compute the Frobenius number of the set?
Here is the link…
biswajitsc
- 63
- 4
4
votes
3 answers
Efficient algorithm to generate all solutions of a linear diophantine equation with ai=1
I am trying to generate all the solutions for the following equations for a given H.
With H=4 :
1) ALL solutions for x_1 + x_2 + x_3 + x_4 =4
2) ALL solutions for x_1 + x_2 + x_3 = 4
3) ALL solutions for x_1 + x_2 = 4
4) ALL solutions for x_1…
Ben
- 239
- 3
- 8
3
votes
2 answers
Threes, finding 23 sets of x y z values satisfy the condition x^3+y^3=1+z^3
Now I have completed the finding 23 sets of x y z values satisfy the condition x^3+y^3=1+z^3 & x
int setsFound = 0;
System.out.println("The first 23 sets ordered by increasing x.");
for (long x = 1; setsFound < 23; x++) {
for (long z = x + 1;…
Jeff
- 31
- 2
3
votes
1 answer
Integer factorization in repetitive pattern
I'm looking for an efficient solution to a specific case of integer factorization. By efficient I mean considerably faster than O(2^n), which I currently have (n represents the number of elements in the array after we are done).
Suppose we have the…
Atte Juvonen
- 4,922
- 7
- 46
- 89
3
votes
1 answer
Solving linear Diophantine equation
I am trying to code an algorithm in Python in order to solve linear Diophantine equations.
I think my algorithm is correct because I have tested it on a paper, however when I run it, it returns strange values.
My code:
def solve_Dioph(a,b,c):
…
Oscar Martinez
- 621
- 1
- 8
- 18
3
votes
2 answers
Representing nested for loops in Python
You're solving a simple Diophantine equation and you use the following Python code to do it.
## 3a+b+c+d=10
r=10/3
for a in range(r, 0, -1):
r=10-3*a
for b in range(r, 0, -1):
r=10-3*a-b
for c in range(r, 0, -1):
…
Bill Bell
- 21,021
- 5
- 43
- 58
3
votes
1 answer
Finding all combinations of multiple variables summing to 1
I am trying to solve the equation
x1 + x2 + x3 + .... + xn = 1
where the values of all xi are restricted to [0, 0.1, 0.2, ..., 0.9, 1].
Currently, I am solving the problem by first generating an n-dimensional array mat, where at each element…
Andreas Schönfeld
- 33
- 4
3
votes
1 answer
Algorithm to approximate an optimal solution for an integer allocation problem
I have the following problem:
Given a set of sums of variables like { a + b, b + c, c + d, a + a + d, b }, find positive integer values for the variables such that all sums are distinct and the highest sum is as small as possible.
Is there an…
fuz
- 88,405
- 25
- 200
- 352
3
votes
1 answer
Iterating a Diophantine equation over a list of itself in python
I'm self-studying MIT Open Courseware Introduction to Computer Science and Programming. Problem Set 2 involves Diophantine equations based on counting sums of chicken nugget boxes (6, 9, or 20).
The way I thought about creating an algorithm was…
Jason Powell
- 31
- 1
3
votes
1 answer
Count number of solutions for multiple-variiable linear diophantine equations with coprime coefficient
Let the general diophantine equation be :
a1*x1 + a2*x2 + .... + am*xm = n , where gcd(a1...am) = 1, (a1....am) >= 0
I want to find the number of non-negative (x1..xm) solutions.
Could someone help me with this?
Detailed mathematical explanations…
user2129227
- 97
- 1
- 4
2
votes
1 answer
Solving Linear Diophantine Equation Systems in C++
For my research I'm confronted with a system of linear diophantine equations.
I found several research papers on the topic but before I start to create
a solver myself, I would like to know if one does know of a (lightweight)
C++ math library, which…
Kickchon
- 61
- 1
- 4
2
votes
3 answers
Counting number of integer solutions of z³ = x²y² for given z
I have been working on this problem for some time now. The problem asks to find two numbers x and y such that the product of the squares of x and y equal the cube of k. My approach was to solve for x, given that an input of 1 would give a number,…
Hooahclitus
- 41
- 4
2
votes
1 answer
Linear Diophantine Equations with Restriction in the GAP System
I am searching for a way to use the GAP System to find a solution of a linear Diophantine equation over the non-negative integers. Explicitly, I have a list L of positive integers for each of which there exists a solution of the linear Diophantine…
Dylan C. Beck
- 135
- 6