|
| |
|
|
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
|
|
|
|
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)):
|
|
|
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))
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
