

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(n1), 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


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(n1)))
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}] (* JeanFrançois Alcover, Feb 02 2015 *)
s[n_] := s[n] = If[n == 0, {1}, Map[Function[x, {x, x*n}], s[n1]] // Flatten // Union]; a[n_] := Length[s[n]]; Table[an = a[n]; Print[n, " ", an]; an, {n, 0, 30}] (* JeanFrançois Alcover, Nov 01 2016, after Alois P. Heinz *)


CROSSREFS

Cf. A070861, A070863, A255937, A307105.
Sequence in context: A302588 A319385 A180249 * A322326 A018826 A258624
Adjacent sequences: A060954 A060955 A060956 * A060958 A060959 A060960


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



