Re: [math-fun] Similar permutations problem
Oops, my braino - your number is correct, and not such a big number by today's standards as you pointed out. The original question remains - is there a better that brute force way to approach it? In actuality, 20,000 is just the number I have on hand, the actual number is much larger.
I think it's time we probed for exactly what you (Dave) mean by "similar". If your criterion for similarity is stricter, it's more likely we'll be able to come up with a speedup over the obvious pairwise comparison. On Thu, May 7, 2015 at 3:44 PM, Dave Dyer <ddyer@real-me.net> wrote:
Oops, my braino - your number is correct, and not such a big number by today's standards as you pointed out.
The original question remains - is there a better that brute force way to approach it? In actuality, 20,000 is just the number I have on hand, the actual number is much larger.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Search engines are now eerily good at correcting typos in their input. I don't know what algorithms are employed to achieve this, but suspect their strategy may have some relevance to this problem. WFL On 5/7/15, Allan Wechsler <acwacw@gmail.com> wrote:
I think it's time we probed for exactly what you (Dave) mean by "similar". If your criterion for similarity is stricter, it's more likely we'll be able to come up with a speedup over the obvious pairwise comparison.
On Thu, May 7, 2015 at 3:44 PM, Dave Dyer <ddyer@real-me.net> wrote:
Oops, my braino - your number is correct, and not such a big number by today's standards as you pointed out.
The original question remains - is there a better that brute force way to approach it? In actuality, 20,000 is just the number I have on hand, the actual number is much larger.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I had an idea in this vein for what you might do if you were Google. Design your text box widget to capture *all the keystrokes* the user used to assemble the final search string, all the erasures and so on. This would give you a rich corpus of common typos. On Thu, May 7, 2015 at 4:15 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Search engines are now eerily good at correcting typos in their input. I don't know what algorithms are employed to achieve this, but suspect their strategy may have some relevance to this problem. WFL
On 5/7/15, Allan Wechsler <acwacw@gmail.com> wrote:
I think it's time we probed for exactly what you (Dave) mean by "similar". If your criterion for similarity is stricter, it's more likely we'll be able to come up with a speedup over the obvious pairwise comparison.
On Thu, May 7, 2015 at 3:44 PM, Dave Dyer <ddyer@real-me.net> wrote:
Oops, my braino - your number is correct, and not such a big number by today's standards as you pointed out.
The original question remains - is there a better that brute force way to approach it? In actuality, 20,000 is just the number I have on hand, the actual number is much larger.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Here is Peter Norvig dissecting his toy spelling correction code: http://norvig.com/spell-correct.html On Thu, May 7, 2015 at 4:15 PM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Search engines are now eerily good at correcting typos in their input. I don't know what algorithms are employed to achieve this, but suspect their strategy may have some relevance to this problem. WFL
On 5/7/15, Allan Wechsler <acwacw@gmail.com> wrote:
I think it's time we probed for exactly what you (Dave) mean by "similar". If your criterion for similarity is stricter, it's more likely we'll be able to come up with a speedup over the obvious pairwise comparison.
On Thu, May 7, 2015 at 3:44 PM, Dave Dyer <ddyer@real-me.net> wrote:
Oops, my braino - your number is correct, and not such a big number by today's standards as you pointed out.
The original question remains - is there a better that brute force way to approach it? In actuality, 20,000 is just the number I have on hand, the actual number is much larger.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Does every set of consecutive integers contain at least one relatively prime to the rest? --Dan
No. The smallest counterexample is 2184,2185,...,2200. This is Pillai's problem. On 5/9/15 4:38 PM, Dan Asimov wrote:
Does every set of consecutive integers contain at least one relatively prime to the rest?
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
See also https://oeis.org/A090318 where it is mentioned that there are sets of consecutive integers of every length > 16 for which any two have a common factor greater than 1. Charles Greathouse Analyst/Programmer Case Western Reserve University On Sat, May 9, 2015 at 5:12 PM, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
No. The smallest counterexample is 2184,2185,...,2200. This is Pillai's problem.
On 5/9/15 4:38 PM, Dan Asimov wrote:
Does every set of consecutive integers contain at least one relatively prime to the rest?
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think you've misstated. Clearly (n,n+1)=1. I think what you meant was that every element of the set shares a common factor with some other element of the set. --ms On 13-May-15 11:59, Charles Greathouse wrote:
See also https://oeis.org/A090318 where it is mentioned that there are sets of consecutive integers of every length > 16 for which any two have a common factor greater than 1.
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Sat, May 9, 2015 at 5:12 PM, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
No. The smallest counterexample is 2184,2185,...,2200. This is Pillai's problem.
On 5/9/15 4:38 PM, Dan Asimov wrote:
Does every set of consecutive integers contain at least one relatively prime to the rest?
--Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (8)
-
Allan Wechsler -
Charles Greathouse -
Dan Asimov -
Dave Dyer -
Fred Lunnon -
Jeff Caldwell -
Jeffrey Shallit -
Mike Speciner