A060957 - OEIS

A060957

Number of different products (including the empty product) of any subset of {1, 2, 3, ..., n}.

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

Cf. A070861, A070863, A255937, A307105.

Sequence in context: A354255 A319385 A180249 * A322326 A018826 A342130

Adjacent sequences: A060954 A060955 A060956 * A060958 A060959 A060960

KEYWORD