A349145 Number of ordered n-tuples (x_1, x_2, x_3, ..., x_n) such that Sum_{k=1..n} k/x_k is an integer and x_k is an integer between 1 and n for 1 <= k <= n.

1, 1, 2, 8, 43, 207, 2391, 15539, 182078, 2070189, 35850460, 338695058, 10609401552, 115445915555

Offset

0,3

Links

Table of n, a(n) for n=0..13.

Example

1/1 + 2/1 = 3 and 3 is an integer.
1/1 + 2/2 = 2 and 2 is an integer.
1/2 + 2/1 = 5/2.
1/2 + 2/2 = 3/2.
So a(2) = 2.

Prog

(Ruby)
def A(n)
  return 1 if n == 0
  cnt = 0
  (1..n).to_a.repeated_permutation(n){|i|
    cnt += 1 if (1..n).inject(0){|s, j| s + j / i[j - 1].to_r}.denominator == 1
  }
  cnt
end
def A349145(n)
  (0..n).map{|i| A(i)}
end
p A349145(6)
(Python)
from fractions import Fraction
from itertools import product
def A349145(n): return sum(1 for d in product(range(1, n+1), repeat=n) if sum(Fraction(i+1, j) for i, j in enumerate(d)).denominator == 1) # Chai Wah Wu, Nov 09 2021

Crossrefs

Cf. A073090, A349146.

Sequence in context: A267619 A012917 A050637 * A188174 A193659 A020023

Adjacent sequences: A349142 A349143 A349144 * A349146 A349147 A349148

Keyword

nonn,more

Author

Seiichi Manyama, Nov 08 2021

Extensions

a(10)-a(13) from Alois P. Heinz, Nov 08 2021

Status

approved