A027424 -id:A027424 - cp's OEIS frontend

A366181 The number of 2n-digit integers that can be written as the product of two n-digit integers.

27, 2205, 194700, 17874052, 1678273759, 159696501022, 15330248094326, 1480695423269672

Offset: 1

Clive Tooth, Oct 03 2023

			a(1)=27. That is, when the integers are expressed in decimal, the number of 2-digit integers that can be written as the product of 2 single-digit integers is 27: 10=2*5, 12=2*6=3*4, 14=2*7, 15=3*5, 16=2*8=4*4, 18=2*9=3*6, 20=4*5, 21=3*7, 24=3*8=4*6, 25=5*5, 27=3*9, 28=4*7, 30=5*6, 32=4*8, 35=5*7, 36=4*9=6*6, 40=5*8, 42=6*7, 45=5*9, 48=6*8, 49=7*7, 54=6*9, 56=7*8, 63=7*9, 64=8*8, 72=8*9, 81=9*9
Note that each of the 2-digit integers 12, 16, 18, 24 and 36 can be expressed as a product of 2 single-digit integers in 2 ways. However, each of those 2-digit integers is only counted once.

Cf. A003991, A027424, A366165.

def A366181(n):
    a, b, c, d = 10**(n-1), 10**n, 10**((n<<1)-1), 10**(n<<1)
    return len({i*j for i in range(a,b) for j in range(min(i,c//i),min(b,d//i+1)) if c<=i*jChai Wah Wu, Oct 13 2023

a(6) from Hugo Pfoertner, Oct 12 2023
a(7) from Bert Dobbelaere, Oct 23 2023
a(8) from Clive Tooth and Benjamin Chaffin, Nov 06 2023

A073961 Let R be the polynomial ring GF(2)[x]. Then a(n) = number of distinct products f*g with f,g in R and 1 <= deg(f),deg(g) <= n.

Original entry on oeis.org

3, 18, 72, 262, 975, 3562, 13456, 50765, 194122, 745526, 2882670, 11173191, 43485970, 169656399, 663259282, 2598327983, 10190686903, 40038932993, 157431481559, 619871680780, 2442107519364, 9632769554849, 38008189079970, 150127212826428, 593141913076502

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 13 2003

nonn

W. Edwin Clark computed the initial terms.

			From _Andrew Howroyd_, Jul 10 2018: (Start)
Case n=1: The following 3 polynomials can be represented:
  x^2 = x*x,
  x^2 + 1 = (x + 1)*(x+1),
  x^2 + x = x*(x + 1).
(End)

Cf. A001037, A027424, A086908.

a(n) = A086908(n) - 1 - Sum_{i=0, n} A001037(i). - Andrew Howroyd, Jul 10 2018

a(9)-a(25) from Andrew Howroyd, Jul 10 2018

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

A373716 a(n) is the number of distinct products i*j minus the number of distinct sums i+j with 1 <= i, j <= n.

Original entry on oeis.org

0, 0, 1, 2, 5, 7, 12, 15, 19, 23, 32, 36, 47, 53, 60, 66, 81, 88, 105, 113, 123, 133, 154, 162, 176, 188, 201, 212, 239, 249, 278, 291, 307, 323, 341, 352, 387, 405, 424, 438, 477, 492, 533, 551, 570, 592, 637, 652, 681, 701, 726, 747, 798, 818, 847, 867, 895

Offset: 1

Darío Clavijo, Jun 22 2024

nonn

			a(5) = 5 because:
 Products:                   Sums:
 * | 1 |  2 |  3 |  4 |  5   + | 1 | 2 | 3 | 4 |  5
 -------------------------   -----------------------
 1 | 1 |  2 |  3 |  4 |  5   1 | 2 | 3 | 4 | 5 |  6
 2 | 2 |  4 |  6 |  8 | 10   2 | 3 | 4 | 5 | 6 |  7
 3 | 3 |  6 |  9 | 12 | 15   3 | 4 | 5 | 6 | 7 |  8
 4 | 4 |  8 | 12 | 16 | 20   4 | 5 | 6 | 7 | 8 |  9
 5 | 5 | 10 | 15 | 20 | 25   5 | 6 | 7 | 8 | 9 | 10
The number of distinct products [1,2,3,4,5,6,8,9,10,12,15,16,20,25] is 14.
The number of distinct sums [2,3,4,5,6,7,8,9,10] is 9.
So a(5) = 14 - 9 = 5.

Cf. A000290, A005408, A027424, A062851.

a(n) = #setbinop((x, y)->x*y, vector(n, i, i)) - 2*n + 1; \\ Michel Marcus, Jun 23 2024

A027424 = lambda n: len({i*j for i in range(1, n+1) for j in range(1, i+1)})
a = lambda n: A027424(n)-((n<<1)-1)
print([a(n) for n in range(1, 58)])

a(n) = A027424(n) - A005408(n-1).

a(n) = (n-1)^2 - A062851(n).

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

A085578 Array read by antidiagonals: T(m,n) is the number of distinct products ij with 1<=i<=m, i<=j<=n, for m>=1, n>=1.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 5, 5, 4, 5, 6, 6, 6, 5, 6, 8, 8, 8, 8, 6, 7, 9, 11, 9, 11, 9, 7, 8, 11, 12, 13, 13, 12, 11, 8, 9, 12, 15, 15, 14, 15, 15, 12, 9, 10, 14, 17, 19, 17, 17, 19, 17, 14, 10, 11, 15, 18, 20, 22, 18, 22, 20, 18, 15, 11, 12, 17, 20, 22, 24, 24, 24, 24, 22, 20, 17, 12, 13, 18, 23, 24, 27, 27, 25, 27, 27, 24, 23, 18, 13

Offset: 1

Michael Kleber, Jul 09 2003

			Array begins:
1 2 3 4 5 6 7 8 9 10 ...
2 3 5 6 8 9 11 12 14 15 ...
3 5 6 8 11 12 15 17 18 20 ...
4 6 8 9 13 15 19 20 22 24 ...
5 8 11 13 14 17 22 24 27 28 ...

A027424 is the main diagonal.

T := (m,n) -> nops({seq(seq(i*j, i=1..m),j=1..n)});

T[m_, n_] := Length[Union @@ Table[i*j, {i, m}, {j, n}]]

cp's OEIS Frontend

A366181 The number of 2n-digit integers that can be written as the product of two n-digit integers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Extensions

A073961 Let R be the polynomial ring GF(2)[x]. Then a(n) = number of distinct products f*g with f,g in R and 1 <= deg(f),deg(g) <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

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

A373716 a(n) is the number of distinct products i*j minus the number of distinct sums i+j with 1 <= i, j <= n.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI

Python

Formula

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

A085578 Array read by antidiagonals: T(m,n) is the number of distinct products ij with 1<=i<=m, i<=j<=n, for m>=1, n>=1.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica