A126025 Number of mappings f:{1,2,3,...,n} -> {1,2,3,...,n} such that gcd(f(x),f(y)) = f(gcd(x,y)) for all x,y in {1,2,3,...,n}.

1, 3, 9, 26, 106, 191, 954, 2427, 8404, 15945, 111952, 141117, 1176623, 2270566, 4477947, 10345290, 104257447, 145407966, 1633452518, 2517488363, 5024167821, 9148333241, 120260250853

Offset: 1

Author

John W. Layman, Feb 27 2007

Keywords

• nonn
• more
• nice

Comments

The greatest common divisor condition was suggested by A061446.

Links

• Manfred Scheucher, Sage Script
• Manfred Scheucher, C Code

Crossrefs

Cf. A061446.

Cf. A000312.

Programs

Haskell

a126025 n = h n1s 0 where
   h us c = if us == nns then c + 1 else h (succ us) (c + g) where
     g = if and [f x `gcd` f y == f (x `gcd` y) |
                 x <- [1 .. n - 1], y <- [x + 1 .. n]] then 1 else 0
     f = (us !!) . subtract 1
   succ (z:zs) = if z < n then (z + 1) : zs else 1 : succ zs
   n1s = take n [1, 1 ..]; nns = take n [n, n ..]
-- Reinhard Zumkeller, May 04 2014

Extensions

a(10)-a(22) from Manfred Scheucher, Jun 06 2015

a(23) from Manfred Scheucher, Aug 13 2015