A263995 -id:A263995 - cp's OEIS frontend

A337947 Numbers that do not appear in the addition or multiplication table of A337946.

5, 11, 16, 17, 18, 20, 26, 27, 28, 32, 35, 38, 39, 40, 41, 43, 45, 46, 51, 53, 55, 56, 57, 58, 63, 65, 67, 70, 71, 72, 74, 75, 76, 78, 79, 80, 81, 82, 87, 89, 93, 95, 96, 98, 99, 100, 101, 102, 103, 104, 105, 106, 109, 110, 111, 112, 117, 118, 119, 121, 123

Offset: 1

Peter Kagey, Oct 02 2020

nonn

			The addition table of A337946(k) for k=1..5:
   + | 1 3  7 12 22
  ---+-------------
   1 | 2 4  8 13 23
   3 |   6 10 15 25
   7 |     14 19 29
  12 |        24 34
  22 |           44
The multiplication table of A337946(k) for k=1..5:
   * | 1 3  7  12  22
  ---+---------------
   1 | 1 3  7  12  22
   3 |   9 21  36  66
   7 |     49  84 154
  12 |        144 264
  22 |            484
Neither of these two tables contain 5, 11, 16, 17, 18, or 20. Since each row is strictly increasing, the rest of the two (infinite) tables do not contain these values either.

Peter Kagey, Table of n, a(n) for n = 1..10000

Cf. A263995, A337657, A337658, A337946.

A352969 Start with {1}, then at each step replace it with the set of all pairwise products and sums of its elements (an element can be paired with itself). a(n) gives the number of elements after n-th step.

Original entry on oeis.org

1, 2, 4, 11, 52, 678, 67144, 357306081

Offset: 0

Vladimir Reshetnikov, Apr 12 2022

			After the 1st step the set becomes {1*1, 1+1} = {1, 2}. It has 2 distinct elements so a(1) = 2.
After the 2nd step the set becomes {1*1, 1+1, 1*2, 1+2, 2*2, 2+2} = {1, 2, 2, 3, 4, 4} = {1, 2, 3, 4}. It has 4 distinct elements so a(2) = 4.

Cf. A263995, A273525, A353535, A353536.

Length /@ NestList[DeleteDuplicates[Flatten[Table[With[{a = #[[k]], b = #[[;; k]]}, {a b, a + b}], {k, Length[#]}]]] &, {1}, 6]

lista(nn) = {my(v = [1]); print1(#v, ", "); for (n=1, nn, v = setunion(setbinop((x,y)->(x+y), v), setbinop((x,y)->(x*y), v)); print1(#v, ", "););} \\ Michel Marcus, Apr 13 2022

from math import prod
from itertools import combinations_with_replacement
from functools import lru_cache
@lru_cache(maxsize=None)
def A352969_set(n):
    if n == 0:
        return {1}
    return set(sum(x) for x in combinations_with_replacement(A352969_set(n-1),2)) | set(prod(x) for x in combinations_with_replacement(A352969_set(n-1),2))
def A353969(n):
    return len(A352969_set(n)) # Chai Wah Wu, Apr 15 2022

a(7) from Thomas Scheuerle, Apr 13 2022

a(7) corrected by Chai Wah Wu, Apr 15 2022

A263996 Smallest possible cardinality of the union of the set of pairwise sums and the set of pairwise products from a set of n positive integers.

Original entry on oeis.org

1, 4, 7, 11, 15, 20, 26, 30, 36, 44, 49, 57, 64, 71, 80, 86, 96, 104, 112, 121, 131, 141, 150, 160, 169, 179, 190, 200, 212, 222, 235, 248, 260, 272, 283, 296, 307, 320, 335, 348, 360, 371

Offset: 1

Hugo Pfoertner, Nov 15 2015

nonn

The November 2015 - February 2016 round of Al Zimmermann's programming contests asked for optimal sets producing a(40), a(80), a(120), ..., a(1000).

			a(1) = 1 because for the set {2} the union of {2+2} and {2*2} = {4}.
a(7) = 26: The set {1,2,3,4,6,8,12} has the set of pairwise sums {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24} and the set of pairwise products {1,2,3,4,6,8,9,12,16,18,24,32,36,48,64,72,96,144}. The cardinality of the union of the two sets, {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,18,20,24,32,36,48,64,72,96,144}, is 26. This is the first nontrivial case with a(n) < A263995(n), which uses the set {1..n}.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd ed., Springer-Verlag New York, 2004. Problem F18.

Hugo Pfoertner, Table of n, a(n) for n = 1..205
P. Erdős and E. Szemeredi, On sums and products of integers, Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 213-218. DOI:10.1007/978-3-0348-5438-2_19
Kevin Hartnett, How a Strange Grid Reveals Hidden Connections Between Simple Numbers, Quanta Magazine, Feb. 6 2019.
Al Zimmermann's Programming Contests, Sums and Products I, Nov 2015 - Feb 2016.

Cf. A027424, A263995.

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.

Original entry on oeis.org

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

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

nonn

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

			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.

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

Cf. A002088, A018805, A027424, A263995.

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

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 *)

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

# 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

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

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

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

Original entry on oeis.org

1, 1, 2, 4, 6, 9, 14, 17, 22, 27, 35, 40, 50, 56, 64, 71, 85, 92, 109, 117, 128, 139, 159, 168, 182, 194, 208, 219, 245, 256, 285, 298, 314, 331, 349, 361, 396, 414, 433, 448, 486, 502, 542, 560, 580, 602, 646, 661, 691, 711, 737, 759, 809

Offset: 1

Darío Clavijo, Jul 30 2024

In other words, these are the products that are not in {2..2*n}.
Essentialy each unique product i*j that is not i+j for 1 <= i, j <= n is in A254671+1.
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.
a(n) < A263995(n).

			a(3) = 2 because:
 Prods = [1, 2, 3, 2, 4, 6, 3, 6, 9]
 Sums = [2, 3, 4, 3, 4, 5, 4, 5, 6]
 Items in Prods not in Sums : [1,9]
Total: 2.
a(4) = 4 because:
 Prods = [1, 2, 3, 4, 2, 4, 6, 8, 3, 6, 9, 12, 4, 8, 12, 16]
 Sums = [2, 3, 4, 5, 3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8]
 Items in Prods not in Sums: [1, 9, 12, 16]
Total: 4.

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

a(n) = #select(x->((x>2*n) || (x<2)), setbinop((x,y)->x*y, [1..n])); \\ Michel Marcus, Jul 30 2024

def a(n):
    P = {i * j for i in range(1, n+1) for j in range(1, n+1)}
    return sum(1 for x in P if x > 2*n or x < 2)
print([a(n) for n in range(1,54)])

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

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

cp's OEIS Frontend

A337947 Numbers that do not appear in the addition or multiplication table of A337946.

Views

Author

Keywords

Examples

Links

Crossrefs

A352969 Start with {1}, then at each step replace it with the set of all pairwise products and sums of its elements (an element can be paired with itself). a(n) gives the number of elements after n-th step.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A263996 Smallest possible cardinality of the union of the set of pairwise sums and the set of pairwise products from a set of n positive integers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Python

Formula