login
A260185
a(n) is the number of ways to select an ordered pair of subsets of {2,...,n} such that each pair of elements from different subsets are relatively prime.
1
1, 3, 9, 21, 63, 111, 333, 693, 1521, 2577, 7731, 13491, 40473, 67833, 119241, 239481, 718443, 1340523, 4021569, 7494849, 13356657, 22271409, 66814227, 130266387, 268286823, 447212583, 896472063, 1684872063, 5054616189, 9566769789, 28700309367, 57402497367
OFFSET
1,2
COMMENTS
This sequence was used by LuoYuping when he set a problem for NOI 2015 Day1 Problem3.
a(n) is the number of ways to find X and Y where set X and Y are subsets of {2,...,n}, and for all a in X and all b in Y, gcd(a,b) = 1. Also note that X or Y can be empty.
REFERENCES
National Olympiad in Informatics 2015, China, Day 1 Problem 3.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..100 (first 80 terms from Giovanni Resta)
Sirius Caffrey, C++ program for A260185
FORMULA
a(p) = 3*a(p-1) for p prime. - Alois P. Heinz, Jul 19 2015
EXAMPLE
For n=1 the 1 pair of sets is [{},{}].
For n=2 the 3 pairs of sets are [{},{}], [{2},{}], and [{},{2}].
For n=3 the 9 pairs of sets are [{},{}], [{2},{}], [{},{2}], [{3},{}], [{},{3}], [{2,3},{}], [{},{2,3}], [{2},{3}], and [{3},{2}].
PROG
(C++) // see link above
(Python) # see link above
CROSSREFS
Sequence in context: A147078 A341704 A146416 * A307105 A239663 A004667
KEYWORD
nonn
AUTHOR
Sirius Caffrey, Jul 17 2015
EXTENSIONS
a(31)-a(32) from Giovanni Resta, Jul 18 2015
STATUS
approved