login
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.
2
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
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
Sequence in context: A341704 A146416 A260185 * A239663 A004667 A237122
KEYWORD
nonn
AUTHOR
Brian Barsotti, Jul 07 2019
EXTENSIONS
a(9)-a(31) from Giovanni Resta, Jul 07 2019
STATUS
approved