A260185 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; graph; refs; listen; history; text; internal format)

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