document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1209831>Question 1209831</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Let S be the set {1, 2, 3, \dots, 10, 11, 12}.  How many subsets of the set S have no two consecutive primes as members?<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #850733 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=850733\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Let S={1,2,3,…,12}.<BR>\n" );
document.write( "The primes in S are P={2,3,5,7,11}.<BR>\n" );
document.write( "We want to find the number of subsets of S such that no two consecutive primes are members.\r<BR>\n" );
document.write( "\n" );
document.write( "Let's consider the primes in S. We want to choose a subset of P such that no two consecutive primes are chosen. Let a <BR>\n" );
document.write( "n<BR>\n" );
document.write( "​<BR>\n" );
document.write( "  be the number of subsets of {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,…,p <BR>\n" );
document.write( "n<BR>\n" );
document.write( "​<BR>\n" );
document.write( " } with no consecutive primes, where p <BR>\n" );
document.write( "i<BR>\n" );
document.write( "​<BR>\n" );
document.write( "  is the i-th prime.\r<BR>\n" );
document.write( "\n" );
document.write( "For n=0, a <BR>\n" );
document.write( "0<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =1 (empty set).<BR>\n" );
document.write( "For n=1, a <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =2 (empty set, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }).<BR>\n" );
document.write( "For n=2, a <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =3 (empty set, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }).<BR>\n" );
document.write( "For n=3, a <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =5 (empty set, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }).<BR>\n" );
document.write( "For n=4, a <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =8 (empty set, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }).<BR>\n" );
document.write( "For n=5, a <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =13 (empty set, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }, {p <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " ,p <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " }).\r<BR>\n" );
document.write( "\n" );
document.write( "We observe that a <BR>\n" );
document.write( "n<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =F <BR>\n" );
document.write( "n+2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " , where F <BR>\n" );
document.write( "n<BR>\n" );
document.write( "​<BR>\n" );
document.write( "  is the n-th Fibonacci number (F <BR>\n" );
document.write( "0<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =0,F <BR>\n" );
document.write( "1<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =1,F <BR>\n" );
document.write( "2<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =1,F <BR>\n" );
document.write( "3<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =2,F <BR>\n" );
document.write( "4<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =3,F <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =5,…).\r<BR>\n" );
document.write( "\n" );
document.write( "Thus, the number of subsets of P with no consecutive primes is a <BR>\n" );
document.write( "5<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =F <BR>\n" );
document.write( "7<BR>\n" );
document.write( "​<BR>\n" );
document.write( " =13.\r<BR>\n" );
document.write( "\n" );
document.write( "Now consider the non-prime numbers in S: N={1,4,6,8,9,10,12}.<BR>\n" );
document.write( "The number of subsets of N is 2 <BR>\n" );
document.write( "7<BR>\n" );
document.write( " =128.\r<BR>\n" );
document.write( "\n" );
document.write( "Each subset of N can be combined with any subset of P that has no consecutive primes.<BR>\n" );
document.write( "Thus, the total number of subsets of S with no consecutive primes is 13×128=1664.\r<BR>\n" );
document.write( "\n" );
document.write( "Final Answer: The final answer is  <BR>\n" );
document.write( "1664<BR>\n" );
document.write( "​\r<BR>\n" );
document.write( "\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );