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

Author

Sirius Caffrey, Jul 17 2015

Keywords

• nonn

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.

Examples

			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}].
		

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

Programs

Python

#  see link above

Formula

a(p) = 3*a(p-1) for p prime. - Alois P. Heinz, Jul 19 2015

Extensions

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