A307105 Number of rational numbers which can be constructed from the set of integers between 1 and n, through a combination of multiplication and division.

1, 1, 3, 9, 21, 63, 117, 351, 621, 1161, 2043, 6129, 8631, 25893, 45135, 71685, 102285, 306855, 420309, 1260927, 1755513, 2671299, 4571073, 13713219, 17156853, 25778169, 43930755, 59315085, 80765235, 242295705, 295267275, 885801825

Offset: 0

Author

Brian Barsotti, Jul 07 2019

Keywords

• nonn

Comments

This sequence can contain only odd terms, because apart from 1, for every term x/y there is always the corresponding terms y/x. - Giovanni Resta, Jul 07 2019

a(n) <= 3*a(n-1), with equality iff n is prime. - Yan Sheng Ang, Feb 13 2020

Conjecture: Let p <= n be prime. If m and p^a*m are two such rationals, then so is p^k*m for all 0 < k < a. - Yan Sheng Ang, Feb 13 2020

Examples

			a(2) = 3 because {1,2} can create {1/2, 1, 2}.
a(3) = 9 because {1,2,3} can create {1/6, 1/3, 1/2, 2/3, 1, 3/2, 2, 3, 6}.
a(4) = 21 because {1,2,3,4} can create {1/24, 1/12, 1/8, 1/6, 1/4, 1/3, 3/8, 1/2, 2/3, 3/4, 1, 4/3, 3/2, 2, 8/3, 3, 4, 6, 8, 12, 24}.
		

Links

• Yan Sheng Ang, Table of n, a(n) for n = 0..51

Crossrefs

Cf. A018805, A060957.

Programs

Maple

s:= proc(n) option remember; `if`(n=0, {1},
      map(x-> [x, x*n, x/n][], s(n-1)))
    end:
a:= n-> nops(s(n)):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 29 2019

Mathematica

L={}; s={1}; Do[s = Union[s, s/k, s*k]; AppendTo[L, Length@ s], {k, 13}]; L (* Giovanni Resta, Jul 07 2019 *)

Formula

a(p) = 3 * a(p-1), for p prime. - Giovanni Resta, Jul 07 2019

Extensions

a(9)-a(31) from Giovanni Resta, Jul 07 2019