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

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

Links

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

Formula

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

Example

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

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 *)

Crossrefs

Cf. A018805, A060957.

Sequence in context: A341704 A146416 A260185 * A239663 A004667 A237122

Adjacent sequences: A307102 A307103 A307104 * A307106 A307107 A307108

Keyword

nonn

Author

Brian Barsotti, Jul 07 2019

Extensions

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

Status

approved