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

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A060957 Number of different products (including the empty product) of any subset of {1, 2, 3, ..., n}. 9
1, 1, 2, 4, 8, 16, 26, 52, 88, 152, 238, 476, 648, 1296, 2016, 2984, 4232, 8464, 11360, 22720, 30544, 43744, 67072, 134144, 166336, 242752, 370992, 498144, 656832, 1313664, 1581312, 3162624, 3960384, 5517248, 8386080, 11111232, 13065792, 26131584, 39690432 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
a(n) <= 2*a(n-1), with equality iff n is prime or n = 4. - Martin Fuller, Jun 03 2006
a(n) = 2^k * b(n) where k is the number of primes p such that n/2 < p <= n, and b(n) is the number of different products of subsets of {1, 2, ..., n} that exclude these primes. - David Radcliffe, Feb 11 2019
Conjecture: Let p <= n be prime. If m and p^a*m are two such products, then so is p^k*m for all 0 < k < a. - Yan Sheng Ang, Feb 13 2020
a(n) is even for n > 1. Since k is a product implies that n!/k is a product, a(n) is odd implies that n! is a square, which is impossible for n > 1 because of the Bertrand's postulate: for n > 1, there is a prime p in the range (n/2, n], so p divides n! while p^2 does not. - Jianing Song, Sep 26 2022
LINKS
Yan Sheng Ang, Table of n, a(n) for n = 0..68 (first 50 terms from David Radcliffe)
EXAMPLE
a(4) = 8: the subsets of {1, 2, 3, 4} are {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}. The 16 numbers as the product are 1, 1, 2, 3, 4, 2, 3, 4, 6, 8, 12, 6, 8, 12, 24. There are only 8 distinct numbers: 1, 2, 3, 4, 6, 8, 12, 24.
a(6) = 26: the set {1, 2, 3, 4, 5, 6, 2*3, 2*4, 2*5, ..., 5*6, 2*3*4, 2*3*5, ..., 4*5*6, ..., ...2*3*4*5*6} contains 26 different values: {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 20, 24, 30, 36, 40, 48, 60, 72, 90, 120, 144, 180, 240, 360, 720}
MAPLE
s:= proc(n) option remember; `if`(n=0, {1},
map(x-> [x, x*n][], s(n-1)))
end:
a:= n-> nops(s(n)):
seq(a(n), n=0..25); # Alois P. Heinz, Aug 25 2016
MATHEMATICA
(* Script not convenient for n > 24 *) a[n_] := Times @@@ Subsets[Range[n]] // Union // Length; Table[Print["a(", n, ") = ", an = a[n]]; an, {n, 1, 24}] (* Jean-François Alcover, Feb 02 2015 *)
s[n_] := s[n] = If[n == 0, {1}, Map[Function[x, {x, x*n}], s[n-1]] // Flatten // Union]; a[n_] := Length[s[n]]; Table[an = a[n]; Print[n, " ", an]; an, {n, 0, 30}] (* Jean-François Alcover, Nov 01 2016, after Alois P. Heinz *)
PROG
(Python)
from functools import cache
@cache
def s(n): return {1} if n == 0 else s(n-1) | set(x*n for x in s(n-1))
def a(n): return len(s(n))
print([a(n) for n in range(30)]) # Michael S. Branicky, Jul 31 2022 after Alois P. Heinz
CROSSREFS
Sequence in context: A354255 A319385 A180249 * A322326 A018826 A342130
KEYWORD
nonn,nice
AUTHOR
Jonas Wallgren, May 10 2001
EXTENSIONS
More terms from Lior Manor May 26 2002
a(26)-a(32) from Giovanni Resta, Feb 14 2006
More terms from Martin Fuller, Jun 03 2006
a(0)=1 and a(37)-a(38) from Alois P. Heinz, Aug 25 2016
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 28 04:27 EDT 2023. Contains 365721 sequences. (Running on oeis4.)