cp's OEIS Frontend

A071603 Number of different positive integers that we can obtain from the integers {1,2,...,n} using each number at most once and the operators +, -, *, /, where intermediate subexpressions must be integers.

%I A071603 #12 Jul 01 2022 22:05:44
%S A071603 1,3,9,31,121,542,2868,16329,106762,758155,6142570
%N A071603 Number of different positive integers that we can obtain from the integers {1,2,...,n} using each number at most once and the operators +, -, *, /, where intermediate subexpressions must be integers.
%H A071603 <a href="/index/Fo#4x4">Index entries for similar sequences</a>
%e A071603 a(4)=31 because we can obtain the positive integers 1,2,...,28 and 30,32,36 by using the integers {1, 2, 3, 4} at most once and the four operations. For example 30 = 3*2*(4+1).
%o A071603 (Python)
%o A071603 def a(n):
%o A071603     R = dict() # index of each reachable subset is [card(s)-1][s]
%o A071603     for i in range(n): R[i] = dict()
%o A071603     for i in range(1, n+1): R[0][(i,)] = {i}
%o A071603     reach = set(range(1, n+1))
%o A071603     for j in range(1, n):
%o A071603         for i in range((j+1)//2):
%o A071603             for s1 in R[i]:
%o A071603                 for s2 in R[j-1-i]:
%o A071603                     if set(s1) & set(s2) == set():
%o A071603                         s12 = tuple(sorted(set(s1) | set(s2)))
%o A071603                         if s12 not in R[len(s12)-1]:
%o A071603                             R[len(s12)-1][s12] = set()
%o A071603                         for a in R[i][s1]:
%o A071603                             for b in R[j-1-i][s2]:
%o A071603                                 allowed = [a+b, a*b, a-b, b-a]
%o A071603                                 if a!=0 and b%a==0: allowed.append(b//a)
%o A071603                                 if b!=0 and a%b==0: allowed.append(a//b)
%o A071603                                 R[len(s12)-1][s12].update(allowed)
%o A071603                                 reach.update(allowed)
%o A071603     return len(set(r for r in reach if r > 0 and r.denominator == 1))
%o A071603 print([a(n) for n in range(1, 9)]) # _Michael S. Branicky_, Jul 01 2022
%Y A071603 Cf. A060315, A070960, A071848.
%K A071603 more,nonn
%O A071603 1,2
%A A071603 Koksal Karakus (karakusk(AT)hotmail.com), Jun 02 2002
%E A071603 a(10)-a(11) from _Michael S. Branicky_, Jul 01 2022