login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of distinct products i*j with 1 <= i, j <= n which are not the sum of two numbers between 1 and n.
1

%I #50 Aug 19 2024 13:16:56

%S 1,1,2,4,6,9,14,17,22,27,35,40,50,56,64,71,85,92,109,117,128,139,159,

%T 168,182,194,208,219,245,256,285,298,314,331,349,361,396,414,433,448,

%U 486,502,542,560,580,602,646,661,691,711,737,759,809

%N Number of distinct products i*j with 1 <= i, j <= n which are not the sum of two numbers between 1 and n.

%C In other words, these are the products that are not in {2..2*n}.

%C Essentialy each unique product i*j that is not i+j for 1 <= i, j <= n is in A254671+1.

%C Conversely the number of distinct sums i+j with 1 <= i, j <= n which are not the product of two numbers between 1 and n is A060715.

%C a(n) < A263995(n).

%F a(n) = A373716(n)+A108954(n).

%e a(3) = 2 because:

%e Prods = [1, 2, 3, 2, 4, 6, 3, 6, 9]

%e Sums = [2, 3, 4, 3, 4, 5, 4, 5, 6]

%e Items in Prods not in Sums : [1,9]

%e Total: 2.

%e a(4) = 4 because:

%e Prods = [1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16]

%e Sums = [2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8]

%e Items in Prods not in Sums: [1, 9, 12, 16]

%e Total: 4.

%o (Python)

%o def a(n):

%o P = {i * j for i in range(1, n+1) for j in range(1, n+1)}

%o return sum(1 for x in P if x > 2*n or x < 2)

%o print([a(n) for n in range(1,54)])

%o (Python)

%o def A375109(n): return len({i*j for i in range(1,n+1) for j in range((n<<1)//i+1,i+1)})+1 # _Chai Wah Wu_, Aug 19 2024

%o (PARI) a(n) = #select(x->((x>2*n) || (x<2)), setbinop((x,y)->x*y, [1..n])); \\ _Michel Marcus_, Jul 30 2024

%Y Cf. A027424, A060715, A108954, A254671, A263995, A373716.

%K nonn,easy

%O 1,3

%A _DarĂ­o Clavijo_, Jul 30 2024