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, 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

Sirius Caffrey, Python 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

Adjacent sequences: A260182 A260183 A260184 * A260186 A260187 A260188

Keyword

nonn

Author

Sirius Caffrey, Jul 17 2015

Extensions

a(31)-a(32) from Giovanni Resta, Jul 18 2015

Status

approved