A370676 - OEIS

%I #44 Mar 06 2024 14:48:14

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

%N 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.

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

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

%C From _David A. Corneth_, Feb 27 2024: (Start)

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

%C 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)

%e For n=3 the a(3)=3 solutions are:

%e   3 * 51 = 153

%e   6 * 21 = 126

%e   8 * 86 = 688

%e For n=4 the a(4)=15 solutions are:

%e   3 * 501 = 1503

%e   3 * 510 = 1530

%e   5 * 251 = 1255

%e   6 * 201 = 1206

%e   6 * 210 = 1260

%e   8 * 473 = 3784

%e   8 * 860 = 6880

%e   9 * 351 = 3159

%e   15 * 93 = 1395

%e   21 * 60 = 1260

%e   21 * 87 = 1827

%e   27 * 81 = 2187

%e   30 * 51 = 1530

%e   35 * 41 = 1435

%e   80 * 86 = 6880

%o (Python)

%o def a(n):

%o     count = 0

%o     for i in range(1, 10**(n-1)):

%o         for j in range(i, 10**n//i+1):

%o             if len(str(i*j)) == n and sorted(str(i)+str(j)) == sorted(str(i*j)):

%o                 count += 1

%o     print(n, count)

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

%Y Cf. A370678, A370679, A370680.

%K nonn,base,more

%O 1,3

%A _Danila Potapov_, Feb 26 2024

%E a(9)-a(10) from _Michael S. Branicky_, Feb 26 2024

%E a(11) from _Chai Wah Wu_, Feb 27 2024

%E a(12)-a(13) from _Martin Ehrenstein_, Mar 02 2024