tag:blogger.com,1999:blog-3722233.post7713603410258963272..comments2023-11-28T22:15:32.433-06:00Comments on Computational Complexity: Do we root for how a problem will go?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-54680576731551765492007-11-16T11:37:00.000-06:002007-11-16T11:37:00.000-06:00A131741 a(n) is least prime (not already in list) ...<A HREF="http://www.research.att.com/~njas/sequences/A131741" REL="nofollow">A131741</A> <BR/><BR/>a(n) is least prime (not already in list) such that no 3-term subset forms an arithmetic progression. <BR/><BR/>2, 3, 5, 11, 13, 29, 31, 37, 41, 67, 73, 83, 89, 101, 107, 127, 139, 157, 179, 193, 227, 233, 263, 271, 281, 307, 331, 337, 379, 389, 397, 401, 409, 431, 433, 467, 491, 499, 509, 563, 571, 613, 641, 647, 743, 769, 809, 823, 883, 887, 907, 937, 983, 1009, 1021 <BR/><BR/>COMMENT <BR/><BR/>a(n) is the smallest prime such that there is no i < j < n with a(n) - a(j) = a(j) - a(i).<BR/><BR/>EXAMPLE <BR/><BR/>Table showing derivation of first 10 values.<BR/><BR/>n a(n) comment<BR/><BR/>1 2<BR/><BR/>2 3<BR/><BR/>3 5<BR/><BR/>4 11 a(4) can't be 7 because (3,5,7) is in arithmetic progression.<BR/><BR/>5 13<BR/><BR/>6 29 can't be 17 because (5,11,17); can't be 19 because (3,11,19); can't be 23 because (3,13,23)<BR/><BR/>7 31<BR/><BR/>8 37<BR/><BR/>9 41<BR/><BR/>10 67 not 43 as (31,37,43); not 47 as (11,29,47); not 53 as (29,41,53); not 59 as (13,31,59); not 61 as (13,37,61)<BR/><BR/>MATHEMATICA <BR/><BR/>f[l_List] := Block[{c, f = 0}, c = If[l == {}, 0, l[[ -1]]]; While[f == 0, c = NextPrime[c]; If[Intersection[l, l - (c - l)] == {}, f = 1]; ]; Append[l, c] ]; Nest[f, {}, 100]<BR/><BR/>CROSSREFS <BR/><BR/>Cf. A000040, A065825.<BR/><BR/>KEYWORD <BR/>easy,nonn<BR/><BR/>AUTHOR <BR/><BR/>Jonathan Vos Post (jvospost2(AT)yahoo.com), Oct 04 2007<BR/><BR/>EXTENSIONS <BR/><BR/>More terms and program from Ray ChandlerAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83662936113499063482007-11-01T20:36:00.000-05:002007-11-01T20:36:00.000-05:00"P\ne NP (better crypto)?"Shame, Bill: P != NP doe..."P\ne NP (better crypto)?"<BR/><BR/>Shame, Bill: P != NP doesn't imply OWF exist.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81962575873421225282007-11-01T15:33:00.000-05:002007-11-01T15:33:00.000-05:00Yes, I can imagine you do not have a rooting inter...Yes, I can imagine you do not have a rooting interest in whether larger 3-free sets exist or not. But wouldn't you have at least a slight rooting interest that the question is relevant to something else?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56137866180907184422007-11-01T12:30:00.000-05:002007-11-01T12:30:00.000-05:00Unlike the case of P vs. NP, an article about 3-fr...Unlike the case of P vs. NP, an article about 3-free sets would have a wider audience if it had applications for matrix multiplication. It would likely be quoted far more often, contributing to your reputation. This may not be why you got interested in a problem, but for many it would be a nice bonus.Unknownhttps://www.blogger.com/profile/04842369931350847129noreply@blogger.com