#16662: OA for n=1046,1059,2164,3992,3994
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.4
Component: combinatorial | Resolution:
designs | Merged in:
Keywords: | Reviewers:
Authors: Nathann Cohen | Work issues:
Report Upstream: N/A | Commit:
Branch: u/ncohen/16662 | 8fcaed066b7f110af10c6a471cbebcad370bd312
Dependencies: #16604 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by ncohen):
Helloooooooo Vincent !
Okay... So let's do that:
1) You saved some time since the first version, and although it is still
slower than needed it's not that awful that we should keep this
construction out of those that are automatically tested
2) Those triple loops are really awful things, so we will have to do
something about it
3) I am thinking of a data structure that would be useful to us, and whose
purpose is to store things like "all n such that there exists a OA(k,n)"
or even "all m such that there exists a OA(k,m), OA(k,m+1), OA(k,m+2)".
What it stores: a set of integers defined by a boolean function
What it is meant to answer: give the list of integers between x and y such
that the boolean function is satisfied.
Of course we want to minimize the number of boolean function queries. Even
though it takes spaces, I am thinking of something like that:
An array which associates to (any) integer n:
a) if f(n) is computed: the smallest integer n'>=n such that f(n') is True
or has not been computed yet.
b) if f(n) is not computed yet: None
This way, if you want to get all solutions to `f(n) is True` between x and
y, here is what you do:
{{{
current=x
while current<=y:
if array[current] is None:
array[current] = f(current)
elif array[current] == current:
yield current
current+=1
else:
new_current = array[current]
# if array[a]==b and array[b]==c then let's define array[a]=c
if array[new_current] is not None:
array[current] = array[new_current]
current = new_current
}}}
This may be cool if we ever implement the `all_n` or `range_n` function.
And we could use it in conjunction with a real function to solve the
partition problem, i.e. "try to find integers from a set S whose sum is
equal or lequal to C".
Anyway.
1) I merged all your commits into one, as some were undoing the previous
ones
2) I added a small commit on top of it. In particular some additional
constraint on k that removes fake '+' in the n<100 area `:-D`
Your code is good otherwise.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/16662#comment:30>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
