How to solve diophantine problems?
Joshua, Y.J. Lai
I can roughly solve the diophantine problem by using a nest loop
ex.
def td(x):
"The number of balls used to construct a tetrahedron"
return x*(x+1)*(x+2)/6
def tri(y):
"The number of balls used to construct a triangle"
return y*(y+1)/2
for x in xrange(100):
for y in xrange(100):
a=td(x)
b=tri(y)
if a==b!=0:
print "x = %d and y = %d , number = %d" % (x,y,a)
----------------------------------------------------------------------------
-------
But if I want to limit the maximum amount of balls (k) in this question
then I will add an additional line:
k=input("Please define the Max of balls: ")
However, I do not know how to write the checking loops in this case?
Because, the x and y are uncertain now. Could anyone please kindly help me.
Thank you.
Emile van Sebille
> I can roughly solve the diophantine problem by using a nest loop
I'm not familiar with the "diophantine problem" and didn't, in a quick
look, spot anything obvious to me stating it.
> ex.
> def td(x):
> "The number of balls used to construct a tetrahedron"
> return x*(x+1)*(x+2)/6
>
> def tri(y):
> "The number of balls used to construct a triangle"
> return y*(y+1)/2
>
> for x in xrange(100):
> for y in xrange(100):
> a=td(x)
> b=tri(y)
> if a==b!=0:
> print "x = %d and y = %d , number = %d" % (x,y,a)
> ----------------------------------------------------------------------
------
> -------
> But if I want to limit the maximum amount of balls (k) in this
question
> then I will add an additional line:
> k=input("Please define the Max of balls: ")
you'll want this to be raw_input
> However, I do not know how to write the checking loops in this case?
> Because, the x and y are uncertain now. Could anyone please kindly
help me.
I think you want to limit the sum of a and b to k? Does this do it?:
if a and a == b and a+b <= k:
print "x = %d and y = %d , number = %d" % (x,y,a)
HTH,
Emile van Sebille
em...@fenx.com
Cameron Laird
Emile van Sebille <em...@fenx.com> wrote:
>Joshua, Y.J. Lai
>> I can roughly solve the diophantine problem by using a nest loop
>
>I'm not familiar with the "diophantine problem" and didn't, in a quick
>look, spot anything obvious to me stating it.
.
.
Rough translation: a solution in integers (to
a system of polynomial equations and constraints).
--
Cameron Laird <Cam...@Lairds.com>
Business: http://www.Phaseit.net
Personal: http://starbase.neosoft.com/~claird/home.html
A. Keyton Weissinger
I've sent this to the Announcements list, but there seems to be just as many
announcements on this list. So I figured I'd drop this one-time note in here
as well.
What is Puffin?
Puffin allows you to test any web application or service. Once customized to
your web application, you can use Puffin to unit test individual web pages,
system test your entire web application, or load test your entire site.
You can find out more about Puffin at http://puffin.sourceforge.net.
You can either download the latest stable release (0.8.9) or retrieve the
latest snapshot from CVS (recommended -- lots of bugfixes and some MySQL
support).
The documentation is in the process of being updated, but check out the
current User's Guide, nonetheless
(http://puffin.sourceforge.net/puffindocs/UserGuide.htm). It gives the ins
and outs of all that Puffin can do.
Be sure to watch IBM's developerWorks for a series of articles coming up on
Puffin as well!
I'm looking for any and every way I can make Puffin better. So don't
hesitate to contact me if you find a bug or think of a feature you want. I
will make whatever time is required to make Puffin better fit your needs and
its purpose!
Thank you!
Keyton
A. Keyton Weissinger
Joshua, Y.J. Lai
"Cameron Laird" <cla...@starbase.neosoft.com> wrote in message
news:EF9D274DA8540EF1.D12AA708...@lp.airnews.net...
> In article <TQXD8.31658$Po6....@rwcrnsc52.ops.asp.att.net>,
> Emile van Sebille <em...@fenx.com> wrote:
> >Joshua, Y.J. Lai
> >> I can roughly solve the diophantine problem by using a nest loop
> >
> >I'm not familiar with the "diophantine problem" and didn't, in a quick
> >look, spot anything obvious to me stating it.
> .
> .
> .
> Rough translation: a solution in integers (to
> a system of polynomial equations and constraints).
Thank you for your precise explanation. The problem now I suffer is how can
I write a new checking loop
instead of using two FOR LOOPs as nest loop. I am really interested in that.
I will be very grateful if anyone of you can give me some hints.
John Machin
> Dear everyone:
>
> I can roughly solve the diophantine problem by using a nest loop
> ex.
> But if I want to limit the maximum amount of balls (k) in this question
> then I will add an additional line:
> k=input("Please define the Max of balls: ")
> However, I do not know how to write the checking loops in this case?
> Because, the x and y are uncertain now. Could anyone please kindly help me.
> Thank you.
You probably want something like this. As Emile said, don't use
input().
import sys
def td(x):
"The number of balls used to construct a tetrahedron"
return x*(x+1)*(x+2)/6
def tri(y):
"The number of balls used to construct a triangle"
return y*(y+1)/2
def dio1(n):
# n is max # balls on one edge of tetrahedron or triangle
for x in xrange(n):
a=td(x)
for y in xrange(n):
b=tri(y)
if a==b!=0:
print "x = %d and y = %d , number = %d" % (x,y,a)
def dio2(k):
# k is max number of balls in total
for x in xrange(sys.maxint):
a=td(x)
if a >= k:
break
for y in xrange(sys.maxint):
b=tri(y)
if a + b > k:
break
if a==b!=0:
print "x = %d and y = %d , number = %d" % (x,y,a)
Python 2.2.1 (#34, Apr 9 2002, 19:34:33) [MSC 32 bit (Intel)] on
win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import diophant
>>> diophant.dio1(100)
x = 1 and y = 1 , number = 1
x = 3 and y = 4 , number = 10
x = 8 and y = 15 , number = 120
x = 20 and y = 55 , number = 1540
>>> diophant.dio2(500)
x = 1 and y = 1 , number = 1
x = 3 and y = 4 , number = 10
x = 8 and y = 15 , number = 120
>>> diophant.dio2(5000)
x = 1 and y = 1 , number = 1
x = 3 and y = 4 , number = 10
x = 8 and y = 15 , number = 120
x = 20 and y = 55 , number = 1540
>>> diophant.dio2(50000)
x = 1 and y = 1 , number = 1
x = 3 and y = 4 , number = 10
x = 8 and y = 15 , number = 120
x = 20 and y = 55 , number = 1540
x = 34 and y = 119 , number = 7140
>>>
Tighter conditions could be used in the two tests of when to break out
of the loop -- but you would have to solve a quadratic and a cubic.
HTH,
John
Cameron Laird
Please explain the problem again. Are you looking for
an implementation that solves this specific diophantine
problem (perhaps with the coefficients as variables,
with respect to the implementation) while manifesting
only one overt loop, or a general way to express
a program transformation which reduces loop counts for
diophantine problems, or ...? At this point, you have
complete knowledge--that is, a terminating procedure
--about the solutions of the problems; what more can
you want?
you first expressed
Bengt Richter
This has nested loops, but they work a bit differently.
You can just let it run until you get tired of waiting ;-)
>>> def td(x):
... "The number of balls used to construct a tetrahedron"
... return x*(x+1)*(x+2)/6
...
>>> def tri(y):
... "The number of balls used to construct a triangle"
... return y*(y+1)/2
...
>>> def dioh():
... x=xt=xp=y=0 # t for triangle, p for pyramid
... while 1:
... x += 1
... xt += x
... xp += xt
... while xp>0:
... y += 1
... xp -= y
... if xp==0:
... print "\rx = %d and y = %d , number = %d" % (x,y,td(x))
... if not x % 1000:
... print "\rx = %d and y = %d , n(x) = %d, n(y) = %d" % (x,y,td(x),tri(y)),
...
>>> dioh()
x = 1 and y = 1 , number = 1
x = 3 and y = 4 , number = 10
x = 8 and y = 15 , number = 120
x = 20 and y = 55 , number = 1540
x = 34 and y = 119 , number = 7140
x = 78000 and y = 12577364 , n(x) = 79095042026000, n(y) = 79095048882930
Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "<stdin>", line 7, in dioh
KeyboardInterrupt
The last line just keeps getting overwritten at every even thousand balls
on the tetrahedron edge, until there's a valid output with td(x)==tri(y)
overwriting it and advancing to the next line.
Regards,
Bengt Richter
Cameron Laird
I apparently temporized: .
.
.
>>Thank you for your precise explanation. The problem now I suffer is how can
>>I write a new checking loop
>>instead of using two FOR LOOPs as nest loop. I am really interested in that.
>>I will be very grateful if anyone of you can give me some hints.
>>
>>
>
>Please explain the problem again. Are you looking for
>an implementation that solves this specific diophantine
>problem (perhaps with the coefficients as variables,
>with respect to the implementation) while manifesting
>only one overt loop, or a general way to express
>a program transformation which reduces loop counts for
>diophantine problems, or ...? At this point, you have
>complete knowledge--that is, a terminating procedure
>--about the solutions of the problems; what more can
>you want?
.
.
Mr. Joshua and I have done a little bit privately. I
still don't understand the question, and think there
might be benefit in doing this back out in public.
I believe he's asking either a very hard question, or
a very easy one. Here's an answer to the easy one:
if we're searching for
all (x,y) such that P(x, y), and 0 <= x,y <= 100
for some proposition P(), then we can exhaustively
search
for x in range(0, 100):
for y in range(0, 100):
if P(x, y):
print "(%s, %s) is a solution." % (x, y)
(note that several optimizations are available. I
choose this expression for what I hope to be expository
clarity). This is what Mr. Joshua has achieved already.
He *might* be asking for a generalization which drops
the range constraints ('cept that we're still looking for
non-negatives?), and asks merely that the program con-
tinue until it finds a solution (which can be rearranged
as a generator, of course). How can he loop, though?
There are plenty of ways to do that; it occurs to me he
might like
sum = 0
while 1:
for x in range (0, sum):
y = sum - x
if P(x, y):
print "(%s, %s) is a solution." % (x, y)
sum = sum + 1
(everybody see how nice generators would make this?).
It's possible, though, that Mr. Joshua is asking for
something like an algorithm to determine upper bounds
on solutions, depending on P. That's a very hard problem,
at least for today.
Michael Hudson
> It's possible, though, that Mr. Joshua is asking for something like
> an algorithm to determine upper bounds on solutions, depending on P.
> That's a very hard problem, at least for today.
I'd say; it's strictly impossible, if the question is what I think it
is (by the MRDP theorem).
Cheers,
M.
--
The use of COBOL cripples the mind; its teaching should, therefore,
be regarded as a criminal offence.
-- Edsger W. Dijkstra, SIGPLAN Notices, Volume 17, Number 5
Christopher Browne
> I can roughly solve the diophantine problem by using a nest loop
> ex.
> def td(x):
> "The number of balls used to construct a tetrahedron"
> return x*(x+1)*(x+2)/6
>
> def tri(y):
> "The number of balls used to construct a triangle"
> return y*(y+1)/2
>
> for x in xrange(100):
> for y in xrange(100):
> a=td(x)
> b=tri(y)
> if a==b!=0:
> print "x = %d and y = %d , number = %d" % (x,y,a)
> But if I want to limit the maximum amount of balls (k) in this question
> then I will add an additional line:
> k=input("Please define the Max of balls: ")
> However, I do not know how to write the checking loops in this case?
> Because, the x and y are uncertain now. Could anyone please kindly help me.
I'd suggest a _completely_ different structuring of the nested loop.
You can make the program on the order of 100 times as fast by simply
storing the td() and tri() values in dictionaries, and comparing
dictionaries, thus:
A={}
B={}
maxballs = 25000
# Compute the function values, ONCE
for x in xrange(1200):
ba=td(x)
if (ba < maxballs):
A[ba] = x # Only keep number of balls if it's legal
bb=tri(x)
if (bb < maxballs):
B[bb] = x
# Now, search A for all the numbers of balls
for k in A.keys():
if B.has_key(k): # If there's a match in B, show it...
print "A Balls:", k, "A count:", A[k], "B Balls:",
k, "B count:", B[k]
... which runs lickety-split ...
A Balls: 10 A count: 3 B Balls: 10 B count: 4
A Balls: 120 A count: 8 B Balls: 120 B count: 15
A Balls: 7140 A count: 34 B Balls: 7140 B count: 119
A Balls: 1540 A count: 20 B Balls: 1540 B count: 55
A Balls: 1 A count: 1 B Balls: 1 B count: 1
A Balls: 0 A count: 0 B Balls: 0 B count: 0
--
(reverse (concatenate 'string "gro.mca@" "enworbbc"))
http://www.cbbrowne.com/info/linuxdistributions.html
"It has every known bug fix to everything." -- KLH (out of context)
Paulo Eduardo Neves
> > hesitate to contact me if you find a bug or think of a feature you want. I
> > will make whatever time is required to make Puffin better fit
> > your needs and
> > its purpose!
How does Puffin compares to httpunit?
http://httpunit.sourceforge.net/
httpunit is a unit testing framework in java. Nowadays I use jython
just to use this library. To be true, I don't even use for testing,
but to simulate the browser behavior and automaticaly perform some
actions in my on line bank. It'd be nice to stay with a pure python
solution.
Alan Kennedy
> "A. Keyton Weissinger" <li...@weissinger.org> wrote in message
> > I'm looking for any and every way I can make Puffin better. So don't
> > > hesitate to contact me if you find a bug or think of a feature you want. I
> > > will make whatever time is required to make Puffin better fit
> > > your needs and
> > > its purpose!
>
> How does Puffin compares to httpunit?
> http://httpunit.sourceforge.net/
Another comparable project is the Apache Latka project, written in
Java, which uses XML comfiguration files to test HTTP conversations.
http://jakarta.apache.org/commons/latka/index.html
I haven't had enough time to look at either Latka or Puffin, but I do
intend to start using one of them soon.
I like the idea of Puffin, because it's pure python.
IMHO, Python is far superior to Java for this type of application,
principally because of the ability to dynamically extract
strings/numbers from the returned resource, turn them into a piece of
python code by simple string manipulation, and 'eval()' it into a
result which can be directly acted upon.
I'll be looking closely at Puffin.
Regards,
Alan Kennedy.