A370676 Number of unordered pairs of natural numbers k1, k2 such that their product is an n-digit number and has the same multiset of digits as in both k1 and k2.

0, 0, 3, 15, 98, 596, 3626, 22704, 146834, 983476, 6846451, 49364315, 367660050

Offset: 1

Author

Danila Potapov, Feb 26 2024

Keywords

• nonn
• base
• more

Comments

Since multiplication and multiset union are commutative operations, we count unordered pairs, i.e., we can assume that k1 <= k2.

The sequence could be redefined in terms of the number of distinct n-digit numbers that could be factorized into such pairs.

From David A. Corneth, Feb 27 2024: (Start)

a(n) >= 2*a(n-1).

As we need k1 + k2 == k1 * k2 (mod 9) there are two possible pairs of residues (k1, k2) mod 3, namely, (0, 0) and (2, 2), and six possible residues mod 9, namely, (0, 0), (2, 2), (3, 6), (5, 8), (6, 3), (8, 5). (End)

Examples

			For n=3 the a(3)=3 solutions are:
  3 * 51 = 153
  6 * 21 = 126
  8 * 86 = 688
For n=4 the a(4)=15 solutions are:
  3 * 501 = 1503
  3 * 510 = 1530
  5 * 251 = 1255
  6 * 201 = 1206
  6 * 210 = 1260
  8 * 473 = 3784
  8 * 860 = 6880
  9 * 351 = 3159
  15 * 93 = 1395
  21 * 60 = 1260
  21 * 87 = 1827
  27 * 81 = 2187
  30 * 51 = 1530
  35 * 41 = 1435
  80 * 86 = 6880
		

Crossrefs

Cf. A370675 (number of such n-digit pairs), A020342.

Cf. A370678, A370679, A370680.

Programs

Python

def a(n):
    count = 0
    for i in range(1, 10**(n-1)):
        for j in range(i, 10**n//i+1):
            if len(str(i*j)) == n and sorted(str(i)+str(j)) == sorted(str(i*j)):
                count += 1
    print(n, count)

Extensions

a(9)-a(10) from Michael S. Branicky, Feb 26 2024

a(11) from Chai Wah Wu, Feb 27 2024

a(12)-a(13) from Martin Ehrenstein, Mar 02 2024