cp's OEIS Frontend

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

%I A060957 #51 Apr 16 2025 05:26:03
%S A060957 1,1,2,4,8,16,26,52,88,152,238,476,648,1296,2016,2984,4232,8464,11360,
%T A060957 22720,30544,43744,67072,134144,166336,242752,370992,498144,656832,
%U A060957 1313664,1581312,3162624,3960384,5517248,8386080,11111232,13065792,26131584,39690432
%N A060957 Number of different products (including the empty product) of any subset of {1, 2, 3, ..., n}.
%C A060957 a(n) <= 2*a(n-1), with equality iff n is prime or n = 4. - _Martin Fuller_, Jun 03 2006
%C A060957 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
%C A060957 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
%C A060957 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
%H A060957 Yan Sheng Ang, <a href="/A060957/b060957.txt">Table of n, a(n) for n = 0..68</a> (first 50 terms from David Radcliffe)
%e A060957 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.
%e A060957 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}
%p A060957 s:= proc(n) option remember; `if`(n=0, {1},
%p A060957       map(x-> [x, x*n][], s(n-1)))
%p A060957     end:
%p A060957 a:= n-> nops(s(n)):
%p A060957 seq(a(n), n=0..25);  # _Alois P. Heinz_, Aug 25 2016
%t A060957 (* 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 *)
%t A060957 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_ *)
%o A060957 (Python)
%o A060957 from functools import cache
%o A060957 @cache
%o A060957 def s(n): return {1} if n == 0 else s(n-1) | set(x*n for x in s(n-1))
%o A060957 def a(n): return len(s(n))
%o A060957 print([a(n) for n in range(30)]) # _Michael S. Branicky_, Jul 31 2022 after _Alois P. Heinz_
%Y A060957 Cf. A070861, A070863, A255937, A307105.
%K A060957 nonn,nice
%O A060957 0,3
%A A060957 _Jonas Wallgren_, May 10 2001
%E A060957 More terms from _Lior Manor_, May 26 2002
%E A060957 a(26)-a(32) from _Giovanni Resta_, Feb 14 2006
%E A060957 More terms from _Martin Fuller_, Jun 03 2006
%E A060957 a(0)=1 and a(37)-a(38) from _Alois P. Heinz_, Aug 25 2016