cp's OEIS Frontend

A347498 Least k such that there exists an n-element subset S of {1,2,...,k} with the property that all products i * j are distinct for i <= j.

%I A347498 #27 Sep 09 2021 09:37:58
%S A347498 1,2,3,5,6,7,9,11,13,15,17,19,20,23,25,28,29,31,33,37,40,41,42,43,47,
%T A347498 51,53,55,57,59,61,67,69,71,73,75,79,83
%N A347498 Least k such that there exists an n-element subset S of {1,2,...,k} with the property that all products i * j are distinct for i <= j.
%C A347498 a(n) <= A066720(n) and a(n+1) >= a(n) + 1
%F A347498 a(n) = min {k >= 1; A338006(k) = n}. - _Pontus von Brömssen_, Sep 09 2021
%e A347498    n | example set
%e A347498 -----+-------------------------------------------------------
%e A347498    1 | {1}
%e A347498    2 | {1, 2}
%e A347498    3 | {1, 2, 3}
%e A347498    4 | {1, 2, 3, 5}
%e A347498    5 | {1, 3, 4, 5,  6}
%e A347498    6 | {1, 3, 4, 5,  6,  7}
%e A347498    7 | {1, 2, 5, 6,  7,  8,  9}
%e A347498    8 | {1, 2, 5, 6,  7,  8,  9, 11}
%e A347498    9 | {1, 2, 5, 6,  7,  8,  9, 11, 13}
%e A347498   10 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15}
%e A347498   11 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17}
%e A347498   12 | {1, 2, 5, 7,  8,  9, 11, 12, 13, 15, 17, 19}
%e A347498   13 | {1, 5, 6, 7,  9, 11, 13, 14, 15, 16, 17, 19, 20}
%e A347498   14 | {1, 2, 5, 7, 11, 12, 13, 16, 17, 18, 19, 20, 21, 23}
%e A347498 For n = 4, the set {1,2,3,4} does not have distinct products because 2*2 = 1*4. However, the set {1,2,3,5} does have distinct products because 1*1, 1*2, 1*3, 1*5, 2*2, 2*3, 2*5, 3*3, 3*5, and 5*5 are all distinct.
%t A347498 Table[k=1;While[!Or@@(Length[s=Union[Sort/@Tuples[#,{2}]]]==Length@Union[Times@@@s]&/@Subsets[Range@k,{n}]),k++];k,{n,12}] (* _Giorgos Kalogeropoulos_, Sep 08 2021 *)
%o A347498 (Python)
%o A347498 from itertools import combinations, combinations_with_replacement
%o A347498 def a(n):
%o A347498     k = n
%o A347498     while True:
%o A347498         for Srest in combinations(range(1, k), n-1):
%o A347498             S = Srest + (k, )
%o A347498             allprods = set()
%o A347498             for i, j in combinations_with_replacement(S, 2):
%o A347498                 if i*j in allprods: break
%o A347498                 else: allprods.add(i*j)
%o A347498             else: return k
%o A347498         k += 1
%o A347498 print([a(n) for n in range(1, 15)]) # _Michael S. Branicky_, Sep 08 2021
%Y A347498 Analogous for sums: A003022 and A227590.
%Y A347498 Cf. A066720, A338006, A347499.
%K A347498 nonn,more
%O A347498 1,2
%A A347498 _Peter Kagey_, Sep 03 2021
%E A347498 a(15)-a(20) from _Michael S. Branicky_, Sep 08 2021
%E A347498 a(21)-a(38) (based on the terms in A338006) from _Pontus von Brömssen_, Sep 09 2021