SOLUTION: 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?

Algebra.Com
Question 1209831: 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?

Found 2 solutions by CPhill, ikleyn:
Answer by CPhill(1959)   (Show Source): You can put this solution on YOUR website!
Let S={1,2,3,…,12}.
The primes in S are P={2,3,5,7,11}.
We want to find the number of subsets of S such that no two consecutive primes are members.
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
n

be the number of subsets of {p
1

,p
2

,…,p
n

} with no consecutive primes, where p
i

is the i-th prime.
For n=0, a
0

=1 (empty set).
For n=1, a
1

=2 (empty set, {p
1

}).
For n=2, a
2

=3 (empty set, {p
1

}, {p
2

}).
For n=3, a
3

=5 (empty set, {p
1

}, {p
2

}, {p
3

}, {p
1

,p
3

}).
For n=4, a
4

=8 (empty set, {p
1

}, {p
2

}, {p
3

}, {p
4

}, {p
1

,p
3

}, {p
1

,p
4

}, {p
2

,p
4

}).
For n=5, a
5

=13 (empty set, {p
1

}, {p
2

}, {p
3

}, {p
4

}, {p
5

}, {p
1

,p
3

}, {p
1

,p
4

}, {p
1

,p
5

}, {p
2

,p
4

}, {p
2

,p
5

}, {p
3

,p
5

}, {p
1

,p
3

,p
5

}).
We observe that a
n

=F
n+2

, where F
n

is the n-th Fibonacci number (F
0

=0,F
1

=1,F
2

=1,F
3

=2,F
4

=3,F
5

=5,…).
Thus, the number of subsets of P with no consecutive primes is a
5

=F
7

=13.
Now consider the non-prime numbers in S: N={1,4,6,8,9,10,12}.
The number of subsets of N is 2
7
=128.
Each subset of N can be combined with any subset of P that has no consecutive primes.
Thus, the total number of subsets of S with no consecutive primes is 13×128=1664.
Final Answer: The final answer is
1664


Answer by ikleyn(52778)   (Show Source): You can put this solution on YOUR website!
.

It looks like @CPhill created/invented a new way presenting solutions
to Math problems: - - - making it in an UNREADABLE format.


To all other visitors and readers of his posts, I recommend ignore them
and read directly from the Google AI source.

Concretely for this given problem, you may read the solution in traditional format from this link

https://www.google.com/search?q=Let+S+be+the+set+%7B1%2C+2%2C+3%2C+...+%2C+10%2C+11%2C+12%7D.+How+many+subsets+of+the+set+S+have+no+two+consecutive+primes+as+members%3F&rlz=1C1CHBF_enUS1071US1071&oq=Let+S+be+the+set+%7B1%2C+2%2C+3%2C+...+%2C+10%2C+11%2C+12%7D.++How+many+subsets+of+the+set+S+have+no+two+consecutive+primes+as+members%3F&gs_lcrp=EgZjaHJvbWUyBggAEEUYOdIBCjE5MjYyajBqMTWoAgiwAgHxBXPVsR37pL67&sourceid=chrome&ie=UTF-8



RELATED QUESTIONS

Let S be the universal set, where: - S={1,2,3,...,18,19,20} Let sets A and B be... (answered by ikleyn)
Let S be the universal set, where: S={1,2,3,...,18,19,20) Let sets A and B be subsets... (answered by ikleyn)
Let S={1,2,3,...,18,19,20} be the universal set. Let sets A and B be subsets of S, (answered by Boreal,ikleyn)
Let S be the universal set, where: S = {1,2,3,...,28,29,30} Let sets A and B be subsets... (answered by MathLover1,ikleyn)
Let S = {1,2,3,...,18,19,20} be the universal set. Let sets A and B be subsets of S,... (answered by Solver92311)
Let A = {1, 2, 3, 4, 5, 6}. (a) How many subsets of 4 elements does the set A have?... (answered by ikleyn)
Assume that the set S has 13 elements. How many subsets of S have at most 3... (answered by Edwin McCravy)
Let S={1,2,3,4,…,n}, and let A and B be two subsets of S such that A ≠ ∅, B ≠ S,... (answered by ikleyn)
Let S={1,2,3,4,5,6,7,8,9,10} be the universal set. Let sets A, B, and C be subsets of... (answered by math_tutor2020)