A180622 Number of distinct sums i+j, absolute differences |i-j|, products ij and quotients i/j and j/i with 1 <= i, j <= n.

3, 6, 12, 19, 30, 38, 56, 68, 86, 100, 129, 143, 178, 197, 222, 246, 293, 313, 367, 392, 428, 460, 525, 551, 606, 643, 694, 730, 813, 841, 931, 977, 1034, 1084, 1151, 1188, 1296, 1351, 1419, 1467, 1586, 1627, 1752, 1811, 1880, 1947, 2084, 2132, 2247, 2308

Offset: 1

Author

Hein van Winkel (hein65(AT)duizendknoop.com), Sep 12 2010

Keywords

• nonn

Comments

I was inspired by the 24-game. How many results can you get from two numbers by addition, subtraction, multiplication and division?

Examples

			For n = 3 sums 2, 3, 4, 5, 6 differences 0, 1, 2 multiplications 1, 2, 3, 4, 6, 9 divisions 1/2, 1/3, 2/3, 2, 3, 3/2 different results are 2, 3, 4, 5, 6, 0, 1, 9, 1/2, 1/3, 2/3, 3/2 or ordered 0, 1/3, 1/2, 2/3, 1, 3/2, 2, 3, 4, 5, 6, 9 so f(3) = 12.
		

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..10000 (terms 1..2000 from Owen Whitby)

Crossrefs

Cf. A002088, A018805, A027424, A263995.

Programs

Maple

A180622 := proc(n) s := {} ; for i from 1 to n do for j from 1 to n do s := s union {i+j} ; s := s union {abs(i-j)} ; s := s union {i*j} ; s := s union {i/j} ; s := s union {j/i} ; end do: end do: nops(s) ; end proc: seq(A180622(n),n=1..83) ; # R. J. Mathar, Sep 19 2010

Mathematica

a180622[maxn_] := Module[{seq = {}, vals = {}, vnew, an, n1}, Do[vnew = {}; n1 = n - 1; Do[vnew = vnew~Join~{i + n, n - i, i*n, i/n, n/i}, {i, n1}]; vnew = vnew~Join~{n + n, 0, n*n, 1}; vals = Union[vals, vnew]; an = Length[vals]; AppendTo[seq, an], {n, maxn}]; seq] (* Owen Whitby, Nov 03 2010 *)

Python

from fractions import Fraction
def A180622(n): return len(set(range((n<<1)+1))|set().union(*({i*j,Fraction(i,j),Fraction(j,i)} for i in range(1,n+1) for j in range(1,i+1)))) # Chai Wah Wu, Aug 21 2024

Python

# faster program
from functools import lru_cache
from sympy import primepi
def A180622(n):
    @lru_cache(maxsize=None)
    def f(n): # based on second formula in A018805
        if n == 0:
            return 0
        c, j = 0, 2
        k1 = n//j
        while k1 > 1:
            j2 = n//k1 + 1
            c += (j2-j)*(f(k1)-1)
            j, k1 = j2, n//j2
        return (n*(n-1)-c+j)
    return len({i*j for i in range(1,n+1) for j in range(1,i+1)})+f(n)+primepi(n<<1)-primepi(n)-n # Chai Wah Wu, Aug 21 2024

Formula

a(n) = A263995(n) + 2*A002088(n) - n = A263995(n) + A018805(n) - n + 1. To see this, terms of the form |i-j| are covered by terms of the form i+j or i*j with the exception of 0. Thus i+j, |i-j| and ij result in A263995(n)+1 distinct terms. Terms i/j where gcd(i,j) > 1 can be reduced to a term i'/j' where gcd(i',j')=1. The only terms left are i/j with gcd(i,j) = 1 for which there are A018805(n) such terms. We need to subtract n terms for the cases where j=1 since i/j=i/1 are integers. This results in the formula. - Chai Wah Wu, Aug 21 2024

Extensions

More terms from R. J. Mathar, Sep 19 2010