cp's OEIS Frontend

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.

%I A370676 #44 Mar 06 2024 14:48:14
%S A370676 0,0,3,15,98,596,3626,22704,146834,983476,6846451,49364315,367660050
%N 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.
%C A370676 Since multiplication and multiset union are commutative operations, we count unordered pairs, i.e., we can assume that k1 <= k2.
%C A370676 The sequence could be redefined in terms of the number of distinct n-digit numbers that could be factorized into such pairs.
%C A370676 From _David A. Corneth_, Feb 27 2024: (Start)
%C A370676 a(n) >= 2*a(n-1).
%C A370676 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 A370676 For n=3 the a(3)=3 solutions are:
%e A370676   3 * 51 = 153
%e A370676   6 * 21 = 126
%e A370676   8 * 86 = 688
%e A370676 For n=4 the a(4)=15 solutions are:
%e A370676   3 * 501 = 1503
%e A370676   3 * 510 = 1530
%e A370676   5 * 251 = 1255
%e A370676   6 * 201 = 1206
%e A370676   6 * 210 = 1260
%e A370676   8 * 473 = 3784
%e A370676   8 * 860 = 6880
%e A370676   9 * 351 = 3159
%e A370676   15 * 93 = 1395
%e A370676   21 * 60 = 1260
%e A370676   21 * 87 = 1827
%e A370676   27 * 81 = 2187
%e A370676   30 * 51 = 1530
%e A370676   35 * 41 = 1435
%e A370676   80 * 86 = 6880
%o A370676 (Python)
%o A370676 def a(n):
%o A370676     count = 0
%o A370676     for i in range(1, 10**(n-1)):
%o A370676         for j in range(i, 10**n//i+1):
%o A370676             if len(str(i*j)) == n and sorted(str(i)+str(j)) == sorted(str(i*j)):
%o A370676                 count += 1
%o A370676     print(n, count)
%Y A370676 Cf. A370675 (number of such n-digit pairs), A020342.
%Y A370676 Cf. A370678, A370679, A370680.
%K A370676 nonn,base,more
%O A370676 1,3
%A A370676 _Danila Potapov_, Feb 26 2024
%E A370676 a(9)-a(10) from _Michael S. Branicky_, Feb 26 2024
%E A370676 a(11) from _Chai Wah Wu_, Feb 27 2024
%E A370676 a(12)-a(13) from _Martin Ehrenstein_, Mar 02 2024